Capacitated domination problem
DOI10.1007/S00453-009-9336-XzbMATH Open1213.05194OpenAlexW2080697418MaRDI QIDQ534769FDOQ534769
Chung-Shou Liao, Der-Tsai Lee, Mong-Jen Kao
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
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On the ratio of optimal integral and fractional covers
- Generalized submodular cover problems and applications
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Improved approximation algorithms for capacitated facility location problems
- Capacitated vertex covering
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- Algorithms - ESA 2003
- Dependent rounding and its applications to approximation algorithms
- \(k\)-tuple domination in graphs
- A new greedy approach for facility location problems
- Integer Programming and Combinatorial Optimization
- Approximation Algorithms for Metric Facility Location Problems
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Local Search Heuristics for k-Median and Facility Location Problems
- Analysis of a Local Search Heuristic for Facility Location Problems
- A constant-factor approximation algorithm for the \(k\)-median problem
- Algorithmic aspect of \(k\)-tuple domination in graphs.
- Approximating min-sum k -clustering in metric spaces
- An improved approximation algorithm for vertex cover with hard capacities
- Approximating \(k\)-median with non-uniform capacities
- Covering Problems with Hard Capacities
Cited In (6)
- Iterative partial rounding for vertex cover with hard capacities
- \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities
- Title not available (Why is that?)
- Capacitated domination: problem complexity and approximation algorithms
- Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
- Tight approximation for partial vertex cover with hard capacities
This page was built for publication: Capacitated domination problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534769)
