On the combinatorial structure of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.     

Lifting the facets of zero–one polytopes

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero–one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero–one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality).     

On hyperbolic Coxeter polytopes with mutually intersecting facets

We prove that, apart from some well-known low-dimensional examples, any compact hyperbolic Coxeter polytope has a pair of disjoint facets. This is one of very few known general results concerning combinatorics of compact hyperbolic Coxeter polytopes. We also obtain a similar result for simple non-compact polytopes.     

Clique facets of the axial and planar assignment polytopes

The (k,s) assignment problem sets a unified framework for studying the facial structure of families of assignment polytopes. Through this framework, we derive classes of clique facets for all axial and planar assignment polytopes. For each of these classes, a polynomial-time separation procedure is described. Furthermore, we provide computational experience illustrating the efficiency of these facet-defining inequalities when applied as cutting planes.     

On approximation by projections of polytopes with few facets

We provide an affirmative answer to a problem posed by Barvinok and Veomett in [4], showing that in general an n-dimensional convex body cannot be approximated by a projection of a section of a simplex of subexponential dimension. Moreover, we prove that for all 1 ≤ n ≤ N there exists an n-dimensional convex body B such that for every n-dimensional convex body K obtained as a projection of a section of an N-dimensional simplex one has $$d(B,K) \geqslant c\sqrt {\frac{n}{{\ln \frac{{2N\ln (2N)}}{n}}}} $$ , where d(·, ·) denotes the Banach-Mazur distance and c is an absolute positive constant. The result is sharp up to a logarithmic factor.     

Coxeter polytopes with a unique pair of non-intersecting facets

We consider compact hyperbolic Coxeter polytopes whose Coxeter diagram contains a unique dotted edge. We prove that such a polytope in d-dimensional hyperbolic space has at most d+3 facets. In view of results by Kaplinskaja [I.M. Kaplinskaya, Discrete groups generated by reflections in the faces of simplicial prisms in Lobachevskian spaces, Math. Notes 15 (1974) 88-91] and the second author [P. Tumarkin, Compact hyperbolic Coxeter n-polytopes with n+3 facets, Electron. J. Combin. 14 (2007), R69, 36 pp.], this implies that compact hyperbolic Coxeter polytopes with a unique pair of non-intersecting facets are completely classified. They do exist only up to dimension 6 and in dimension 8.     

On the complete set packing and set partitioning polytopes: Properties and rank 1 facets

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary $n$-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

Note dual polytopes of rational convex polytopes

LetP ^d be a rational convex polytope with dimP=d such that the origin of ^d is contained in the interiorP – P ofP. In this paper, from a viewpoint of enumeration of certain rational points inP (which originated in Ehrhart's work), a necessary and sufficient condition for the dual polytopeP ^dual ofP to be integral is presented.This research was performed while the author was staying at Massachusetts Institute of Technology during the 1988–89 academic year.     

Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems

Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities. J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112. A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1).