Improved performance of the greedy algorithm for partial cover
From MaRDI portal
Publication:293139
DOI10.1016/S0020-0190(97)00182-8zbMath1339.68318OpenAlexW2155148197MaRDI QIDQ293139
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097001828?np=y
combinatorial optimizationgreedy algorithmapproximation algorithmsset coverminimum coverpartial cover
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Capacitated Arc Stabbing ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Partial multicuts in trees ⋮ Local ratio method on partial set multi-cover ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ On fair covering and hitting problems ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ On colorful vertex and edge cover problems ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ Complexity of majority monopoly and signed domination problems ⋮ Graph coloring with rejection ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ On approximation of the submodular set cover problem ⋮ Approximation algorithm for partial set multicover versus full set multicover ⋮ Parallel approximation for partial set cover ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Combinatorial optimization algorithms for radio network planning ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Approximation algorithm for stochastic set cover problem ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Computing small partial coverings ⋮ Approximation algorithms for the partition vertex cover problem ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ 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 ⋮ On Partial Covering For Geometric Set Systems
Cites Work
