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

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

zbMATH Keywords

algorithmsapproximationset coverprimal-dualparallelvoting lemmas

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Cites Work

• Reducibility among Combinatorial Problems
• A Greedy Heuristic for the Set-Covering Problem
• On the ratio of optimal integral and fractional covers
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• On the hardness of approximating minimization problems
• Title not available (Why is that?)
• A parallel approximation algorithm for positive linear programming

Cited In (34)

• Set cover problems with small neighborhood covers
• Approximation algorithm for partial set multicover versus full set multicover
• 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
• Tight approximation bounds for maximum multi-coverage
• A self-stabilizing algorithm to maximal 2-packing with improved complexity
• 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 that?)
• 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
• Inapproximability of $H$-Transversal/Packing
• 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
• Tight Approximation Bounds for Maximum Multi-coverage
• Distributed Spanner 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)