Approximation algorithms for partial covering problems

DOI10.1016/j.jalgor.2004.04.002zbMath1068.68177MaRDI QIDQ4826763

Aravind Srinivasan, Rajiv Gandhi, Samir Khuller

Publication date: 12 November 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1903/1129

zbMATH Keywords

Randomized rounding; Vertex cover; Approximation algorithms; Set cover; Partial covering; Primal-dual methods

Mathematics Subject Classification ID

68W25: Approximation algorithms

Related Items

Approximation algorithm for partial set multicover versus full set multicover, Unnamed Item, Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem, Constant-approximation for minimum weight partial sensor cover, Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems, Approximating Partially Bounded Degree Deletion on Directed Graphs, On Partial Covering For Geometric Set Systems, Improved Upper Bounds for Partial Vertex Cover, Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs, An approximation algorithm for the partial vertex cover problem in hypergraphs, Randomized approximation for the set multicover problem in hypergraphs, An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem, Thresholded covering algorithms for robust and max-min optimization, Partial multicovering and the \(d\)-consecutive ones property, On the inapproximability of maximum intersection problems, An exact procedure and LP formulations for the leader-follower location problem, A unified approach to approximating partial covering problems, Implicit branching and parameterized partial cover problems, An improved approximation algorithm for the most points covering problem, Approximation algorithms for the partition vertex cover problem, A randomised approximation algorithm for the hitting set problem, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, Partial multicuts in trees, Multiple voting location problems, A simple approximation algorithm for minimum weight partial connected set cover, Subexponential algorithms for partial cover problems, Maximum subset intersection, A 6/5-approximation algorithm for the maximum 3-cover problem, Lift \& project systems performing on the partial-vertex-cover polytope, Approximation algorithm for the partial set multi-cover problem, Approximation algorithm for the multicovering problem, Approximation algorithm for stochastic set cover problem, Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks, Approximation algorithm for vertex cover with multiple covering constraints, A primal-dual algorithm for the minimum power partial cover problem, Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty, Approximation algorithm for minimum partial multi-cover under a geometric setting, Parallel algorithm for minimum partial dominating set in unit disk graph, Algorithms for covering multiple submodular constraints and applications, Iterative partial rounding for vertex cover with hard capacities, Parallel approximation for partial set cover, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, An approximation algorithm for the partial covering 0-1 integer program, A primal-dual algorithm for the minimum partial set multi-cover problem, Set cover problems with small neighborhood covers, The most points connected-covering problem with two disks, Approximation algorithms for the covering-type \(k\)-violation linear program, Geometric red-blue set cover for unit squares and related problems, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, Capacitated Arc Stabbing, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, Local ratio method on partial set multi-cover, Minimum power partial multi-cover on a line, Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph, An approximation algorithm for \(P\)-prize-collecting set cover problem, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS, The Approximability of Partial Vertex Covers in Trees, Maximum Weighted Independent Sets with a Budget, A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem