Approximation algorithms for partial covering problems
From MaRDI portal
Publication:4826763
DOI10.1016/j.jalgor.2004.04.002zbMath1068.68177MaRDI QIDQ4826763
Samir Khuller, Aravind Srinivasan, Rajiv Gandhi
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
Randomized rounding; Vertex cover; Approximation algorithms; Set cover; Partial covering; Primal-dual methods
68W25: Approximation algorithms
Related Items
Improved Upper Bounds for Partial Vertex Cover, 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, Subexponential algorithms for partial cover problems, Maximum subset intersection, A 6/5-approximation algorithm for the maximum 3-cover problem, 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, AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS, A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
