Neighborly cubical spheres and a cubical lower bound conjecture

Using mirrors and cyclic polytopes, we construct cubicald-spheres which are the analogs of cyclic polytopes in the sense that they have the ⌉d−1/2⌈-skeleta of cubes. The existence of these neighborly cubical spheres leads to a special case of an upper bound conjecture for cubical spheres, suggested by Kalai. We extend the same construction to show that the closed convex hull off-vectors of cubical spheres contains a cone described by Adin, as an analog to the generalized lower bound theorem for simplicial polytopes. Supported in part, respectively, by an NSF Postdoctoral Fellowship; NSF Grants DMS 9207700 and 9500581; and an NSF Planning Grant.     

On the generalized lower bound conjecture for polytopes and spheres

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If P is a simplicial d-polytope then its h-vector (h ₀, h ₁, …, h _d ) satisfies $ {h_0}\leq {h_1}\leq \ldots \leq {h_{{\left\lfloor {{d \left/ {2} \right.}} \right\rfloor }}} $ . Moreover, if h _r?1 = h _r for some $ r\leq \frac{1}{2}d $ then P can be triangulated without introducing simplices of dimension ≤d ? r. The first part of the conjecture was solved by Stanley in 1980 using the hard Lefschetz theorem for projective toric varieties. In this paper, we give a proof of the remaining part of the conjecture. In addition, we generalize this result to a certain class of simplicial spheres, namely those admitting the weak Lefschetz property.     

The generalization of Minkowski problems for polytopes

The generalization of Minkowski problems, such as the $L_p$ and Orlicz Minkowski problems, have caused wide concern recently. In this paper, we will establish the existence of the Orlicz Minkowski problem for polytopes. In particular, a solution to the $L_p$ Minkowski problem for polytopes with $p>1$ is given. By the uniqueness of this solution, we present a new proof of the $L_p$ Minkowski inequality that demonstrates the relationship between these two fundamental theorems of the $L_p$ Brunn–Minkowski theory.     

A lower bound on the number of sharp shadow-boundaries of convex polytopes

We give the lower bound on the number of sharp shadow-boundaries of convexd-polytopes (or unbounded convex polytopal sets) withn facets. The polytopes (sets) attaining these bounds are characterized. Additionally, our results will be transferred to the dual theory.The research work of the first author was (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1812.     

Gaps in the numbers of vertices of cubical polytopes,I

A cubical polytope is a convex polytope of which very facet is a combinatorial cube. We ask for the numbers which occur as vertex numbers ofd-dimensional cubical polytopes, and we show, as a first step, that every cubicald-polytope for evend≥4 has an even number of vertices.     

Projection problems for symmetric polytopes

Let K⊂Rn be a convex body (a compact, convex subset with non-empty interior), ΠK its projection body. Finding the least upper bound, as K ranges over the class of origin-symmetric convex bodies, of the affine-invariant ratio V(ΠK)/V(K)ⁿ⁻¹, being called Schneider's projection problem, is a well-known open problem in the convex geometry. To study this problem, Lutwak, Yang and Zhang recently introduced a new affine invariant functional for convex polytopes in Rn. For origin-symmetric convex polytopes, they posed a conjecture for the new functional U(P). In this paper, we give an affirmative answer to the conjecture in Rn, thereby, obtain a modified version of Schneider's projection problem.     

On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.     

The parameterized upper and lower triangular splitting methods for saddle point problems

Complex moment-based eigensolvers for solving interior eigenvalue problems have been studied because of their high parallel efficiency. Recently, we proposed the block Arnoldi-type complex moment-based eigensolver without a low-rank approximation. A low-rank approximation plays a very important role in reducing computational cost and stabilizing accuracy in complex moment-based eigensolvers. In this paper, we develop the method and propose block Krylov-type complex moment-based eigensolvers with a low-rank approximation. Numerical experiments indicate that the proposed methods have higher performance than the block SS–RR method, which is one of the most typical complex moment-based eigensolvers.     

Equilibrium problems with lower and upper bounds

In this paper, we obtain some existence results of equilibrium problems with lower and upper bounds by employing a fixed-point theorem due to Ansari and Yao [1] and Ky Fan Lemma [2], respectively. Our results give answers to the open problem raised by Isac, Sehgal and Singh [3].     

Weighted quasi-equilibrium problems with lower and upper bounds

This paper is devoted to studying the solution existence of weighted quasi-equilibrium problems with lower and upper bounds by using maximal element theorems, a fixed point theorem of set-valued mappings and Fan–KKM theorem, respectively. Some new results are obtained.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Systems of quasi-equilibrium problems with lower and upper bounds

In this work, we consider systems of quasi-equilibrium problems with lower and upper bounds and establish the existence of their solutions by using some known maximal element theorems for a family of multivalued maps. Our problems are more general than the one posed in [G. Isac, V.M. Sehgal, S.P. Singh, An alternative version of a variational inequality, Indian J. Math. 41 (1999) 25–31]. As a particular case, we also get the answer to the problem raised in [G. Isac, V.M. Sehgal, S.P. Singh, An alternative version of a variational inequality, Indian J. Math. 41 (1999) 25–31].     

Singular problems motivated from classical upper and lower solutions

General existence criteria are presented for nonlinear singular boundary value problems. Our nonlinearity may be singular in both the dependent and independent variable. This revised version was published online in June 2006 with corrections to the Cover Date.     

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems

Due to the growing interest in approximation for multiobjective optimization problems (MOPs), a theoretical framework for defining and classifying sets representing or approximating solution sets for MOPs is developed. The concept of tolerance function is proposed as a tool for modeling representation quality. This notion leads to the extension of the traditional dominance relation to \(t\hbox {-}\)dominance. Two types of sets representing the solution sets are defined: covers and approximations. Their properties are examined in a broader context of multiple solution sets, multiple cones, and multiple quality measures. Applications to complex MOPs are included.     

The method of upper and lower solutions for diffraction problems of quasilinear elliptic reaction-diffusion systems

The aim of this paper is to show the existence of solutions of the n-dimensional diffraction problem for weakly coupled quasilinear elliptic reaction-diffusion system. The coefficients of the equations under consideration are allowed to be discontinuous. We extend the method of upper and lower solutions for reaction-diffusion equations with continuous coefficients to the elliptic diffraction problem. An application of these results is given to the steady-state problem of Lotka-Volterra cooperation model with two cooperating species.