It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k =0 (bipartite graphs) and for k =1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b -matching.

We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7/3. This allows us to derive a 7/3-approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than$k$vertex-disjoint odd cycles, where$k$is any constant. Previously, polynomial-time algorithms were only known for$k=0$(bipartite graphs) and for$k=1$. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.

A metric graph is a pair (G, d), where G is a graph and d: E(G) → R≥ 0 is a distance function. Let p∈ [1 ,∞] be fixed. An isometric embedding of the metric graph (G, d) in ℓpk=(Rk,dp) is a map ϕ: V(G) → Rk such that dp(ϕ(v) ,ϕ(w)) = d(vw) for all edges vw∈ E(G). The ℓp-dimension of G is the least integer k such that there exists an isometric embedding of (G, d) in ℓpk for all distance functions d such that (G, d) has an isometric embedding in ℓpK for some K. It is easy to show that ℓp-dimension is a minor-monotone property. In this paper, we characterize the minor-closed graph classes C with bounded ℓp-dimension, for p∈ { 2 ,∞}. For p= 2 ,we give a simple proof that C has bounded ℓ2-dimension if and only if C has bounded treewidth. In this sense, the ℓ2-dimension of a graph is ‘tied’ to its treewidth. For p= ∞, the situation is completely different. Our main result states that a minor-closed class C has bounded ℓ∞-dimension if and only if C excludes a graph obtained by joining copies of K4 using the 2-sum operation, or excludes a Möbius ladder with one ‘horizontal edge’ removed.

Consider the family of graphs without k node-disjoint odd cycles, where k is a constant. Determining the complexity of the stable set problem for such graphs G is a long-standing problem. We give a polynomial-time algorithm for the case that G can be further embedded in a (possibly nonorientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface (Kawarabayashi & Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost nonnegative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case.

The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree G = (V, E) with n = |V| nodes, an additional set of edges L called links and a cost vector . The goal is to choose a minimum cost subset S ⊆ L such that G = (V, E ∪ S) is 2-edgeconnected. In the unweighted case, that is, when we have cℓ = 1 for all ℓ ∊ L, the problem is called the tree augmentation problem (TAP). Both problems are known to be APX-hard, and the best known approximation factors are 2 for WTAP by (Frederickson and JáJá, ’81) and for TAP due to (Kortsarz and Nutov, TALG ’16). Adjashvili (SODA ’17) recently presented an ≈ 1.96418 + ε-approximation algorithm for WTAP for the case where all link costs are bounded by a constant. This is the first approximation with a better guarantee than 2 that does not require restrictions on the structure of the tree or the links. In this paper, we improve Adjiashvili's approximation to a + ε-approximation for WTAP under the bounded cost assumption. We achieve this by introducing a strong LP that combines {0, ½}-Chvátal-Gomory cuts for the standard LP for the problem with bundle constraints from Adjiashvili. We show that our LP can be solved efficiently and that it is exact for some instances that arise at the core of Adjiashvili's approach. This results in the improved performance guarantee of + ε, which is asymptotically on par with the result by Kortsarz and Nutov. Our result also is the best-known LP-relative approximation algorithm for TAP.

Let $W_t$ denote the wheel on t+1 vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k \geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as a minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. For the min-knapsack cover problem, our main result can be stated formally as follows: for any ∊ > 0, there is a (1/∊)O(1)nO(log n)-size LP relaxation with an integrality gap of at most 2 + ∊, where n is the number of items. Prior to this work, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our construction is inspired by a connection between extended formulations and monotone circuit complexity via Karchmer-Wigderson games. In particular, our LP is based on O (log2 n)-depth monotone circuits with fan-in 2 for evaluating weighted threshold functions with n inputs, as constructed by Beimel and Weinreb. We believe that a further understanding of this connection may lead to more positive results complementing the numerous lower bounds recently proved for extended formulations.

Let $G$ be a graph and $p \in [1, \infty]$. The parameter $f_p(G)$ is the least integer $k$ such that for all $m$ and all vectors $(r_v)_{v \in V(G)} \subseteq \mathbb{R}^m$, there exist vectors $(q_v)_{v \in V(G)} \subseteq \mathbb{R}^k$ satisfying $\|r_v-r_w\|_p=\|q_v-q_w\|_p$ for all $vw\in E(G).$ It is easy to check that $f_p(G)$ is always finite and that it is minor monotone. By the graph minor theorem of Robertson and Seymour [J. Combin. Theory Ser. B, 92 (2004), pp. 325--357], there are a finite number of excluded minors for the property $f_p(G) \leq k$. In this paper, we determine the complete set of excluded minors for $f_\infty(G) \leq 2$. The two excluded minors are the wheel on five vertices and the graph obtained by gluing two copies of $K_4$ along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for $f_1(G) \leq 2$. In addition, we give a family of examples that show that $f_\infty$ is unbounded on the class of planar graphs and $f_\infty$ is not bounded as a function of tree-width.

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef [Math. Program, 53 (1992), pp. 147--172]. We show how to derive each of the results from the other. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2.

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [30], [31] proved that the problem is NP-hard to approximate within a factor 2 - ε, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best in approximability result for the problem is due to Dinur and Safra [16], [17]: vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor of 2 - ε has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomially many inequalities.

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via LPs (more precisely, linear extended formulations), in two distinct models. In the uniform model, the constraints of the LP are not allowed to depend on the input graph, which should be encoded solely in the objective function. There we prove a super-polynomial lower bound with overwhelming probability for every LP that is exact for a randomly selected set of instances with a natural distribution. In the non-uniform model, the constraints of the LP may depend on the input graph, but we allow weights on the vertices. The input graph is sampled according to the Erdös-Renyi model. There we obtain upper and lower bounds holding with high probability for various ranges of p. We obtain a super-polynomial lower bound all the way from essentially p = polylog(n) / n to p = 1 / log n. Our upper bound is close as there is only an essentially quadratic gap in the exponent, which also exists in the worst case model. Finally, we state a conjecture to close the gap both in the average-case and worst-case models.

The order polytopes we consider here are the linear order polytope, the interval order polytope, the semiorder polytope and the partial order polytope. Among their known facet defining inequalities (FDIs), many have their coefficients in {-1, 0, 1}. We consider the problem of finding all of these particular FDIs. The problem is easy for the partial order polytope. For the interval order polytope, we prove that the solution consists of the so-called io-clique inequalities of Müller and Schulz [5]. We present a characterisation of the {-1, 0, 1}-FDIs for the semiorder polytope. The similar problem for the linear order polytope remains open and seems harder to solve because of the large variety of known examples of FDIs which fall in this class.

We develop a framework for proving approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that quadratic approximations for CLIQUE require linear programs of exponential size. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem) Moreover, we establish a similar result for approximations of semi definite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov's rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjoint ness matrix.

We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set $P$, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of $P$. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical.

Abstract We consider combinatorial optimization problems arising in radiation therapy. Given a matrix I with non‐negative integer entries, we seek a decomposition of I as a weighted sum of binary matrices having the consecutive ones property, such that the total sum of the coefficients is minimized. The coefficients are restricted to be non‐negative integers. Here, we investigate variants of the problem with additional constraints on the matrices used in the decomposition. Constraints appearing in the application include the interleaf motion and interleaf distance constraints. The former constraint was previously studied by Baatar et al. [Discr Appl Math 152 (2005), 6–34] and Kalinowski [Discr Appl Math 152 (2005), 52–88]. The latter constraint was independently considered by Kumar [Working paper (2007)] in the case where coefficients of the decomposition are not restricted to be integers. For both constraints, we prove that finding an optimal decomposition reduces to finding a maximum value potential in an auxiliary network with integer arc lengths and no negative length cycle. This allows us to simplify and unify the previous approaches. Moreover, we give an O ( MN + K M ) algorithm to solve the problem under the interleaf distance constraint, where M and N , respectively, denote the number of rows and columns of the matrix I and K is the number of matrices used in the decomposition. We also give an O ( MN log M + K M ) algorithm for solving the problem under the interleaf motion constraint and hence improve on previous results. Finally, we show the problem can still be solved in O ( MN log M + K M ) time when both constraints are considered simultaneously. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S by comparing a minimum number of pairs in T. Special cases include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing $ITLB+o(ITLB)+O(n)$ comparisons in the worst case. Here, n denotes the size of the ground sets, and $ITLB$ denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information-theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao [SIAM J. Comput., 18 (1989), pp. 679–689]. We base our analysis on the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound.

Only recently Goyal, Olver, and Shepherd [Proc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms, 24 (1997), pp. 287–309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPN, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry.

Proceedings of the 41st annual ACM Symposium on Theory of Computing STOC 2009, Bethesda, Maryland, 31 mai–2 juin 2009

We find new facet‐defining inequalities for the linear ordering polytope generalizing the well‐known Möbius ladder inequalities. Our starting point is to observe that the natural derivation of the Möbius ladder inequalities as $\{0,\frac{1}{2}\}$‐cuts produces triangulations of the Möbius band and of the corresponding (closed) surface, the projective plane. In that sense, Möbius ladder inequalities have the same “shape” as the projective plane. Inspired by the classification of surfaces, a classic result in topology, we prove that a surface has facet‐defining $\{0,\frac{1}{2}\}$‐cuts of the same “shape” if and only if it is nonorientable.

This paper presents the study of the properties of graph colorings that minimize the quantity of color information with respect to a given probability distribution on the vertices. The minimum entropy of any coloring is the chromatic entropy. Applications of the chromatic entropy are found in coding with side information and digital image partition coding. We show that minimum entropy colorings are hard to compute even if a minimum cardinality coloring is given, the distribution is uniform, and the graph is planar. We also consider the minimum number of colors in a minimum entropy coloring, and show that this number can be arbitrarily larger than the chromatic number, even for restricted families of uniformly weighted graphs.

The weak order polytopes are studied in Gurgel and Wakabayashi [ Discrete Math., 175 (1997), pp. 163--172], Gurgel and Wakabayashi [The Complete Pre-Order Polytope: Facets and Separation Problem, manuscript, 1996], and Fiorini and Fishburn [Weak order polytopes, submitted]. We make use of their natural, affine projection onto the partition polytopes to determine several new families of facets for them. It turns out that not all facets of partition polytopes are lifted into facets of weak order polytopes. We settle the cases of all facet-defining inequalities established for partition polytopes by Grötschel and Wakabayashi [Math. Programming, 47 (1990), pp. 367--387]. Our method, although rather simple, allows us to establish general families of facets which contain two particular cases previously requiring long proofs.