A unified approach to approximating partial covering problems
From MaRDI portal
Publication:633845
DOI10.1007/s00453-009-9317-0zbMath1211.68511OpenAlexW2175530190MaRDI QIDQ633845
Ojas Parekh, Jochen Könemann, 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
Related Items (32)
Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs ⋮ A note on the minimum power partial cover problem on the plane ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ Approximation algorithm for the stochastic prize-collecting set multicover problem ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ 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 ⋮ An approximation algorithm for the \(H\)-prize-collecting power cover problem ⋮ An approximation algorithm for \(P\)-prize-collecting set cover problem ⋮ An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem ⋮ Black-box reductions for cost-sharing mechanism design ⋮ Parallel approximation for partial set cover ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Unnamed Item ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ Approximation algorithm for stochastic set cover problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ On Partial Covering For Geometric Set Systems ⋮ Unnamed Item ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Partial multicuts in trees
- Path hitting in acyclic graphs
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Constrained weighted matchings and edge coverings in graphs
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- On approximation of the submodular set cover problem
- On the hardness of approximating Multicut and Sparsest-Cut
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- A threshold of ln n for approximating set cover
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On the power of unique 2-prover 1-round games
- Saving an epsilon
- Approximating the k-multicut problem
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- A linear-time approximation algorithm for the weighted vertex cover problem
- A 1-matching blossom-type algorithm for edge covering problems
- Set Partitioning: A survey
- Covering, Packing and Knapsack Problems
- A Tight Analysis of the Greedy Algorithm for Set Cover
- Approximation algorithms for partial covering problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
This page was built for publication: A unified approach to approximating partial covering problems
