A unified approach to approximating partial covering problems
From MaRDI portal
Publication:633845
DOI10.1007/S00453-009-9317-0zbMATH Open1211.68511OpenAlexW2175530190MaRDI QIDQ633845FDOQ633845
Authors: Jochen Könemann, Ojas Parekh, Danny Segev 
Publication date: 30 March 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9317-0
Recommendations
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Title not available (Why is that?)
- On the ratio of optimal integral and fractional covers
- Using homogeneous weights for approximating the partial cover problem
- Algorithms for facility location problems with outliers. (Extended abstract)
- Approximation algorithms for partial covering problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- On the hardness of approximating Multicut and Sparsest-Cut
- On the power of unique 2-prover 1-round games
- Set Partitioning: A survey
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Title not available (Why is that?)
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Constrained weighted matchings and edge coverings in graphs
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- A 1-matching blossom-type algorithm for edge covering problems
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Approximating the k-multicut problem
- Title not available (Why is that?)
- On approximation of the submodular set cover problem
- Lagrangian relaxation and partial cover (Extended abstract)
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- A Tight Analysis of the Greedy Algorithm for Set Cover
- Partial multicuts in trees
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- Path hitting in acyclic graphs
- Covering, Packing and Knapsack Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (44)
- Title not available (Why is that?)
- Algorithms for covering multiple submodular constraints and applications
- On partial covering for geometric set systems
- Lift \& project systems performing on the partial-vertex-cover polytope
- Title not available (Why is that?)
- Solving the set covering problem with conflicts on sets: a new parallel GRASP
- An approximation algorithm for the \(H\)-prize-collecting power cover problem
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- Partial multicovering and the \(d\)-consecutive ones property
- Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
- Title not available (Why is that?)
- Partial vertex cover and budgeted maximum coverage in bipartite graphs
- Black-box reductions for cost-sharing mechanism design
- An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
- On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
- Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage
- An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- On uniform covering, adaptive random search and raspberries
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- One for the price of two: a unified approach for approximating covering problems
- Implicit branching and parameterized partial cover problems
- Approximation algorithm for the partial set multi-cover problem
- Approximation algorithm for the stochastic prize-collecting set multicover problem
- An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
- Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
- Approximation algorithm for stochastic set cover problem
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- A GRASP algorithm to solve the unicost set covering problem
- Black-box reductions for cost-sharing mechanism design
- Approximating \(k\)-forest with resource augmentation: a primal-dual approach
- A note on the minimum power partial cover problem on the plane
- Approximating node-weighted \(k\)-MST on planar graphs
- From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
- A simple approximation algorithm for minimum weight partial connected set cover
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- On the integrality gap of the prize-collecting Steiner forest LP
- An approximation algorithm for \(P\)-prize-collecting set cover problem
- A Unified Approach to Approximating Partial Covering Problems
- An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem
- A PTAS for the cardinality constrained covering with unit balls
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
- Parallel approximation for partial set cover
This page was built for publication: A unified approach to approximating partial covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633845)
