A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
From MaRDI portal
Publication:2391176
DOI10.1007/S00453-007-9003-ZzbMATH Open1194.68262OpenAlexW2178856181MaRDI QIDQ2391176FDOQ2391176
Authors: Julián Mestre 
Publication date: 24 July 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9003-z
Recommendations
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximation algorithms for partial covering problems
- scientific article; zbMATH DE number 1754596
- An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
- Improved Upper Bounds for Partial Vertex Cover
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for NP-hard problems.
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Using homogeneous weights for approximating the partial cover problem
- Algorithms for facility location problems with outliers. (Extended abstract)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Title not available (Why is that?)
- Approximation algorithms for partial covering problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Capacitated vertex covering
- Title not available (Why is that?)
- Dependent rounding and its applications to approximation algorithms
- Title not available (Why is that?)
- Automata, Languages and Programming
- Title not available (Why is that?)
Cited In (18)
- Approximation algorithms for partial vertex covers in trees
- Lift \& project systems performing on the partial-vertex-cover polytope
- Improved Upper Bounds for Partial Vertex Cover
- Tight approximation for partial vertex cover with hard capacities
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
- The Approximability of Partial Vertex Covers in Trees
- Approximation algorithms for the partition vertex cover problem
- Approximation algorithm for vertex cover with multiple covering constraints
- Capacitated Arc Stabbing
- Using homogeneous weights for approximating the partial cover problem
- Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems
- On Partial Covering For Geometric Set Systems
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs
- Tight approximation for partial vertex cover with hard capacities
This page was built for publication: A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391176)
