Primal-dual algorithms for precedence constrained covering problems

DOI10.1007/978-3-319-18263-6_22MaRDI QIDQ3453300zbMATH OpenOpenAlexFDO

Authors Andreas Wierz, Britta Peis, S. Thomas McCormick

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

approximation algorithmscapacitated coveringknapsack problemprecedence constraints

Mathematics Subject Classification ID

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

Recommendations

• Primal-dual algorithms for precedence constrained covering problems
• Precedence-constrained covering problems with multiplicity constraints
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Polyhedral results for the precedence-constrained knapsack problem
• On column-restricted and priority covering integer programs

Cites work

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

Cited in

(6)

• A pegging approach to the precedence-constrained knapsack problem
• Primal-dual algorithms for precedence constrained covering problems
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• scientific article; zbMATH DE number 1138448 (Why is no real title available?)
• Precedence-Constrained Min Sum Set Cover
• Precedence-constrained covering problems with multiplicity constraints

This page was built for publication: Primal-dual algorithms for precedence constrained covering problems

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