TY - GEN

T1 - Approximation algorithms for the capacitated domination problem

AU - Kao, Mong Jen

AU - Chen, Han Lin

N1 - Funding Information:
This work was supported in part by the National Science Council, Taipei 10622, Taiwan, under the Grants NSC98-2221-E-001-007-MY3, NSC98-2221-E-001-008-MY3, NSC97-2219-E-001-001, and NSC97-2745-P-001-001.

PY - 2010

Y1 - 2010

N2 - We consider the Capacitated Domination problem, which models a service-requirement assignment scenario and is a generalization to the well-known Dominating Set problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service. In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models on general graphs. On the other hand, from the perspective of parameterization, we prove that this problem is W[1]-hard when parameterized by a structure of the graph called treewidth. Based on this hardness result, we present exact fixed-parameter tractable algorithms with respect to treewidth and maximum capacity of the vertices. This algorithm is further extended to obtain pseudo-polynomial time approximation schemes for planar graphs.

AB - We consider the Capacitated Domination problem, which models a service-requirement assignment scenario and is a generalization to the well-known Dominating Set problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service. In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models on general graphs. On the other hand, from the perspective of parameterization, we prove that this problem is W[1]-hard when parameterized by a structure of the graph called treewidth. Based on this hardness result, we present exact fixed-parameter tractable algorithms with respect to treewidth and maximum capacity of the vertices. This algorithm is further extended to obtain pseudo-polynomial time approximation schemes for planar graphs.

UR - http://www.scopus.com/inward/record.url?scp=77955902625&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14553-7_19

DO - 10.1007/978-3-642-14553-7_19

M3 - Conference contribution

AN - SCOPUS:77955902625

SN - 3642145523

SN - 9783642145520

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 185

EP - 196

BT - Frontiers in Algorithmics - 4th International Workshop, FAW 2010, Proceedings

Y2 - 11 August 2010 through 13 August 2010

ER -