Types of maximum noninteger vertices of the relaxation polyhedron of the four-index axial assignment problem

We describe various types of maximum noninteger vertices. We identify types of polyhedron vertices by the number of fractional components contained in three-sections of fourindex matrices representing the polyhedron vertices.     

Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem

For the relaxation polyhedron M(4, n) in the four-index axial assignment problem of order n, n ≥ 3, a characterization of all possible types (except for a single case) of maximum noninteger vertices, i.e., vertices with 4n — 3 fractional components is proposed. A formula enumerating all the maximum noninteger vertices of the same type in M(4, n) is derived.     

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.     

Master corner polyhedron: Vertices

We focus on the vertices of the master corner polyhedron (MCP), a fundamental object in the theory of integer linear programming. We introduce two combinatorial operations that transform vertices to their neighbors. This implies that each MCP can be defined by the initial vertices regarding these operations; we call them support vertices. We prove that the class of support vertices of all MCPs over a group is invariant under automorphisms of this group and describe MCP vertex bases. Among other results, we characterize its irreducible points, establish relations between a vertex and the nontrivial facets that pass through it, and prove that this polyhedron is of diameter 2.     

The generalized Estermann ternary problem for noninteger powers with almost equal summands

An asymptotic formula in the generalized Estermann ternary problem for noninteger powers with almost equal summands dealing with the representation of a sufficiently large natural number as the sum of two primes and the integer part of a noninteger power of a natural number is proved.     

Polyhedra related to a lattice

Without using the l.p. duality theorem, we give a new and direct proof that Hoffman's lattice polyhedra, polyhedra from problems of Edmonds and Giles, and others, are integer. These polyhedra are intersections of more simple polyhedra such that every vertex of the initial polyhedron is a vertex of some simple polyhedron. In many cases encountered in combinatorics the simple polyhedra have a totally unimodular constraint matrix. This implies that all vertices of the initial polyhedron are integral. The proof is based on a theorem on submodular functions, which was not known earlier. The method of this paper can be applied to the consideration of the matching polyhedron.     

Vertex-faithful regular polyhedra

We study the abstract regular polyhedra with automorphism groups that act faithfully on their vertices, and show that each non-flat abstract regular polyhedron covers a “vertex-faithful” polyhedron with the same number of vertices. We then use this result and earlier work on flat polyhedra to study abstract regular polyhedra based on the size of their vertex set. In particular, we classify all regular polyhedra where the number of vertices is prime or twice a prime. We also construct the smallest regular polyhedra with a prime squared number of vertices.     

On the difficulty of triangulating three-dimensional Nonconvex Polyhedra

A number of different polyhedraldecomposition problems have previously been studied, most notably the problem of triangulating a simple polygon. We are concerned with thepolyhedron triangulation problem: decomposing a three-dimensional polyhedron into a set of nonoverlapping tetrahedra whose vertices must be vertices of the polyhedron. It has previously been shown that some polyhedra cannot be triangulated in this fashion. We show that the problem of deciding whether a given polyhedron can be triangulated is NP-complete, and hence likely to be computationally intractable. The problem remains NP-complete when restricted to the case of star-shaped polyhedra. Various versions of the question of how many Steiner points are needed to triangulate a polyhedron also turn out to be NP-hard.This work was supported by National Science Foundation Grant CCR-8809040.     

Complexity of linear relaxations in integer programming

Mathematical Programming - For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the...     

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.     

A polyhedron of genus 4 with minimal number of vertices and maximal symmetry

We construct a symmetric polyhedron of genus 4 in R ³ with 11 vertices. This shows that for given genus g the minimal numbers of vertices of combinatorial manifolds and of polyhedra coincide in the first previously unknown case g=4 also. We show that our polyhedron has the maximal symmetry for the given genus and minimal number of vertices.     

Classification of Refinable Splines

A refinable spline is a compactly supported refinable function that is piecewise polynomial. Refinable splines, such as the well-known B-splines, play a key role in computer aided geometric design. So far all studies on refinable splines have focused on positive integer dilations and integer translations, and under this setting a rather complete classification was obtained in [12]. However, refinable splines do not have to have integer dilations and integer translations. The classification of refinable splines with noninteger dilations and arbitrary translations is studied in this paper. We classify completely all refinable splines with integer translations and arbitrary dilations. Our study involves techniques from number theory and complex analysis.     

On rainbowness of semiregular polyhedra

We introduce the rainbowness of a polyhedron as the minimum number k such that any colouring of vertices of the polyhedron using at least k colours involves a face all vertices of which have different colours. We determine the rainbowness of Platonic solids, prisms, antiprisms and ten Archimedean solids. For the remaining three Archimedean solids this parameter is estimated. Dedicated to Professor Miroslav Fiedler on the occasion of his 80th birthday.     

The vertices of the knapsack polytope

The number of vertices of a polytope associated to the Knapsack integer programming problem is shown to be small. An algorithm for finding these vertices is discussed.     

Some estimates for the number of vertices of integer polyhedra

A polyhedron is called integer if its every vertex has integer coordinates. We consider integer polyhedra P _I = conv(P ∩ ? ^d ) defined implicitly; that is, no system of linear inequalities is known for P _I but some is known for P. Some estimates are given for the number of vertices of P _I .     

Combinatorial structure and adjacency of vertices of polytope of b-factors

In the present paper in terms of the graph theory we describe the structure and vertices adjacency criterion of b-factors polyhedron. The special attention is paid to nonintegral vertices. Results of the present paper, in particular, generalize properties of nonintegral vertices of TSP polyhedron, give vertices adjacency criterion of a transportation polytope.     

On nonnegative solutions of random systems of linear inequalities

The set of nonnegative solutions of a system of linear equations or inequalities is a convex polyhedron. If the coefficients of the system are chosen at random, the number of vertices of this polyhedron is a random variable. Its expected value, dependent on the probability distribution of the coefficients, which are assumed to be nonnegative throughout, is investigated, and a distribution-independent upper bound for this expected value is established.     

The Median of the Number of Simple Paths on Three Vertices in the Random Graph

We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer b and a sufficiently large number n of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is b decreases with n. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large n.

     

On the facets of the mixed–integer knapsack polyhedron

We study the mixed–integer knapsack polyhedron, that is, the convex hull of the mixed–integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet–defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed–integer programming.Supported, in part, by NSF grants DMII–0070127 and DMII–0218265.Mathematics Subject Classification (2000): 90C10, 90C11, 90C57