Abstract
Given a bounded integer program with n variables and m constraints each with 2 variables we present an O(mU) time and O(m) space feasibility algorithm for such integer programs (where U is the maximal variable range size). We show that with the same complexity we can find an optimal solution for the positively weighted minimization problem for monotone systems. Using the localratio technique we develop an O(nmU) time and O(m) space 2-approximation algorithm for the positively weighted minimization problem for the general case. We further generalize all results to non linear constraints (called axis-convex constraints) and to non linear (but monotone) weight functions.
Our algorithms are not only better in complexity than other known algorithms, but they are also considerably simpler, and contribute to the understanding of these very fundamental problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Aspvall and Y. Shiloach. A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM Journal on Computing, 9:827–845, 1980.
R. Bar-Yehuda. One for the price of two: A unified approach for approximating covering problems. In APPROX’98 1st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 49–62, July 1998. To appear in Algorithmica.
R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2:198–203, 1981.
R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27–46, 1985.
S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multi-commodity flow problems. SIAM Journal on Computing, 5(4):691–703, 1976.
M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. Journal of the ACM, 35:921–940, 1988.
D. Gusfield and L. Pitt. A bounded approximation for the minimum cost 2-SAT problem. Algorithmica, 8:103–117, 1992.
D. S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555–556, 1982.
D. S. Hochbaum, N. Megiddo, J. Naor, and A. Tamir. Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Mathematical Programming, 62:69–83, 1993.
G. L. Nemhauser and L. E. Trotter. Vertex packings: structural properties and algorithms. Mathematical Programming, 8:232–248, 1975.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Yehuda, R., Rawitz, D. (1999). Efficient Algorithms for Integer Programs with Two Variables per Constraint. In: Nešetřil, J. (eds) Algorithms - ESA’ 99. ESA 1999. Lecture Notes in Computer Science, vol 1643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48481-7_11
Download citation
DOI: https://doi.org/10.1007/3-540-48481-7_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66251-8
Online ISBN: 978-3-540-48481-3
eBook Packages: Springer Book Archive