有容量的支配集問題的近似演算法

Approximation Algorithms for Capacitated Domination Problem

陳翰霖(Han-Lin Chen)

指導教授 ： 李德財

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01134

摘要

我們考慮容量支配集問題。此問題模型化了一般的服務-需求問題
並且是傳統的支配集問題的一個一般化。在這個問題裡，給定一圖並
在各個點上附有三個參數：價格、容量與需求。我們將要尋找一個最
低價格的配置並滿足需求與容量上的限制。我們在不同的需求配置模
型上提供了多項式時間的近似演算法，此演算法也逼近了傳統的支配
集問題的成果。與已知的前人的結果結合起來，已經從兩個方面逼近
了傳統支配集問題的成果。

關鍵字

支配集問題 ； 近似演算法

並列摘要

We consider the Capacitated Domination problem, which models a service requirement assignment scenario and is also a generalization of 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 for this problem on general graphs, which also establishes the corresponding
approximating results to the well-known approximations of the traditional Dominating Set problem. Together with previously known results, this closes the problem of generally approximating the optimal solution.

並列關鍵字

dominating Set ； approximation algorithm

參考文獻

algorithms for dominating set and related problems on planar graphs. Algorithmica,

33(4):461–493, 2002.

[2] Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data

reduction for dominating set. J. ACM, 51(3):363–384, 2004.

[3] Brenda S. Baker. Approximation algorithms for np-complete problems on planar