Adaptive local ratio

ABSTRACT

Local Ratio is a well-known paradigm for designing approximation algorithms for combinatorial optimization problems. At a very high level, a local ratio algorithm first decomposes the input weight function w into a positive linear combination of simpler weight functions or models. Guided by this process a solution S is constructed such that S is α-approximate with respect to each model used in the decomposition. As a result, S is α-approximate under w as well.

These models usually have a very simple structure that remains "unchanged" throughout the execution of the algorithm. In this work we show that adaptively choosing a model from a richer spectrum of functions can lead to a better local ratio. Indeed, by turning the search for a good model into an optimization problem of its own, we get improved approximations for a data migration problem.

REFERENCES

• 1: Eric Anderson , Joseph Hall , Jason D. Hartline , Michael Hobbs , Anna R. Karlin , Jared Saia , Ram Swaminathan , John Wilkes, An Experimental Study of Data Migration Algorithms, Proceedings of the 5th International Workshop on Algorithm Engineering, p.145-158, August 28-31, 2001
• 2: N. Bansal, L. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, and M. Sviridenko. Further improvements in competitive guarantees for QoS buffering. In Proceedings of the 14th International Colloquium on Automata, Languages, and Programming (ICALP), pages 196--207, 2004.
• 3: Amotz Bar-Noy , Mihir Bellare , Magnús M. Halldórsson , Hadas Shachnai , Tami Tamir, On chromatic sums and distributed resource allocation, Information and Computation, v.140 n.2, p.183-202, Feb. 1, 1998 [doi>10.1006/inco.1997.2677 ]
• 4: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 5: R. Bar-Yehuda. One for the price of two: A unified approach for approximating covering problems. Algorithmica, 27(2):131--144, 2000.
• 6: Reuven Bar-Yehuda, Using homogeneous weights for approximating the partial cover problem, Journal of Algorithms, v.39 n.2, p.137-144, May 2001 [doi>10.1006/jagm.2000.1150 ]
• 7: R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27--46, 1985.
• 8: Reuven Bar-Yehuda , Dror Rawitz, On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique, SIAM Journal on Discrete Mathematics, v.19 n.3, p.762-797, 2005 [doi>10.1137/050625382]
• 9: Reuven Bar-Yehuda , Keren Bendel , Ari Freund , Dror Rawitz, Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004, ACM Computing Surveys (CSUR), v.36 n.4, p.422-463, December 2004 [doi>10.1145/1041680.1041683]
• 10: B. E. Birnbaum and K. J. Goldman. An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 49--60, 2006.
• 11: F. Chudak, M. X. Goemans, and D. S. Hochbaum. A primal-dual interpretation of recent 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operations Research Letter, 22:111--118, 1998.
• 12: K. L. Clarkson. A modification of the greedy algorithm for vertex cover. Information Processing Letters, 16(1): 23--25, 1983.
• 13: E. G. Coffman, M. R. Garey, D. S. Johnson, and A. S. LaPaugh. Scheduling file transfers. SIAM Journal on Computing, 14(3):744--780, 1985.
• 14: William J. Cook , William H. Cunningham , William R. Pulleyblank , Alexander Schrijver, Combinatorial optimization, John Wiley & Sons, Inc., New York, NY, 1998
• 15: R. Gandhi and J. Mestre. Combinatorial algorithms for data migration to minimize average completion time. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 128--139, 2006.
• 16: R. Gandhi, M. M. Halldórsson, G. Kortsarz, and H. Shachnai. Improved bounds for scheduling conflicting jobs with minsum criteria. In Proceedings of the 2nd Workshop on Approximation and Online Algorithms (WAOA), pages 68--82, 2004.
• 17: Rajiv Gandhi , Samir Khuller , Aravind Srinivasan, Approximation algorithms for partial covering problems, Journal of Algorithms, v.53 n.1, p.55-84, October 2004 [doi>10.1016/j.jalgor.2004.04.002]
• 18: Rajiv Gandhi , Magnús M. Halldórsson , Guy Kortsarz , Hadas Shachnai, Improved results for data migration and open shop scheduling, ACM Transactions on Algorithms (TALG), v.2 n.1, p.116-129, January 2006 [doi>10.1145/1125994.1126001]
• 19: Michel X. Goemans , David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 20: Joseph Hall , Jason Hartline , Anna R. Karlin , Jared Saia , John Wilkes, On algorithms for efficient data migration, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.620-629, January 07-09, 2001, Washington, D.C., United States
• 21: N. Immorlica, M. Mahdian, and V. S. Mirrokni. Cycle cover with short cycles. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 641--653, 2005.
• 22: Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003 [doi>10.1145/950620.950621]
• 23: Samir Khuller , Yoo-Ah Kim, Algorithms for Data Migration with Cloning, SIAM Journal on Computing, v.33 n.2, p.448-461, 2004 [doi>10.1137/S009753970342585X]
• 24: Yoo-Ah Kim, Data migration to minimize the total completion time, Journal of Algorithms, v.55 n.1, p.42-57, April 2005 [doi>10.1016/j.jalgor.2004.07.009]
• 25: Y.-A. Kim, S. Khuller, and A. Malekian. Improved algorithms for data migration. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 164--175, 2006.
• 26: D. Marx. Complexity results for minimum sum edge coloring. Unpublished Manuscript, 2004.
• 27: Takao Nishizeki , Kenichi Kashiwagi, On the 1.1 edge-coloring of multigraphs, SIAM Journal on Discrete Mathematics, v.3 n.3, p.391-410, Aug. 1990 [doi>10.1137/0403035]
• 28: Maurice Queyranne , Maxim Svirdenko, New and improved algorithms for minsum shop scheduling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.871-878, January 09-11, 2000, San Francisco, California, United States
• 29: D. P. Williamson. The primal dual method for approximation algorithms. Mathematical Programming, 91(3): 447--478, 2002.
• 30: D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov, and D. B. Shmoys. Short shop schedules. Operations Research, 45 (2):288--94, 1997.