Integer programming as a framework for optimization and approximability

DOI10.1006/jcss.1998.1584zbMath0915.90212OpenAlexW2086176558MaRDI QIDQ1276163

Madhukar N. Thakur, Ian Barland, Phokion G. Kolaitis

Publication date: 15 June 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/58acdba60120d4079f41b7bfbfc77dfaaa64ae5a

zbMATH Keywords

structural approximation theory

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (2)

The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Expressing combinatorial optimization problems by linear programs
• Approximation algorithms for combinatorial problems
• Integer programming formulation of combinatorial optimization problems
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Logical definability of NP optimization problems
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Approximation properties of NP minimization classes
• On Syntactic versus Computational Views of Approximability

This page was built for publication: Integer programming as a framework for optimization and approximability