Vectors in a box

DOI10.1007/S10107-011-0474-YzbMATH Open1254.90122arXiv0912.0424OpenAlexW2166652474MaRDI QIDQ715080FDOQ715080

Authors: Kevin Buchin, Robin A. Moser, Dömötör Pálvölgyi, Jiří Matoušek 

Publication date: 15 October 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: For an integer d>=1, let tau(d) be the smallest integer with the following property: If v1,v2,...,vt is a sequence of t>=2 vectors in [-1,1]^d with v1+v2+...+vt in [-1,1]^d, then there is a subset S of {1,2,...,t} of indices, 2<=|S|<=tau(d), such that sum_{iin S} vi is in [-1,1]^d. The quantity tau(d) was introduced by Dash, Fukasawa, and G"unl"uk, who showed that tau(2)=2, tau(3)=4, and tau(d)=Omega(2^d), and asked whether tau(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 tau(d) <= d^{d+o(d)}, and based on a construction of Alon and Vu, whose main idea goes back to Hastad, we obtain a lower bound of tau(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 tau(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.

Full work available at URL: https://arxiv.org/abs/0912.0424

Recommendations

• The vector partition problem for convex objective functions.
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Fast integer programming in fixed dimension
• scientific article
• scientific article; zbMATH DE number 6850361

zbMATH Keywords

integer programmingmaster equality polyhedronSteinitz lemma

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Cites Work

• Title not available (Why is that?)
• Some polyhedra related to combinatorial problems
• On the complexity of integer programming
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• On the Size of Weights for Threshold Gates
• On a generalization of the master cyclic group polyhedron
• Non-standard approaches to integer programming
• The master equality polyhedron with multiple rows

Cited In (2)

• The last dozen of years of or research in Czechia and Slovakia
• A colorful Steinitz lemma with application to block-structured integer programs

This page was built for publication: Vectors in a box

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715080)