Bounds on the number of vertices of perturbed polyhedra

Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.     

Nonflexible polyhedra with a small number of vertices

The paper shows which embedded and immersed polyhedra with no more than eight vertices are nonflexible. It turns out that all embedded polyhedra are nonflexible, except possibly for polyhedra of one of the combinatorial types, for which the problem still remains open. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 1, pp. 143–165, 2006.     

New estimates for the number of integer polynomials with given discriminants

Lithuanian Mathematical Journal - In this paper, we propose a new method of upper bounds for the number of integer polynomials of the fourth degree with a given discriminant. By direct calculation...     

Quadratic estimates for the number of integer points in convex bodies

We give bounds for the mean square deviation with respect to arbitrary probability measures of the number of integer points in translated or dilated convex bodies. The proofs are based on Fourier analytic methods.     

On recognizing integer polyhedra

We give a simple proof that, determining whether a convex polytope has a fractional vertex, is NP-complete.Research supported by the National Science Foundation.     

On integer points in polyhedra

We give an upper bound on the number of vertices ofP _I , the integer hull of a polyhedronP, in terms of the dimensionn of the space, the numberm of inequalities required to describeP, and the size of these inequalities. For fixedn the bound isO(m ^{n n–} ). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1+ in time polynomial inm, and 1/ when the dimensionn is fixed.Supported by Sonderfschungsbereich 303 (DFG) and NSF grant ECS-8611841.Partially supported by NSF grant DMS-8905645.Supported by NSF grants ECS-8418392 and CCR-8805199.mcd%vax.oxford.ac.uk     

Total dual integrality and integer polyhedra

A linear system Ax ? b (A, b rational) is said to be totally dual integral (TDI) if for any integer objective function c such that max {cx: Ax ? b} exists, there is an integer optimum dual solution. We show that if P is a polytope all of whose vertices are integer valued, then it is the solution set of a TDI system Ax ? b where b is integer valued. This was shown by Edmonds and Giles [4] to be a sufficient condition for a polytope to have integer vertices.     

Representing polyhedra: faces are better than vertices

This paper investigates the reconstruction of planar-faced polyhedra given their spherical dual representation. The spherical dual representation for any genus 0 polyhedron is shown to be unambiguous and to be uniquely reconstructible in polynomial time. It is also shown that when the degree of the spherical dual representation is at most four, the representation is unambiguous for polyhedra of any genus. The first result extends, in the case of planar-faced polyhedra, the well known result that a vertex or face connectivity graph represents a polyhedron unambiguously when the graph is triconnected and planar. The second result shows that when each face of a polyhedron of arbitrary genus has at most four edges, the polyhedron can be reconstructed uniquely. This extends the previous result that a polyhedron can be uniquely reconstructed when each face of the polyhedron is triangular. As a consequence of this result, faces are a more powerful representation than vertices for polyhedra whose faces have three or four edges. A result of the reconstruction algorithm is that high level features of the polyhedron are naturally extracted. Both results explicitly use the fact that the faces of the polyhedron are planar. It is conjectured that the spherical dual representation is unambiguous for polyhedra of any genus.     

Local minima of lattices and vertices of Klein polyhedra

We prove that each vertex of a Klein polyhedron of a lattice is a local minimum.     

The localization for eigenfunctions of the dirichlet problem in thin polyhedra near the vertices

Under some geometric assumptions, we show that eigenfunctions of the Dirichlet problem for the Laplace operator in an n-dimensional thin polyhedron localize near one of its vertices. We construct and justify asymptotics for the eigenvalues and eigenfunctions. For waveguides, which are thin layers between periodic polyhedral surfaces, we establish the presence of gaps and find asymptotics for their geometric characteristics.     

Efficient enumeration of the vertices of polyhedra associated with network LP's

Algorithms are given to list the vertices of polyhedra associated with network linear programs and their duals. Each algorithm has running time which is quadratic in the number of vertices of the polyhedron, and does not require that the polyhedron be either bounded or simple. The algorithms use characterizations of adjacent vertices in network and dual network LP's to perform an efficient traversal of the edge graph of the polyhedron. This contrasts with algorithms for enumerating the vertices of a general polyhedron, all of which have worst-case complexity which is exponential in the number of vertices of the polyhedron.     

A criterion for the integral equivalence of two generalized convex integer polyhedra

We introduce the notion of integral equivalence and formulate a criterion for the equivalence of two polyhedra having certain special properties. The category of polyhedra under consideration includes Klein polyhedra, which are the convex hulls of nonzero points of the lattice ?³ that belong to some 3-dimensional simplicial cone with vertex at the origin, and therefore the criterion enables one to improve some results related to Klein polyhedra. In particular, we suggest a simplified formulation of a geometric analog of Lagrange’s theorem on continued fractions in the three-dimensional case.     

The rank of (mixed-) integer polyhedra

We define a purely geometrical notion of the rank of (mixed-) integer rational polyhedra that differs substantially from the existing notions found in the literature.     

Relaxations of mixed integer sets from lattice-free polyhedra

This paper gives an introduction to a recently established link between the geometry of numbers and mixed integer optimization. The main focus is to provide a review of families of lattice-free polyhedra and their use in a disjunctive programming approach. The use of lattice-free polyhedra in the context of deriving and explaining cutting planes for mixed integer programs is not only mathematically interesting, but it leads to some fundamental new discoveries, such as an understanding under which conditions cutting planes algorithms converge finitely.     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

Realization of nets of convex polyhedra with equiangular vertices. 5

A complete list of convex polyhedra with equiangular vertices up to combinatorial equivalence is found. In the list are 104 closed polyhedra, 26 infinite polyhedra, and three infinite series — cones and polyhedra dual to prisms and antiprisms. One table.Translated from Ukrainskií Geometricheskií Sbornik, No. 30, 1987, pp. 22–36.     

Realization of nets of convex polyhedra with equiangular vertices. 3

Translated from Ukrainskií Geometricheskií Sbornik, No. 28, 1985, pp. 26–43.