Approximating integer programs with positive right-hand sides
type: Item
instance of: scholarly article
title: Approximating integer programs with positive right-hand sides
zbMATH Open document ID: 1229.90098
author: Peter Jonsson
author: Johan Thapper
published in: Information Processing Letters
publication date: 2012-01-18T00:00:00Z
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5998988
zbMATH Keywords: integer linear programs
zbMATH Keywords: minimisation
zbMATH Keywords: NP-hard
MaRDI profile type: MaRDI publication profile
full work available at URL: j.ipl.2010.02.011
OpenAlex ID: W2027280132
cites work: Rounding algorithms for covering problems
cites work: Q4952606
cites work: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
cites work: On the hardness of approximating minimum vertex cover
cites work: Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
cites work: On the Greedy Heuristic for Continuous Covering and Packing Problems
cites work: A fast approximation algorithm for the multicovering problem
cites work: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
cites work: Approximability of Sparse Integer Programs
cites work: The complexity of satisfiability problems
DOI: 10.1016/J.IPL.2010.02.011
description: scientific article; zbMATH DE number 5998988