A general approach for incremental approximation and hierarchical clustering

ABSTRACT

We present a general framework and algorithmic approach for incremental approximation algorithms. The framework handles cardinality constrained minimization problems, such as the k-median and k-MST problems. Given some notion of ordering on solutions of different cardinalities k, we give solutions for all values of k such that the solutions respect the ordering and such that for any k, our solution is close in value to the value of an optimal solution of cardinality k. For instance, for the k-median problem, the notion of ordering is set inclusion and our incremental algorithm produces solutions such that any k and k', k < k', our solution of size k is a subset of our solution of size k'. We show that our framework applies to this incremental version of the k-median problem (introduced by Mettu and Plaxton [30]), and incremental versions of the k-MST problem, k-vertex cover problem, k-set cover problem, as well as the uncapacitated facility location problem (which is not cardinality-constrained). For these problems we either get new incremental algorithms, or improvements over what was previously known. We also show that the framework applies to hierarchical clustering problems. In particular, we give an improved algorithm for a hierarchical version of the k-median problem introduced by Plaxton [31].

REFERENCES

• 1: A. Archer, A. Levin, and D. P. Williamson. A faster, better approximation algorithm for the minimum latency problem. Technical Report 1362, Cornell ORIE, 2003. Available at http://www.orie.cornell.edu/~dpw/minlat.ps.
• 2: Aaron Archer , David P. Williamson, Faster approximation algorithms for the minimum latency problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , Kamesh Munagala , Vinayaka Pandit, Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal on Computing, v.33 n.3, p.544-562, 2004 [doi>10.1137/S0097539702416402]
• 4: Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: Nader H. Bshouty , Lynn Burroughs, Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.298-308, February 25-27, 1998
• 7: Moses Charikar , Chandra Chekuri , Tomas Feder , Rajeev Motwani, Incremental Clustering and Dynamic Information Retrieval, SIAM Journal on Computing, v.33 n.6, p.1417-1440, 2004 [doi>10.1137/S0097539702418498]
• 8: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 9: M. Chrobak, C. Kenyon, J. Noga, and N. E. Young. Online medians via online bribery. http://www.arxiv.org/abs/cs.DS/0504103, Apr. 2005.
• 10: M. Chrobak, C. Kenyon, and N. Young. The reverse greedy algorithm for the metric k-median problem. In COCOON, pages 654--660, 2005. Journal version to appear in IPL.
• 11: Bruno Codenotti , Gianluca De Marco , Mauro Leoncini , Manuela Montangero , Massimo Santini, Approximation algorithms for a hierarchically structured bin packing problem, Information Processing Letters, v.89 n.5, p.215-221, 16 March 2004 [doi>10.1016/j.ipl.2003.12.001]
• 12: Sanjoy Dasgupta , Philip M. Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences, v.70 n.4, p.555-569, June 2005 [doi>10.1016/j.jcss.2004.10.006]
• 13: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 14: Developments from a June 1996 seminar on Online algorithms: the state of the art, January 1998
• 15: Rajiv Gandhi , Samir Khuller , Aravind Srinivasan, Approximation Algorithms for Partial Covering Problems, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.225-236, July 08-12, 2001
• 16: Naveen Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060650]
• 17: M. X. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111--124, 1998.
• 18: T. González. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293--306, 2005.
• 19: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 20: Anupam Gupta , R. Ravi , Amitabh Sinha, An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.218-227, October 17-19, 2004 [doi>10.1109/FOCS.2004.11]
• 21: J. Hartline and A. Sharp. Hierarchical flow. In INOC, pages 681--687, 2005.
• 22: Dorit S. Hochbaum, The t-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.111-122, July 18-19, 1998
• 23: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 24: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 25: 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]
• 26: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 27: Lujun Jia , Guolong Lin , Guevara Noubir , Rajmohan Rajaraman , Ravi Sundaram, Universal approximations for TSP, Steiner tree, and set cover, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060649]
• 28: Mohammad Mahdian , Yinyu Ye , Jiawei Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.229-242, September 17-21, 2002
• 29: J. Mestre. A primal-dual approximation algorithm for partial vertex cover: making educated guesses. In APPROX, 2005.
• 30: Ramgopal R. Mettu , C. Greg Plaxton, The Online Median Problem, SIAM Journal on Computing, v.32 n.3, p.816-832, 2003 [doi>10.1137/S0097539701383443]
• 31: C. Greg Plaxton, Approximation algorithms for hierarchical location problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780549]
• 32: Petr Slavík, Improved performance of the greedy algorithm for partial cover, Information Processing Letters, v.64 n.5, p.251-254, Dec. 15, 1997 [doi>10.1016/S0020-0190(97)00182-8]
• 33: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 34: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Theory