Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs

DOI10.1137/S0097539793260763zbMATH Open0914.68096OpenAlexW1988837529MaRDI QIDQ4210164FDOQ4210164

Authors 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

zbMATH Keywords

algorithmsapproximationset coverprimal-dualparallelvoting lemmas

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 1263280
• New approaches to covering and packing problems
• Distributed set cover approximation: primal-dual with optimal locality
• A threshold of ln n for approximating set cover
• scientific article; zbMATH DE number 1754596

Cites Work

• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A parallel approximation algorithm for positive linear programming
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Reducibility among combinatorial problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited In (35)

• How well can primal-dual and local-ratio algorithms perform?
• Set cover problems with small neighborhood covers
• Approximation algorithm for partial set multicover versus full set multicover
• Inapproximability of \(H\)-transversal/packing
• Set multi-covering via inclusion-exclusion
• Scheduling orders for multiple product types with due date related objectives
• New approaches to covering and packing problems
• A derandomization using min-wise independent permutations
• Robust multicovers with budgeted uncertainty
• On improved interval cover mechanisms for crowdsourcing markets
• Distributed spanner approximation
• Tight approximation bounds for maximum multi-coverage
• A self-stabilizing algorithm to maximal 2-packing with improved complexity
• Tight approximation bounds for maximum multi-coverage
• Beyond Moulin mechanisms
• Novel geometric approach for virtual coiling
• Approximation algorithm for the partial set multi-cover problem
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Set selection under explorable stochastic uncertainty via covering techniques
• Dynamic programming based algorithms for set multicover and multiset multicover problems
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
• Approximating set multi-covers
• Title not available (Why is no real title available?)
• A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times
• An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
• Constant-time distributed dominating set approximation
• On positive influence dominating sets in social networks
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• Parallel approximation for partial set cover
• Approximation of set multi-cover via hypergraph matching
• On the Approximability of Combinatorial Exchange Problems

This page was built for publication: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs

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