Precedence-constrained covering problems with multiplicity constraints

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

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

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

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)