Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
From MaRDI portal
(Redirected from Publication:4210164)
Recommendations
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
(41)- Set cover problems with small neighborhood covers
- How well can primal-dual and local-ratio algorithms perform?
- A 1/2-approximation algorithm for maximum interval multi-cover
- Approximation algorithm for partial set multicover versus full set multicover
- Set multi-covering via inclusion-exclusion
- Inapproximability of \(H\)-transversal/packing
- 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
- A self-stabilizing algorithm to maximal 2-packing with improved complexity
- Robust multicovers with budgeted uncertainty
- Tight approximation bounds for maximum multi-coverage
- Distributed spanner approximation
- On improved interval cover mechanisms for crowdsourcing markets
- 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
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
- Set selection under explorable stochastic uncertainty via covering techniques
- Partial interval multicover: approximation and complexity
- Attaining equilibria using control sets
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Learn to optimize from structured samples for minimum partial set cover
- 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
- A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times
- scientific article; zbMATH DE number 2102778 (Why is no real title available?)
- 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
- When far is better: the Chamberlin-Courant approach to obnoxious committee selection
- Constant-time distributed dominating set approximation
- On positive influence dominating sets in social networks
- Scheduling splittable jobs on configurable machines
- 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)
