Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
From MaRDI portal
Publication:4210164
DOI10.1137/S0097539793260763zbMath0914.68096OpenAlexW1988837529MaRDI QIDQ4210164
Sridhar Rajagopalan, Vijay V. Vazirani
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793260763
Related Items (31)
Tight Approximation Bounds for Maximum Multi-coverage ⋮ Beyond Moulin mechanisms ⋮ Set multi-covering via inclusion-exclusion ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Novel geometric approach for virtual coiling ⋮ An anonymous self-stabilizing algorithm for 1-maximal independent set in trees ⋮ A derandomization using min-wise independent permutations ⋮ Approximating set multi-covers ⋮ A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Set selection under explorable stochastic uncertainty via covering techniques ⋮ On positive influence dominating sets in social networks ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ A self-stabilizing algorithm to maximal 2-packing with improved complexity ⋮ Approximation of set multi-cover via hypergraph matching ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ Approximation algorithm for partial set multicover versus full set multicover ⋮ Parallel approximation for partial set cover ⋮ Robust multicovers with budgeted uncertainty ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Constant-time distributed dominating set approximation ⋮ On the Approximability of Combinatorial Exchange Problems ⋮ Set cover problems with small neighborhood covers ⋮ Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Distributed Spanner Approximation ⋮ Scheduling orders for multiple product types with due date related objectives ⋮ Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons ⋮ Tight approximation bounds for maximum multi-coverage
Cites Work
- Unnamed Item
- On the ratio of optimal integral and fractional covers
- A Greedy Heuristic for the Set-Covering Problem
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Reducibility among Combinatorial Problems
- On the hardness of approximating minimization problems
- A parallel approximation algorithm for positive linear programming
This page was built for publication: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
