臺灣博碩士論文加值系統

我們考慮在圖論上廣為人知的支配集問題，並將它加以推廣。所謂「有容量的支配集問題」是指在給定的圖上，尋找滿足每個點的容量限制(capacity)與需求限制(demand)的最小支配集。在這個問題模型中，每個點都有各自的容量和需求。容量(capacity)指的是，每份此頂點的實體(copy)，可以容納多少單位來自閉鄰點(closed
neighborhood)的需求。而需求(demand)指的則是，此頂點需要多少單位來自閉鄰點的容量供給。

在此論文中，我們從演算法的觀點探討「有容量的支配集問題」在樹狀結構中的表現。在需求不可分割的模型裡，我們提供了線性時間複雜度的演算法；而對於需求可分割的問題模型，我們則提供了虛擬多項式時間(pseudo-polynomial time)的演算法。

除此之外，我們也証明，當需求可分割時，這個問題在樹狀結構上也是NP-完備，並進一步提供可任意逼近最佳解(polynomial
time approximation scheme)的演算法。對於一般的圖，我們則提供以線性規劃的primal-dual為基礎的近似演算法。

We consider a generalization of the well-known domination problem on graphs. The soft capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demand of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies that the demand of each vertex in
V is met by the capacities of vertices in D dominating it.

In this thesis, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.

Contents
口試委員會審定書....................................i
Acknowledgement...................................ii
Chinese Abstract....................................iii
English Abstract....................................iv
1 Introduction
1.1 Preliminaries...................................5
2 Capacitated Domination on Trees
2.1 Unsplittable Demand Model...........................7
2.2 NP-completeness for Splittable Demand Model................13
2.3 A Pseudo-polynomial Time Algorithm for Splittable Demand Model....16
2.3.1 The Relaxed Knapsack Problem....................21
3 Approximation Algorithms for Splittable Demand Model
3.1 Approximation on Trees.............................23
3.2 Approximation on General Graphs.......................27
4 Conclusion
4.1 Discussion.....................................32
4.2 Future Work...................................34
Bibliography 34
A Pseudo Codes 39
A.1 Algorithm MCDUT...............................39
A.2 Algorithm MCDST................................43
A.3 Algorithm MCDAWG..............................46
B Implementation 48

[1] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3) (2004) pp. 544-562.

[2] J. Bar-Ilan, G. Kortsarz, D. Peleg. Generalized submodular cover problems and applications. Theoretical Computer Science, 250 (2001) pp. 179-200.

[3] R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2 (1981) pp. 198-203.

[4] Y. Bartal, M. Charikar, and D. Raz. Approximating min-sum k-clustering in metric spaces. In Proceedings of 33th ACM Symposium on Theory of Computing, (2001) pp. 11-20.

[5] M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and k-median problems. In Proceedings of 40th IEEE Symposium of Foundations of Computer Science, (1999) pp. 378-388.

[6] M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1) (2002) pp. 129-149.

[7] X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z.Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks.
Networks, 42(4) (2003) pp. 202-208.

[8] J. Chuzhoy and J.S. Naor. Covering problems with hard capacities. SIAM Journal on Computing, 36(2) (2006) pp. 498-515.

[9] J. Chuzhoy and Y. Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, (2005) pp. 952-958.

[10] F.A. Chudak and D.B. Shmoys. Improved approximation algorithms for a capacitated facility location problem. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, (1999) pp. 875-876.

[11] F.A. Chudak and D.P. Williamson. Improved approximation algorithms for capacitated facility location problems. Mathematical Programming, 102(2) (2005) pp. 207-222.

[12] V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3) (1979) pp. 233-235.

[13] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4) (1998) pp. 634-652.

[14] R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan. An improved approximation algorithm for vertex cover with hard capacities. Journal of Computer and System Sciences, 72(1) (2006) pp. 16-33.

[15] R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM, 53(3) (2006) pp. 324-360.

[16] S. Guha, R. Hassin, S. Khuller, and E. Or. Capacitated vertex covering. Journal of Algorithms, 48(1) (2003) pp. 257-270.

[17] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater. Domination in Graphs: The Theory, Marcel Dekker, Inc. New York (1998).

[18] D.S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3) (1982) pp. 555-556.

[19] O.H. Ibarra and C.E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4) (1975) pp. 463-468.

[20] K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems. In Proceedings of 34th ACM Symposium on Theory of Computing, (2002) pp. 731-740.

[21] K. Jain and V.V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal
of the ACM, 48(2) (2001) pp. 274-296.

[22] D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3) (1974), pp. 256-278.

[23] M. Korupolu, C. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1) (2000) pp. 146-188.

[24] R. Levi, D.B. Shmoys, and C. Swamy. LP-based approximation algorithms for capacitated facility location. In Proceedings of 10th Conference on Integer Programming
and Combinatorial Optimization, (2004) pp. 206-218.

[25] C. S. Liao and G. J. Chang. Algorithmic aspect of k-tuple domination in graphs. Taiwanese J. Math., 6 (2002) 415-420.

[26] C.S. Liao and G.J. Chang. k-tuple domination in graphs. Inform. Process. Letter., 87(1) (2003) pp. 45-50.

[27] L. Lovasz. On the ratio of optimal and fractional covers. Discrete Math., 13 (1975) pp. 383-390.

[28] M. Mahdian and M. Pal. Universal facility location. In Proceedings of 11th European Symposium on Algorithms, (2003) pp. 409-421.

[29] M. Mahdian, Y. Ye, and J. Zhang. Approximation algorithms for metric facility location problems. SIAM Journal on Computing, 36(2) (2006) pp. 411-432.

[30] M. Pal, E . Tardos, and T. Wexler. Facility location with nonuniform hard capacities. In Proceedings of 42th Symposium of Foundations of Computer Science, (2001) pp.
329-338.

[31] D.B. Shmoys, E . Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proceedings of 29th ACM Symposium on Theory of Computing, (1997) pp. 265-274.

[32] J. Zhang, Bo Chen, and Y. Ye. A multi-exchange local search algorithm for the capacitated facility location problem. Mathematics of Operations Research, 30(2)
(2005) pp. 389-403.