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 (36)
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
This page was built for publication: Using Homogeneous Weights for Approximating the Partial Cover Problem
