Efficient algorithms for integer programs with two variables per constraint.

DOI10.1007/S004530010075MaRDI QIDQ5943665zbMATH OpenOpenAlexFDO

Authors Reuven Bar-Yehuda, Dror Rawitz

Publication date 27 September 2001

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

2 SATApproximation algorithmCombinatorial optimization: Integer programmingLocal-ratio techniqueVertex cover

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1405787
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Algorithms and Computation

Cited in

(20)

• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• On polynomial kernels for sparse integer linear programs
• scientific article; zbMATH DE number 1670524 (Why is no real title available?)
• Combining traditional map labeling with boundary labeling
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• scientific article; zbMATH DE number 1757949 (Why is no real title available?)
• scientific article; zbMATH DE number 1405787 (Why is no real title available?)
• Crossing Layout in Non-planar Graph Drawings
• On integer programming and convolution
• Algorithms and Computation
• Approximating infeasible 2VPI-systems
• A fast algorithm for unbounded monotone integer linear systems with two variables per inequality via graph decomposition
• Applications and efficient algorithms for integer programming problems on monotone constraints
• Approximability of sparse integer programs
• A set partitioning reformulation of a school bus scheduling problem
• Graph realization of distance sets
• Trichotomy for integer linear systems based on their sign patterns
• The vehicle routing problem with coupled time windows

This page was built for publication: Efficient algorithms for integer programs with two variables per constraint.

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