Name
Abstract | ||
|---|---|---|
For an integer d ≥ 1, let τ(d) be the smallest integer with the following property: if v 1, v 2, . . . , v t is a sequence of t ≥ 2 vectors in [−1, 1] d with \({{\bf v}_1+{\bf v}_2+\cdots+{\bf v}_t \in [-1,1]^d}\) , then there is a set \({S\subseteq \{1,2,\ldots,t\}}\) of indices, 2 ≤ |S| ≤ τ(d), such that \({\sum_{i \in S}{\bf v}_i \in [-1,1]^d}\) . The quantity τ(d) was introduced by Dash, Fukasawa, and Günlük, who showed that τ(2) = 2, τ(3) = 4, and τ(d) = Ω(2 d ), and asked whether τ(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of τ(d) ≤ d d+o(d), and based on a construction of Alon and Vũ, whose main idea goes back to Håstad, we obtain a lower bound of τ(d) ≥ d d/2-o(d). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al. which is a “universal” polyhedron encoding valid cutting planes for integer programs (this line of research was started by Gomory in the late 1960s). In particular, the upper bound on τ(d) implies a pseudo-polynomial running time for an algorithm of Dash et al. for integer programming with a fixed number of constraints. The algorithm consists in solving a linear program, and it provides an alternative to a 1981 dynamic programming algorithm of Papadimitriou. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10107-011-0474-y | Math. Program. |
Keywords | Field | DocType |
upper bound,lower bound,integer programming,dynamic programming algorithm,cutting plane,linear program | Integer,Discrete mathematics,Combinatorics,Mathematical optimization,Upper and lower bounds,Polyhedron,Integer programming,Mathematics | Journal |
Volume | Issue | ISSN |
135 | 1-2 | 1436-4646 |
Citations | PageRank | References |
2 | 0.41 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kevin Buchin | 1 | 521 | 52.55 |
| Jirí Matousek | 2 | 763 | 76.77 |
| Robin A. Moser | 3 | 240 | 12.51 |
| Dömötör Pálvölgyi | 4 | 202 | 29.14 |