Precedence-constrained covering problems with multiplicity constraints

DOI10.1007/s10878-023-01027-4zbMath1518.90089OpenAlexW4367679646MaRDI QIDQ6039535

Antonis Skarlatos, Stavros G. Kolliopoulos

Publication date: 5 May 2023

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-023-01027-4

zbMATH Keywords

precedence constraintscovering integer programs

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• The precedence constrained knapsack problem: separating maximally violated inequalities
• Approximability of sparse integer programs
• Primal-dual schema for capacitated covering problems
• On the approximability of average completion time scheduling under precedence constraints.
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Precedence-constrained covering problems with multiplicity constraints
• Primal-dual algorithms for precedence constrained covering problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Approximation algorithms for covering/packing integer programs
• Faces for a linear inequality in 0–1 variables
• Non-approximability results for optimization problems on bounded degree instances
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

This page was built for publication: Precedence-constrained covering problems with multiplicity constraints