Instant recognition of half integrality and 2-approximations

DOI10.1007/BFB0053967MaRDI QIDQ4400848zbMATH OpenFDO

Authors Dorit S. Hochbaum

Publication date 2 August 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0053967

zbMATH Keywords

2-approximate solutionbinary integer programshalf integral superoptimal solutions

Mathematics Subject Classification ID

Boolean programming (90C09) Integer programming (90C10)

Recommendations

• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Instant recognition of polynomial time solvability, half integrality and 2-approximations
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

Cited in

(8)

• On dependent randomized rounding algorithms
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• A primal-dual approximation algorithm for \textsc{minsat}
• scientific article; zbMATH DE number 1670524 (Why is no real title available?)
• Experimental and Efficient Algorithms
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Rounding to an integral program

This page was built for publication: Instant recognition of half integrality and 2-approximations

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