Covering Problems with Hard Capacities
From MaRDI portal
Publication:3434996
DOI10.1137/S0097539703422479zbMath1112.68066MaRDI QIDQ3434996
Julia Chuzhoy, Joseph (Seffi) Naor
Publication date: 3 May 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (29)
Capacitated Arc Stabbing ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ Approximating power node-deletion problems ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ Capacitated covering problems in geometric spaces ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Primal-Dual Schema for Capacitated Covering Problems ⋮ Improved bounds for metric capacitated covering problems ⋮ The Exact Subset MultiCover problem ⋮ Unnamed Item ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Capacitated Domination Problem ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Capacitated domination problem ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ The multi‐integer set cover and the facility terminal cover problem ⋮ Unnamed Item ⋮ An LP-Based Correlated Rounding Scheme for Multi-Item Ecommerce Order Fulfillment ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Capacitated discrete unit disk cover ⋮ Primal-dual schema for capacitated covering problems ⋮ Retracting Graphs to Cycles ⋮ Randomized Rounding in the Presence of a Cardinality Constraint ⋮ Approximation algorithm for vertex cover with multiple covering constraints ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Capacitated domination: problem complexity and approximation algorithms
This page was built for publication: Covering Problems with Hard Capacities
