Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
From MaRDI portal
Publication:1321662
DOI10.1007/BF01585160zbMath0802.90080MaRDI QIDQ1321662
Dorit S. Hochbaum, Nimrod Megiddo, Arie Tamir, Joseph (Seffi) Naor
Publication date: 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Related Items
Vertex cover meets scheduling, Distributionally robust mixed integer linear programs: persistency models with applications, On approximation algorithms for the minimum satisfiability problem, The Linear Complementarity Problems with a Few Variables per Constraint, Binary integer programs with two variables per inequality, Resolution of indecomposable integral flows on signed graphs, On the tree augmentation problem, Some results on the strength of relaxations of multilinear functions, Approximability of the vertex cover problem in power-law graphs, Solving min ones 2-SAT as fast as vertex cover, Minimum shared‐power edge cut, Neighborhood persistency of the linear optimization relaxation of integer linear optimization, Trichotomy for integer linear systems based on their sign patterns, Approximability of sparse integer programs, Rational and integral \(k\)-regular matrices., Technical Note—Assortment Optimization with Small Consideration Sets, Approximating integer programs with positive right-hand sides, A set partitioning reformulation of a school bus scheduling problem, A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Monotonizing linear programs with up to two nonzeroes per column, On the complexity of submodular function minimisation on diamonds, Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs, Trichotomy for the reconfiguration problem of integer linear systems, Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, The Next Whisky Bar, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Unnamed Item, A q-queens problem. VI. The bishops' period, Complexity results for some global optimization problems, Integer programming as a framework for optimization and approximability, Minimal distance of propositional models, Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, Introduction to the Maximum Solution Problem, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
Cites Work
- Efficient bounds for the stable set, vertex cover and set packing problems
- A bounded approximation for the minimum cost 2-sat problem
- Testing the necklace condition for shortest tours and optimal factors in the plane
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Integer Programming with a Fixed Number of Variables
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- The Computational Complexity of Simultaneous Diophantine Approximation Problems
- A Polynomial Algorithm for the Two-Variable Integer Programming Problem
- Vertex packings: Structural properties and algorithms
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- On the Complexity of Timetable and Multicommodity Flow Problems
