Using Selective Orthonormalization to Update the Analytic Center after Addition of Multiple Cuts

We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope. This is an important issue that arises at every stage of cutting-plane algorithms. If q n cuts are to be added, we show that we can use a selective orthonormalization procedure to modify the cuts before adding them; it is then easy to identify a direction for an affine step into the interior of the new polytope and the next analytic center is then found in O(qlog q) Newton steps. Further, we show that multiple cut variants with selective orthonormalization of standard interior-point cutting-plane algorithms have the same complexity as the original algorithms.This research was partially supported by ONR Grant N00014-94-1-0391, by NSF Grants CCR-9901822 and DMS-0317323, and by a grant from the Dutch NWO and Delft University of Technology for the 1997–98 academic year, while the senior author was visiting ITS/TWI/SSOR. The authors thanks two anonymous referees for careful reading of the paper and useful suggestions.     

An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

On the Universal Partition Theorem for 4-Polytopes

By means of sign-patterns any finite family of polynomials induces a decomposition of R ⁿ into basic semialgebraic sets. In case of integer coefficients the latter decomposition roughly appears to be a partition into realization spaces of 4 -polytopes. The latter is stated by the Universal Partition Theorem for 4 -polytopes by Richter-Gebert. The present paper presents a different proof. As its main tool, the von Staudt polytope is introduced. The von Staudt polytope constitutes the polytopal equivalent of the well-known von Staudt constructions for point configurations. With the aid of the von Staudt polytope the original ideas of universality theory can be directly applied to the polytopal case. Moreover, a new method for representing real values (on a computation line) by polytopal means is presented. This method implies a bundling strategy in order to duplicate the encoded information. Based on this approach, the following complexity result is obtained. The incidence code of a polytope, exhibiting a realization space equivalent to a given semialgebraic set, can be computed in the same time that it requires to generate the defining polynomial system. Received December 19, 1995, and in revised form December 16, 1996, April 28, 1997, and September 10, 1997.     

Higher integrality conditions, volumes and Ehrhart polynomials

A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.     

A Commuting q-Analogue of the Addition Formula for Disk Polynomials

Starting from the addition formula for q-disk polynomials, which is an identity in noncommuting variables, we establish a basic analogue in commuting variables of the addition and product formula for disk polynomials. These contain, as limiting cases, the addition and product formula for little q-Legendre polynomials. As q tends to 1 the addition and product formula for disk polynomials are recovered. Date received: September 29, 1995. Date revised: May 20, 1996.     

Supermodularity in Mean-Partition Problems*

Supermodularity of the λ function which defines a permutation polytope has proved to be crucial for the polytope to have some nice fundamental properties. Supermodularity has been established for the λ function for the sum-partition problem under various models. On the other hand, supermodularity has not been established for the mean-partition problem even for the most basic labeled single-shape model. In this paper, we fill this gap and also settle for all other models except one. We further extend our results to other types of supermodularity. *This research is partially supported by a Republic of China National Science grant NSC 92-2115-M-009-014.     

Some Basic Lommel Polynomials

The basic Lommel polynomials associated to the₁₁q-Bessel function and the Jacksonq-Bessel functions are considered as orthogonal polynomials inq^ν, whereνis the order of the corresponding basic Bessel functions. The corresponding moment problems are both indeterminate and determinate depending on a parameter. Using techniques of Chihara and Maki we derive an explicit orthogonality measure, which is discrete and unbounded. For the indeterminate moment problem this measure is N-extremal. Some results on the zeros of the basic Bessel functions, both as functions of the order and of the argument are obtained. Precise asymptotic behaviour of the zeros of the₁₁q-Bessel function is obtained.     

Embedding a polytope in a lattice

We present a special similarity ofR ⁴ⁿ which maps lattice points into lattice points. Applying this similarity, we prove that if a (4n−1)-polytope is similar to a lattice polytope (a polytope whose vertices are all lattice points) inR ⁴ⁿ , then it is similar to a lattice polytope inR ⁴ⁿ⁻¹, generalizing a result of Schoenberg [4]. We also prove that ann-polytope is similar to a lattice polytope in someR ^N if and only if it is similar to a lattice polytope inR ²ⁿ⁺¹, and if and only if sin²(<ABC) is rational for any three verticesA, B, C of the polytope.     

Matroid Polytopes and their Volumes

We express the matroid polytope P _M of a matroid M as a signed Minkowski sum of simplices, and obtain a formula for the volume of P _M . This gives a combinatorial expression for the degree of an arbitrary torus orbit closure in the Grassmannian Gr _k,n . We then derive analogous results for the independent set polytope and the underlying flag matroid polytope of M. Our proofs are based on a natural extension of Postnikov’s theory of generalized permutohedra.     

Well-posed reduction formulas for the <Emphasis Type="Italic">q</Emphasis>-Kampé-de-Fériet function

By using the limiting case of Watson’s q-Whipple transformation as n → ∞, we investigate the transformations of the nonterminating q-Kampé-de-Fériet series. Further, new formulas for the transformations and well-posed reduction formulas are established for the basic Clausen hypergeometric series. Several remarkable formulas are also found for new function classes beyond the q-Kampé-de-Fériet function.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999     

Dilation of Newton Polytope and <Emphasis Type="Italic">p</Emphasis>-adic Estimate

Let f(X) be a polynomial in n variables over the finite field  \mathbbF_q\mathbb{F}_{q}. Its Newton polytope Δ(f) is the convex closure in ℝ ⁿ of the origin and the exponent vectors (viewed as points in ℝ ⁿ ) of monomials in f(X). The minimal dilation of Δ(f) such that it contains at least one lattice point of $\mathbb{Z}_{>0}^{n}$\mathbb{Z}_{>0}^{n} plays a vital pole in the p-adic estimate of the number of zeros of f(X) in  \mathbbF_q\mathbb{F}_{q}. Using this fact, we obtain several tight and computational bounds for the dilation which unify and improve a number of previous results in this direction.     

Lie algebras and recurrence relations III:q-analogs and quantized algebras

q-Analogs of the basic structures discussed in Lie Algebras and Recurrence Relations I are presented. Theq-Heisenberg-Weyl (qHW) and qsl(2) algebras are discussed in detail. Presently it is known that such structures are very closely tied in with the theory of quantum groups. Among other topics, coherent state representations and their interpretations asq-identities forq-Hermite and Al-Salam-Chihara (q-Meixner) polynomials are discussed. A discussion of Clebsch-Gordan coefficients for a qsu(2)-type algebra is presented.