Efficient algorithms for integer programs with two variables per constraint.

DOI10.1007/s004530010075zbMath1106.90359OpenAlexW2800596119MaRDI QIDQ5943665

Dror Rawitz, Reuven Bar Yehuda

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)

Related Items (9)

On polynomial kernels for sparse integer linear programs ⋮ Trichotomy for integer linear systems based on their sign patterns ⋮ Approximability of sparse integer programs ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ The vehicle routing problem with coupled time windows ⋮ A set partitioning reformulation of a school bus scheduling problem ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ Combining Traditional Map Labeling with Boundary Labeling ⋮ Crossing Layout in Non-planar Graph Drawings

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