Precedence-constrained covering problems with multiplicity constraints

DOI10.1007/978-3-030-92702-8_15MaRDI QIDQ2085754zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Approximability of sparse integer programs
• Approximation algorithms for covering/packing integer programs
• Faces for a linear inequality in 0–1 variables
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Non-approximability results for optimization problems on bounded degree instances
• On the approximability of average completion time scheduling under precedence constraints.
• Primal-Dual Schema for Capacitated Covering Problems
• Primal-dual algorithms for precedence constrained covering problems
• The precedence constrained knapsack problem: separating maximally violated inequalities
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(2)

• Precedence-Constrained Min Sum Set Cover
• Precedence-constrained covering problems with multiplicity constraints

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

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