Precedence-constrained covering problems with multiplicity constraints

DOI10.1007/978-3-030-92702-8_15OpenAlexW4205268374MaRDI QIDQ2085754

Stavros G. Kolliopoulos, Antonis Skarlatos

Publication date: 19 October 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92702-8_15

zbMATH Keywords

precedence constraintscovering integer programs

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items

Precedence-constrained covering problems with multiplicity constraints

Cites Work

• Unnamed Item
• Unnamed Item
• The precedence constrained knapsack problem: separating maximally violated inequalities
• Approximability of sparse integer programs
• On the approximability of average completion time scheduling under precedence constraints.
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• 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
• Primal-Dual Schema for Capacitated Covering Problems
• 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