Capacitated domination problem

DOI10.1007/S00453-009-9336-XMaRDI QIDQ534769zbMATH OpenOpenAlexFDO

Authors Mong-Jen Kao, Chung-Shou Liao, 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

zbMATH Keywords

AlgorithmDominationFacility location

Mathematics Subject Classification ID

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

• scientific article; zbMATH DE number 1305496 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• A constant-factor approximation algorithm for the k-median problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A new greedy approach for facility location problems
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• A threshold of ln n for approximating set cover
• Algorithmic aspect of k-tuple domination in graphs.
• Algorithms - ESA 2003
• An improved approximation algorithm for vertex cover with hard capacities
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximating \(k\)-median with non-uniform capacities
• Approximating min-sum k -clustering in metric spaces
• Approximation Algorithms for Metric Facility Location Problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for combinatorial problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Capacitated vertex covering
• Covering Problems with Hard Capacities
• Dependent rounding and its applications to approximation algorithms
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Generalized submodular cover problems and applications
• Improved approximation algorithms for capacitated facility location problems
• Integer Programming and Combinatorial Optimization
• Local Search Heuristics for k-Median and Facility Location Problems
• On the ratio of optimal integral and fractional covers
• \(k\)-tuple domination in graphs

Cited in

(6)

• Iterative partial rounding for vertex cover with hard capacities
• \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities
• scientific article; zbMATH DE number 1271323 (Why is no real title available?)
• 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)