×

Testing additive integrality gaps. (English) Zbl 1280.90086

Summary: We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.

MSC:

90C10 Integer programming
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
11H06 Lattices and convex bodies (number-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baum S.P., Trotter L.E. Jr: Integer rounding for polymatroid and branching optimization problems. SIAM J. Algebraic Discret. Methods 2(4), 416-425 (1981) · Zbl 0518.90058 · doi:10.1137/0602044
[2] Cook, W.J., Lovász L., Schrijver, A.: A polynomial-time test for total dual integrality in fixed dimension. In: Korte, B.H., Ritter, K. (eds.) Mathematical Programming at Oberwolfach II, vol. 22 of Mathematical Programming Study, pp. 64-69. North-Holland, Amsterdam (1984) · Zbl 0557.90071
[3] Ding G., Feng L., Zang W.: The complexity of recognizing linear systems with certain integrality properties. Math. Program. 114(2), 321-334 (2008) · Zbl 1160.90633 · doi:10.1007/s10107-007-0103-y
[4] Eisenbrand F., Shmonin G.: Parametric integer programming in fixed dimension. Math. Oper. Res. 33(4), 839-850 (2008) · Zbl 1218.90123 · doi:10.1287/moor.1080.0320
[5] Gijswijt D.: Integer decomposition for polyhedra defined by nearly totally unimodular matrices. SIAM J. Discret. Math. 19(3), 798-806 (2005) · Zbl 1113.90101 · doi:10.1137/S089548010343569X
[6] Giles, F.R., Orlin, J.B.: Verifying total dual integrality. Manuscript (1981) · Zbl 0474.90065
[7] Hoşten S., Sturmfels B.: Computing the integer programming gap. Combinatorica 27(3), 367-382 (2007) · Zbl 1136.13016 · doi:10.1007/s00493-007-2057-3
[8] Hoffman, A. J.; Kruskal, J. B.; Kuhn, H. W. (ed.); Tucker, A. W. (ed.), Integral boundary points of convex polyhedra, 223-246 (1956), Princeton, NJ · Zbl 0072.37803
[9] Kannan, R.: Test sets for integer programs, \[{\forall \, \exists}\] sentences. In: Cook, W.J., Seymour, P.D. (eds.) Polyhedral Combinatorics: Proceedings of a DIMACS Workshop held at the Center for Discrete Mathematics and Theoretical Computer Science, 12-16 June 1989, vol. 1 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science American Mathematical Society, pp. 39-47 (1990) · Zbl 0753.11013
[10] Kannan R.: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2), 161-177 (1992) · Zbl 0753.11013 · doi:10.1007/BF01204720
[11] Lenstra H.W. Jr: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538-548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[12] Matoušek, J.: Lectures on Discrete Geometry, vol. 212 of Graduate Texts in Mathematics, Springer, Berlin (2002) · Zbl 0999.52006
[13] Pap J.: Recognizing conic TDI systems is hard. Math. Program. 128(1-2, Ser. A), 43-48 (2011) · Zbl 1218.90226 · doi:10.1007/s10107-009-0294-5
[14] Papadimitriou C.H.: On the complexity of integer programming. J. ACM 28(4), 765-768 (1981) · Zbl 0468.68050 · doi:10.1145/322276.322287
[15] Ramírez Alfonsín J.L.: Complexity of the Frobenius problem. Combinatorica 16(1), 143-147 (1996) · Zbl 0847.68036 · doi:10.1007/BF01300131
[16] Schrijver A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, West Sussex (1986)
[17] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24 of Algorithms and Combinatorics. Springer, Berlin (2003) · Zbl 1041.90001
[18] Seymour P.D.: Decomposition of regular matroids. J. Comb. Theory Ser. B 28(3), 305-359 (1980) · Zbl 0443.05027 · doi:10.1016/0095-8956(80)90075-1
[19] Tipnis S.K., Trotter L.E. Jr: Node-packing problems with integer rounding properties. SIAM J. Discret. Math. 2(3), 407-412 (1989) · Zbl 0681.05056 · doi:10.1137/0402036
[20] Vazirani V.V.: Approximation Algorithms. Springer, Berlin (2001) · Zbl 0999.68546
[21] Veinott A.F. Jr, Dantzig G.B.: Integral extreme points. SIAM Rev. 10(3), 371-372 (1968) · Zbl 0162.33401 · doi:10.1137/1010063
[22] Zambelli G.: Colorings of k-balanced matrices and integer decomposition property of related polyhedra. Oper. Res. Lett. 35(3), 353-356 (2007) · Zbl 1130.05014 · doi:10.1016/j.orl.2006.06.006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.