Using Homogeneous Weights for Approximating the Partial Cover Problem
From MaRDI portal
Publication:2729647
DOI10.1006/jagm.2000.1150zbMath0974.68236OpenAlexW2070814595MaRDI QIDQ2729647
Publication date: 12 December 2001
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.2000.1150
Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, Capacitated Arc Stabbing, Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, Partial multicuts in trees, 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, Local ratio method on partial set multi-cover, 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, Approximating power node-deletion problems, 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, A unified approach to approximating partial covering problems, The Approximability of Partial Vertex Covers in Trees, Maximum Weighted Independent Sets with a Budget, Implicit branching and parameterized partial cover problems, 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, Approximation algorithm for the multicovering problem, Unnamed Item, A bicriteria algorithm for the minimum submodular cost partial set multi-cover 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, 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, On Partial Covering For Geometric Set Systems, Approximation algorithms for maximum linear arrangement, Approximation algorithm for minimum partial multi-cover under a geometric setting, Randomized approximation for the set multicover problem in hypergraphs
