A unified approach to approximating partial covering problems

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

zbMATH Keywords

Lagrangian relaxationapproximation algorithmspartial cover

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (34)

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 ⋮ Solving the set covering problem with conflicts on sets: a new parallel GRASP ⋮ Approximation algorithm for stochastic set cover problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties ⋮ 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