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