Primal-Dual Algorithms for Precedence Constrained Covering Problems

DOI10.1007/978-3-319-18263-6_22zbMath1457.68313OpenAlexW2156885983MaRDI QIDQ3453300

S. Thomas McCormick, Britta Peis, Andreas Wierz

Publication date: 20 November 2015

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-18263-6_22

zbMATH Keywords

knapsack problemprecedence constraintsapproximation algorithmscapacitated covering

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique-based facets for the precedence constrained knapsack problem
• Approximability of sparse integer programs
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Polyhedral results for the precedence-constrained knapsack problem
• On the approximability of average completion time scheduling under precedence constraints.
• Lifting valid inequalities for the precedence constrained knapsack problem
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Primal-Dual Schema for Capacitated Covering Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Non-approximability results for optimization problems on bounded degree instances
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Approximation and Online Algorithms

This page was built for publication: Primal-Dual Algorithms for Precedence Constrained Covering Problems