Capacitated domination problem
From MaRDI portal
Publication:534769
DOI10.1007/s00453-009-9336-xzbMath1213.05194OpenAlexW2080697418MaRDI QIDQ534769
Chung-Shou Liao, Mong-Jen Kao, Der-Tsai Lee
Publication date: 10 May 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9336-x
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
Tight approximation for partial vertex cover with hard capacities, Iterative partial rounding for vertex cover with hard capacities, \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities, Capacitated domination: problem complexity and approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(k\)-tuple domination in graphs
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Generalized submodular cover problems and applications
- Improved approximation algorithms for capacitated facility location problems
- Algorithmic aspect of \(k\)-tuple domination in graphs.
- A constant-factor approximation algorithm for the \(k\)-median problem
- An improved approximation algorithm for vertex cover with hard capacities
- A threshold of ln n for approximating set cover
- Approximation Algorithms for Metric Facility Location Problems
- Covering Problems with Hard Capacities
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Dependent rounding and its applications to approximation algorithms
- A new greedy approach for facility location problems
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Capacitated vertex covering
- Analysis of a Local Search Heuristic for Facility Location Problems
- Local Search Heuristics for k-Median and Facility Location Problems
- Approximating min-sum k -clustering in metric spaces
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- Integer Programming and Combinatorial Optimization
- Algorithms - ESA 2003
