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-coverageBeyond Moulin mechanismsSet multi-covering via inclusion-exclusionAn Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity ModelNovel geometric approach for virtual coilingAn anonymous self-stabilizing algorithm for 1-maximal independent set in treesA derandomization using min-wise independent permutationsApproximating set multi-coversA parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery timesParallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graphInapproximability of $H$-Transversal/PackingSet selection under explorable stochastic uncertainty via covering techniquesOn positive influence dominating sets in social networksOn improved interval cover mechanisms for crowdsourcing marketsA self-stabilizing algorithm to maximal 2-packing with improved complexityApproximation of set multi-cover via hypergraph matchingApproximation schemes for deal splitting and covering integer programs with multiplicity constraintsApproximation algorithm for partial set multicover versus full set multicoverParallel approximation for partial set coverRobust multicovers with budgeted uncertaintyApproximation algorithm for the partial set multi-cover problemDynamic programming based algorithms for set multicover and multiset multicover problemsA bicriteria algorithm for the minimum submodular cost partial set multi-cover problemConstant-time distributed dominating set approximationOn the Approximability of Combinatorial Exchange ProblemsSet cover problems with small neighborhood coversBreaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover ProblemDistributed Spanner ApproximationScheduling orders for multiple product types with due date related objectivesFast distributed algorithms for (weakly) connected dominating sets and linear-size skeletonsTight approximation bounds for maximum multi-coverage



Cites Work


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