Search

We present a dynamical systems approach for geometric matchings in an ensemble of polytopes along rigid-body motions. Each polytope can be characterized by a vertex set and edge or faces determined by vertices, and polygons and simplexes correspond to a polytope. For a geometric matching, we propose a system of dynamical system for the evolution of centroids and rotations of polytopes to match the vertices under rigid-body motions which can be decomposed as a composition of translation and rotations. Our proposed dynamical system acts on the product space $({\mathbb R}^d \times SO(d))^N$. The evolution of centroids can be described by the coupled linear second-order dynamical system with diffusive linear couplings, whereas rotations for the matching of vertices are described by the Lohe matrix model on $SO(d)^N$. In particular, the Lohe matrix model has been derived from some set of physical principles compared to previous works in which the Lohe matrix model were employed as a system dynamics. This is a contrasted difference between earlier works on the Lohe matrix model which has been adopted a priori for an aggregate modeling of matrices. We also provide an analytical result leading to the complete shape matchings for an ensemble of congruent polytopes, and several numerical examples to illustrate analytical results visually.

We completely characterize the faces of the root polytope $\tilde Q_G = \text{conv}\{\mathbf 0, \mathbf e_i - \mathbf e_j\: (i,j) \in E(G)\}$ combinatorially. Our results specialize to state of the art results in a straightforward way., Comment: 18 pages, 8 figures. v2: corrected proof of lemma 3.19

Given a polytope $\mathcal P$, an interior point ${x}\in\mathcal P$, and a direction ${d}\in\mathbb{R}^n$, the projection of ${x}$ along ${d}$ asks to find the maximum step length $t^*$ such that $...

For any marked poset we define a continuous family of polytopes, parametrized by a hypercube, generalizing the notions of marked order and marked chain polytopes. By providing transfer maps, we show that the vertices of the hypercube parametrize an Ehrhart equivalent family of lattice polytopes. The combinatorial type of the polytopes is constant when the parameters vary in the relative interior of each face of the hypercube. Moreover, with the help of a subdivision arising from a tropical hyperplane arrangement associated to the marked poset, we give an explicit description of the vertices of the polytope for generic parameters., Comment: 31 pages, 5 figures

In this paper we introduce a natural model for the realization space of a polytope up to projective equivalence which we call the slack realization space of the polytope. The model arises from the positive part of an algebraic variety determined by the slack ideal of the polytope. This is a saturated determinantal ideal that encodes the combinatorics of the polytope. We also derive a new model of the realization space of a polytope from the positive part of the variety of a related ideal. The slack ideal offers an effective computational framework for several classical questions about polytopes such as rational realizability, non-prescribability of faces, and realizability of combinatorial polytopes., Comment: The original arXiv submission of this paper has now been split into two parts; this paper describing the slack realization space of a polytope and applications of the slack ideal, and a second paper focussing on toric slack ideals and projective uniqueness

In this paper, we consider a general decomposition of any convex polytope $P\subset\mathbb{R}^n$ into a set of subpolytopes $\Omega_i$ and develop methods for approximating a definite integral of a...

Gelfand-Tsetlin polytopes are prominent objects in algebraic combinatorics. The number of integer points of the Gelfand-Tsetlin polytope $\mathrm{GT}(\lambda)$ is equal to the dimension of the corresponding irreducible representation of $GL(n)$. It is well-known that the Gelfand-Tsetlin polytope is a marked order polytope; the authors have recently shown it to be a flow polytope. In this paper, we draw corollaries from this result and establish a general theory connecting marked order polytopes and flow polytopes., Comment: 18 pages, 10 figures

We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from the interior of polytopes in ℝn specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold equipped with the metric induced by the Hessian of a convex function; each step is the solution of an ordinary differential equation (ODE). The resulting sampling algorithm for polytopes mixes in O*(mn3/4) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes. Our analysis of the geodesic walk for general Hessian manifolds does not assume positive curvature and might be of independent interest.

In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given any query point $q \in \mathbb{R}^d$, it is possible to determine efficiently whether $q \in K$. We consider this problem in an approximate setting. Given an approximation parameter $\varepsilon$, the query can be answered either way if the distance from $q$ to $K$'s boundary is at most $\varepsilon$ times $K$'s diameter. We assume that the dimension $d$ is fixed, and $K$ is presented as the intersection of $n$ halfspaces. Previous solutions to approximate polytope membership were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former is optimal in the worst-case with respect to space, and the latter is optimal with respect to query time. We present four main results. First, we show how to combine the two above techniques to obtain a simple space-time trade-off. Second, we present an algorithm that dramatically improves this trade-off. In particular, for any constant $\alpha \ge 4$, this data structure achieves query time $O(1/\varepsilon^{(d-1)/\alpha})$ and space roughly $O(1/\varepsilon^{(d-1)(1 - O(\log \alpha)/\alpha)})$. We do not know whether this space bound is tight, but our third result shows that there is a convex body such that our algorithm achieves a space of at least $\Omega( 1/\varepsilon^{(d-1)(1-O(\sqrt{\alpha})/\alpha} )$. Our fourth result shows that it is possible to reduce approximate Euclidean nearest neighbor searching to approximate polytope membership queries. Combined with the above results, this provides significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching in $\mathbb{R}^d$., Comment: Preliminary results of this paper appeared in "Approximate Polytope Membership Queries", in Proc. ACM Sympos. Theory Comput. (STOC), 2011, 579-586 and "Polytope Approximation and the Mahler Volume", in Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA), 2012, 29-42

We consider the multilinear polytope defined as the convex hull of the set of binary points $z$ satisfying a collection of equations of the form $z_e = \prod_{v \in e} {z_v}$, $e \in E$, where $E$ denotes a family of subsets of $\{1, \ldots , n\}$ of cardinality at least two. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as $0-1$ polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the multilinear polytope in conjunction with the acyclicity degree of the underlying hypergraph. We provide explicit characterizations of the multilinear polytopes corresponding to Berge-acylic and $\gamma$-acyclic hypergraphs. As the multilinear polytope for $\gamma$-acyclic hypergraphs may contain exponentially many facets in general, we present a strongly polynomial-time algorithm to solve the separation problem, implying polynomial solvability of the corresponding class of $0-1$ polynomial optimization prob...

We extend the Barvinok-Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger Arithmetic. We also give an application to the k-Frobenius problem.

We define the excess degree $\xi(P)$ of a $d$-polytope $P$ as $2f_1-df_0$, where $f_0$ and $f_1$ denote the number of vertices and edges, respectively. This parameter measures how much $P$ deviates from being simple. It turns out that the excess degree of a $d$-polytope does not take every natural number: the smallest possible values are $0$ and $d-2$, and the value $d-1$ only occurs when $d=3$ or 5. On the other hand, for fixed $d$, the number of values not taken by the excess degree is finite if $d$ is odd, and the number of even values not taken by the excess degree is finite if $d$ is even. The excess degree is then applied in three different settings. It is used to show that polytopes with small excess (i.e. $\xi(P), Comment: 36 pages, 3 figures

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arising in combinatorial settings. Our first contribution is proving that f(0)(P)f(d-1) (P)

In this paper we exhibit the first infinite family of abstract 4-polytopes whose connection groups are not string C-groups. In addition we present some new results on methods of representing the connection group of a polytope in terms of its automorphism group. We also analyze the connection groups of all of the pyramids over the finite regular 3-tori.

The paper is devoted to the normal tiling whose tiles are uniformly bounded and general connected closed sets instead of being restricted to polytopes or convex sets. We estimate the number of neighbors of a tile in the normal tiling and develop various novel techniques to derive lower and upper bounds. The bounds for lattice tilings are shown to be optimal.

Given a group-based Markov model on a tree, one can compute the vertex representation of a polytope describing a toric variety associated with the algebraic statistical model. In the cases of ${\mathbb Z}_2$ and ${\mathbb Z}_2\times{\mathbb Z}_2$, these polytopes have applications in the field of phylogenetics. We provide a half-space representation of the polytope for the $m$-claw tree where $G={\mathbb Z}_2\times{\mathbb Z}_2$. This choice of group corresponds to the Kimura-3 model of evolution.

A graph is called $t$-perfect if its stable set polytope is fully described by non-negativity, edge and odd-cycle constraints. We characterise $P_5$-free $t$-perfect graphs in terms of forbidden $t$-minors. Moreover, we show that $P_5$-free $t$-perfect graphs can always be coloured with three colours, and that they can be recognised in polynomial time., Work of Holm et al of which we were not aware made some parts unnecessary. This concerns mostly the section on near-bipartite graphs that is much shorter now

We study the simultaneous convexification of graphs of bilinear functions $g^k({x};{y}) = {y}^{\intercal} A^k {x}$ over ${x} \in \ensuremath{\Xi} = \{ {x} \in [0,1]^n \, | \, E{x} \geq {f} \}$ and ${y} \in \Delta_m = \{ {y} \in {R}_+^{m} \, | \, {1^{\intercal}y} \leq 1 \}$. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied to derive convex and concave envelopes of certain bilinear functions, to study unary expansions of integer variables in mixed integer bilinear sets, and to obtain convex hulls of sets with complementarity constraints. Exploiting the structure of $\Xi$, the procedure naturally yields stronger linearizations for bilinear terms in a variety of practical settings. In particular, we demonstrate the effectiveness of the approach by strengthening the traditional dual formulation of network interdiction problems and report encouraging preliminary numerical results.

We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all \ ultrametrics. The ${\rm CAT}(0)$-metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen-Provan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric behave better. They exhibit properties desirable for geometric statistics, such as geodesics of small depth., Comment: 21 pages, 5 figures; Theorem 13 is now proved in all dimensions

Reaction networks taken with mass-action kinetics arise in many settings, from epidemiology to population biology to systems of chemical reactions. Bistable reaction networks are posited to underlie biochemical switches, which motivates the following question: which reaction networks have the capacity for multiple steady states? Mathematically, this asks: among certain parametrized families of polynomial systems, which admit multiple positive roots? No complete answer is known. This work analyzes the smallest networks, those with only a few chemical species or reactions. For these "smallest" networks, we completely answer the question of multistationarity and, in some cases, multistability too, thereby extending related work of Boros. Our results highlight the role played by the Newton polytope of a network (the convex hull of the reactant vectors). Also, our work is motivated by recent results that explain how a given network's capacity for multistationarity arises from that of certain related networks which are typically smaller. Hence, we are interested in classifying small multistationary networks, and our work forms a first step in this direction., 27 pages, small corrections, added citations, new definition of "arrow diagram"

We prove that universal second-order rigidity implies universal prestress stability and that triangulated convex polytopes in 3-space (with holes appropriately positioned) are prestress stable.

We show that the problem of deciding membership in the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group is in NP and coNP. This is the first non-trivial result on the computational complexity of this problem, which naively amounts to a quadratically-constrained program. Our result applies in particular to the Kronecker polytopes, and therefore to the problem of deciding positivity of the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard in general [Ikenmeyer, Mulmuley and Walter, arXiv:1507.02955]. We discuss the consequences of our work in the context of complexity theory and the quantum marginal problem., 20 pages

We study upper bounds on the number of lattice points for convex bodies having their centroid at the origin. For the family of simplices as well as in the planar case we obtain best possible results. For arbitrary convex bodies we provide an upper bound, which extends the centrally symmetric case and which, in particular, shows that the centroid assumption is indeed much more restrictive than an assumption on the number of interior lattice points even for the class of lattice polytopes., 12 pages

Common approaches to solving a robust optimization problem decompose the problem into a master problem (MP) and adversarial problems (APs). The MP contains the original robust constraints, written, however, only for nite numbers of scenarios. Additional scenarios are generated on the y by solving the APs. We consider in this work the budgeted uncertainty polytope from Bertsimas and Sim, widely used in the literature, and propose new dynamic programming algorithms to solve the APs that are based on the maximum number of deviations allowed and on the size of the deviations. Our algorithms can be applied to robust constraints that occur in various applications such as lot-sizing, the traveling salesman problem with time windows, scheduling problems, and inventory routing problems, among many others. We show how the simple version of the algorithms leads to a fully polynomial time approximation scheme when the deterministic problem is convex. We assess numerically our approach on a lot-sizing problem, showing a comparison with the classical mixed integer linear programming reformulation of the AP.

In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been a focus of a long line of work. For a given set of $d$ linear queries $A$ over a database $x \in \mathbb{R}^N$, we seek to find the differentially private mechanism that has the minimum mean squared error relative to the true answer $Ax$. For pure differential privacy, Hart and Talwar and Bhaskara et al. give an $O(\log^2 d)$ approximation to the optimal mechanism. Our first contribution is to give an $O(\log^2 d)$ approximation guarantee for the case of $(\varepsilon,\delta)$-approximate differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers and runs in time polynomial in $d$ and $N$. The mechanism is based on a recursive construction of a “small” enclosing ellipsoid of the sensitivity polytope $AB_1^N$, where $B_1^N$ denotes the $N$-dimensional $\ell_1$ b...

We perform a convergence analysis for discretizations of Helmholtz scattering and resonance problems obtained by Hardy space infinite elements. Superalgebraic convergence rates with respect to the number of Hardy space degrees of freedom are achieved. We consider spheres and piecewise polytopes as transparent boundaries. The analysis is based on a G\aa rding-type inequality and standard operator theoretical results. While the obtained results are related to those for the radial perfectly matched layer method, different techniques are used in the analysis.

In this paper we show that the pipe dream complex associated to the permutation 1n(n-1)...2 can be geometrically realized as a triangulation of the vertex figure of a root polytope. Leading up to this result we show that the Grothendieck polynomial specializes to the h-polynomial of the corresponding pipe dream complex, which in certain cases equals the h-polynomial of canonical triangulations of root (and flow) polytopes, which in turn equals a specialization of the reduced form of a monomial in the subdivision algebra of root (and flow) polytopes. Thus, we connect Grothendieck polynomials to reduced forms in subdivision algebras and root (and flow) polytopes. We also show that root polytopes can be seen as projections of flow polytopes, explaining that these families of polytopes possess the same subdivision algebra., Comment: 11 pages, 5 figures

We generalize the recent invariant polytope algorithm for computing the joint spectral radius and extend it to a wider class of matrix sets. This, in particular, makes the algorithm applicable to sets of matrices that have finitely many spectrum maximizing products. A criterion of convergence of the algorithm is proved. As an application we solve two challenging computational open problems. First we find the regularity of the Butterfly subdivision scheme for various parameters $\omega$. In the “most regular” case $\omega = \frac{1}{16}$, we prove that the limit function has Holder exponent 2 and its derivative is “almost Lipschitz” with logarithmic factor 2. Second we compute the Holder exponent of Daubechies wavelets of high order.

Given an $\mathcal{H}$-polytope $P$ and a $\mathcal{V}$-polytope $Q$, the decision problem whether $P$ is contained in $Q$ is co-NP-complete. This hardness remains if $P$ is restricted to be a standard cube and $Q$ is restricted to be the affine image of a cross polytope. While this hardness classification by Freund and Orlin dates back to 1985, for general dimension there seems to be only limited progress on that problem so far. Based on a formulation of the problem in terms of a bilinear feasibility problem, we study sum of squares certificates to decide the containment problem. These certificates can be computed by a semidefinite hierarchy. As a main result, we show that under mild and explicitly known preconditions the semidefinite hierarchy converges in finitely many steps. In particular, if $P$ is contained in a large $\mathcal{V}$-polytope $Q$ (in a well-defined sense), then containment is certified by the first step of the hierarchy., 16 pages, 1 figure; to appear in SIAM J. Discrete Math

Border bases arise as a canonical generalization of Grobner bases, using order ideals instead of term orderings. We provide a polyhedral characterization of all order ideals (and hence all border bases) that are supported by a zero-dimensional ideal: order ideals that support a border basis correspond one-to-one to integral points of the order ideal polytope. In particular, we establish a crucial connection between the ideal and its combinatorial structure. Based on this characterization we also provide an adaptation of the border basis algorithm of Kehrein and Kreuzer [J. Pure Appl. Algebra, 205 (2006), pp. 279--295] to allow for computing border bases for arbitrary order ideals, given implicitly via maximizing a preference on monomials (variable selection problem), independent of term orderings. The algorithm requires the same size of resources as the border basis algorithm except for some minor overhead. We also show that the underlying variable selection problem of finding an order ideal that supports...

Many interesting properties of polynomials are closely related to the geometry of their Newton polytopes. In this article, we analyze the coercivity on $\mathbb{R}^n$ of multivariate polynomials $f\in \mathbb{R}[x]$ in terms of their so-called Newton polytopes at infinity. In fact, we introduce the broad class of so-called gem regular polynomials and characterize their coercivity via conditions solely containing information about the geometry of the vertex set of the Newton polytope at infinity, as well as sign conditions on the corresponding polynomial coefficients. For all other polynomials, the so-called gem irregular polynomials, we introduce sufficient conditions for coercivity based on those from the regular case. For some special cases of gem irregular polynomials, we establish necessary conditions for coercivity, too. Using our techniques, the problem of deciding the coercivity of a polynomial can often be studied based on its Newton polytope at infinity. We relate our results to the context of po...

We define a statistical measure of the typical size of short words in a linear code over a finite field. We prove that the dual toric codes coming from polytopes of degree one are characterized, among all dual toric codes, by being extremal with respect to this measure. We also give a geometric interpretation of the minimum distance of dual toric codes and characterize its extremal values. Finally, we obtain formulas for the parameters of both primal and dual toric codes associated to polytopes of degree one., Comment: 13 pages

We derive upper and lower bounds on the gradients of Wachspress coordinates defined over any simple convex d-dimensional polytope P. The bounds are in terms of a single geometric quantity h_*, which denotes the minimum distance between a vertex of P and any hyperplane containing a non-incident face. We prove that the upper bound is sharp for d=2 and analyze the bounds in the special cases of hypercubes and simplices. Additionally, we provide an implementation of the Wachspress coordinates on convex polyhedra using Matlab and employ them in a 3D finite element solution of the Poisson equation on a non-trivial polyhedral mesh. As expected from the upper bound derivation, the H^1-norm of the error in the method converges at a linear rate with respect to the size of the mesh elements., 18 pages, to appear in SINUM

The quadratic traveling salesman problem asks for a tour of minimal total costs where the costs are associated with each of two arcs that are traversed in succession. This structure arises, e.g., if the succession of two arcs represents loading processes in transport networks or a switch between different technologies in communication networks. Based on an integer program with quadratic objective function we present a linearized integer programming formulation and study the corresponding polyhedral structure of the asymmetric quadratic traveling salesman problem (AQTSP), where the costs may depend on the direction of traversal. The constructive approach that is used to establish the dimension of the underlying polytope allows us to prove the facetness of several classes of valid inequalities. Some of them are related to the Boolean quadric polytope. Two new classes are developed that exclude conflicting configurations. Among these the first one is separable in polynomial time, and the separation problem f...

We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was ...

The diameter of the stable matching (stable marriage) polytope is bounded from above by $\left\lfloor\frac{n}{2}\right\rfloor$, where $n$ is the number of men (or women) involved in the matching; this bound is attainable.

We study the degree of non-homogeneous lattice ideals over arbitrary fields, and give formulae to compute the degree in terms of the torsion of certain factor groups of Z^s and in terms of relative volumes of lattice polytopes. We also study primary decompositions of lattice ideals over an arbitrary field using the Eisenbud-Sturmfels theory of binomial ideals over algebraically closed fields. We then use these results to study certain families of integer matrices (PCB, GPCB, CB, GCB matrices) and the algebra of their corresponding matrix ideals. In particular, the family of generalized positive critical binomial matrices (GPCB matrices) is shown to be closed under transposition, and previous results for PCB ideals are extended to GPCB ideals. Then, more particularly, we give some applications to the theory of 1-dimensional binomial ideals. If G is a connected graph, we show as a further application that the order of its sandpile group is the degree of the Laplacian ideal and the degree of the toppling ideal. We also use our earlier results to give a structure theorem for graded lattice ideals of dimension 1 in 3 variables and for homogeneous lattices in Z^3 in terms of critical binomial ideals (CB ideals) and critical binomial matrices, respectively, thus complementing a well-known theorem of Herzog on the toric ideal of a monomial space curve., Comment: SIAM J. Discrete Math., to appear

We study weighted clustering problems in Minkowski spaces under balancing constraints with a view towards separation properties. First, we introduce the gravity polytopes and more general gravity bodies that encode all feasible clusterings and indicate how they can be utilized to develop efficient approximation algorithms for quite general, hard to compute objective functions. Then we show that their extreme points correspond to strongly feasible power diagrams, certain specific cell complexes, whose defining polyhedra contain the clusters, respectively. Further, we characterize strongly feasible centroidal power diagrams in terms of the local optima of some ellipsoidal function over the gravity polytope. The global optima can also be characterized in terms of the separation properties of the corresponding clusterings.

Facility location, arising in a rich variety of applications, has been studied extensively in the fields of operations research and computer science. In this paper we consider the classical uncapacitated facility location problem and its "prize-collecting" variant introduced by Ba¨ iou and Barahona, and we show that the linear systems associated with these problems are totally dual integral if and only if the input graphs do not contain a certain type of odd cycles. As corollaries, we get structural characterizations of two min-max relations on facility location. Our results strengthen the integrality theorems on facility location polytopes proved by Ba¨ iou and Barahona; our proofs lead to combinatorial polynomial-time algorithms for the facility location problems that we consider.

Using the correspondence between abstract regular polytopes and string C-groups, in a recent paper [M. E. Fernandes, D. Leemans, and M. Mixer, J. Combin. Theory Ser. A, 119 (2012), pp. 42–56], we constructed an abstract regular polytope of rank r, for each $r \geq 3$, with automorphism group isomorphic to $A_{2r+3}$ when r is odd, and $A_{2r+1}$ when r is even. In this paper, the remaining cases are completed. It is shown that every group $A_n$, with n sufficiently large, acts on at least one abstract regular polytope of rank $\lfloor\frac{n-1}{2}\rfloor$. We conjecture that this is the highest possible rank for $n\geq 12$.

Given a preference system $(G, \prec)$ and an integral weight function defined on the edge set of $G$ (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of $(G, \prec)$ with maximum total weight. In this paper we study this $NP$-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of $(G, \prec)$ is totally dual integral if and only if this polytope is integral if and only if $(G, \prec)$ has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Kiraly and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.

In the last years, several integer linear programming (ILP) formulations for the crossing number problem arose. While they all contain a common conceptual core, the properties of the corresponding polytopes have never been investigated. In this paper, we formally establish the crossing number polytope and show several facet-defining constraint classes.

We study a prize-collecting version of the uncapacitated facility location problem and of the $p$-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the $p$-median and facility location problems studied in this paper.

We study the facial structure of the alldifferent system, i.e., the polytope (namely, $P_{I}$) defined as the convex hull of integer vectors satisfying such a system. We derive classes of facets for $P_{I}$ by examining induced subgraphs of the associated constraint graph. Some of these graphic structures (for example, odd holes, webs, etc.) are well known to induce facets of the set packing polytope, namely, $P_{S}$. This is a rather surprising result, given that $P_{S}$ is defined in terms of binary variables whereas $P_{I}$ is defined in terms of integer variables receiving values from a discrete domain. As a consequence, the resulting facet-defining inequalities are different for $P_{I}$ and $P_{S}$. Furthermore, we show that the families of facet-defining graphic structures for $P_{I}$ and $P_{S}$ do not coincide as we exhibit such a structure yielding facets for $P_{I}$ but not for $P_{S}$. We also prove that the facets of $P_{I}$ come in pairs of the form $(\alpha x\geq\beta,\alpha x\leq\delta)$ and show that the separation of the first implies that of the second (and vice versa). In addition, we provide the complete linear description of $P_{I}$ when the constraint graph of the alldifferent system is of degree 2.

The feasible set $M$ in generalized semi-infinite programming (GSIP) need not be closed. Under the so-called symmetric Mangasarian-Fromovitz constraint qualification (Sym-MFCQ), its closure $\overline{M}$ can be described by means of infinitely many inequality constraints of maximum type. In this paper we introduce the nonsmooth symmetric reduction ansatz (NSRA). Under NSRA we prove that the set $\overline{M}$ can locally be described as the feasible set of a so-called disjunctive optimization problem defined by finitely many inequality constraints of maximum type. This also shows the appearance of re-entrant corners in $\overline{M}$. Under Sym-MFCQ all local minimizers of GSIP are KKT points for GSIP. We show that NSRA is generic and stable at all KKT points and that all KKT points are nondegenerate. The concept of (nondegenerate) KKT points as well as a corresponding GSIP-index are introduced in this paper. In particular, a nondegenerate KKT-point is a local minimizer if and only if its GSIP-index vanishes. At local minimizers NSRA coincides with the symmetric reduction ansatz (SRA) as introduced in [H. Gunzel, H. Th. Jongen, and O. Stein, Optim. Lett., 2 (2008), pp. 415-424]. In comparison with SRA, the main new issue in NSRA is the following: At KKT points different from local minimizers, the Lagrange polytope at the lower level generically need not be a singleton anymore. In fact, it will be a full-dimensional simplex. This fact is crucial to provide the above-mentioned local reduction to a disjunctive optimization problem. Finally, we establish a local cell-attachment theorem which will be the basis for the development of a global critical point theory for GSIP.

We provide an upper bound to the number of graph homomorphisms from $G$ to $H$, where $H$ is a fixed graph with certain properties, and $G$ varies over all $N$-vertex, $d$-regular graphs. This result generalizes a recently resolved conjecture of Alon and Kahn on the number of independent sets. We build on the work of Galvin and Tetali, who studied the number of graph homomorphisms from $G$ to $H$ when $H$ is bipartite. We also apply our techniques to graph colorings and stable set polytopes., 22 pages. To appear in SIAM J. Discrete Math

Discrete tomography is concerned with the retrieval of finite point sets in some $\mathbbm{R}^d$ from their X-rays in a given number $m$ of directions $u_1,\ldots, u_m$. In the present paper we focus on uniqueness issues. The first remark gives a uniform treatment and extension of known uniqueness results. In particular, we introduce the concept of $J$-additivity and give conditions when a subset $J$ of possible positions is already determined by the given data. As a by-product, we settle a conjecture of Brunetti and Daurat on planar lattice convex sets. Remark 2 resolves a problem of Kuba posed in 1997 on the uniqueness in the case $d=m=3$ with $u_1,u_2,u_3$ being the standard unit vectors. Remark 3 determines the computational complexity of finding a smallest set $J$ of positions whose disclosure yields uniqueness. As a corollary, we obtain a hardness result for $0$-$1$-polytopes.

Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84-106] introduced the class of Eisenberg-Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani; whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.

In this paper we consider finite families ${\cal F}$ of real $n\!\times\!n$ matrices. In particular, we focus on the computation of the joint spectral radius $\rho({\cal F})$ via the detection of an extremal norm in the class of complex polytope norms, whose unit balls are balanced complex polytopes with a finite essential system of vertices. Such a finiteness property is very useful in view of the construction of efficient computational algorithms. More precisely, we improve the results obtained in our previous paper [N. Guglielmi, F. Wirth, and M. Zennaro, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 721-743], where we gave some conditions on the family ${\cal F}$ which are sufficient to guarantee the existence of an extremal complex polytope norm. Unfortunately, they exclude unnecessarily many interesting cases of real families. Therefore, here we relax the conditions given in our previous paper in order to provide a more satisfactory treatment of the real case.