{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:57Z","timestamp":1787340417678,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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 for any k and $k'$, $k&lt;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 [R. R. Mettu and C. G. Plaxton, SIAM J. Comput., 32 (2003), pp. 816\u2013832]) 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 get either 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 [C. G. Plaxton, J. Comput. System Sci., 72 (2006), pp. 425\u2013443].<\/jats:p>","DOI":"10.1137\/070698257","type":"journal-article","created":{"date-parts":[[2010,11,5]],"date-time":"2010-11-05T20:13:40Z","timestamp":1288988020000},"page":"3633-3669","source":"Crossref","is-referenced-by-count":28,"title":["A General Approach for Incremental Approximation and Hierarchical Clustering"],"prefix":"10.1137","volume":"39","author":[{"given":"Guolong","family":"Lin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chandrashekhar","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,11,4]]},"reference":[{"key":"R1","unstructured":"O. Amini, F. V. Fomin, and S. Saurabh,\n                      Implicit branching and parameterized partial cover problems (extended abstract)\n                      , in Proceedings of FSTTCS, IARCS, Chennai, India, 2008, pp. 1\u201312."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/07068151X"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"R4","unstructured":"R. Bar-Yehuda,\n                      Using homogenous weights for approximating the partial cover problem\n                      , in Proceedings of ACM-SIAM SODA, ACM, New York, SIAM, Philadelphia, 1999, pp. 71\u201375."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00434-9"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, P. Raghavan, and M. Sudan,\n                      The minimum latency problem\n                      , in Proceedings of ACM STOC, ACM, New York, 1994, pp. 163\u2013171.","DOI":"10.1145\/195058.195125"},{"key":"R7","unstructured":"A. Borodin and R. El-Yaniv,\n                      Online Computation and Competitive Analysis\n                      , Cambridge University Press, Cambridge, UK, 1998."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty and L. Burroughs,\n                      Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem\n                      , in STACS, Lecture Notes in Comput. Sci. 1373, Springer, Berlin, 1998, pp. 298\u2013308.","DOI":"10.1007\/BFb0028569"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. Byrka,\n                      An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem\n                      , Report PNA-E0611, CWI, 2006.","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418498"},{"key":"R11","unstructured":"M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan,\n                      Algorithms for facility location problems with outliers\n                      , in Proceedings of ACM-SIAM SODA, ACM, New York, SIAM, Philadelphia, pp. 642\u2013651."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9005-x"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.09.009"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.12.001"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.006"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0330"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Fiat and G. J. Woeginger, eds.\n                      Online Algorithms: The State of the Art\n                      , Springer, Berlin, 1998.","DOI":"10.1007\/BFb0029561"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Gandhi, S. Khuller, and A. Srinivasan,\n                      Approximation algorithms for partial covering problems\n                      , in Proceedings of ICALP, Crete, Greece, 2001, pp. 225\u2013236.","DOI":"10.1007\/3-540-48224-5_19"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"N. Garg,\n                      \n                        Saving an epsilon: A 2-approximation for the\n                        k\n                        -MST problem in graphs\n                      \n                      , in Proceedings of ACM-SIAM STOC, ACM, New York, SIAM, Philadelphia, 2005, pp. 396\u2013402.","DOI":"10.1145\/1060590.1060650"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585867"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"A. Gupta, M. Pal, R. Ravi, and A. Sinha,\n                      Boosted sampling: Approximation algorithms for stochastic optimization\n                      , in Proceedings of ACM STOC, ACM, New York, 2004, pp. 417\u2013426.","DOI":"10.1145\/1007352.1007419"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0237"},{"key":"R26","unstructured":"J. Hartline and A. Sharp,\n                      Hierarchical flow\n                      , in Proceedings of INOC, Lisbon, Portugal, 2005, pp. 681\u2013687."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"D. Hochbaum,\n                      \n                        The\n                        t\n                        -vertex cover problem: Extending the half integrality framework with budget constraints\n                      \n                      , in Proceedings of APPROX, Aalborg, Denmark, 1998, pp. 111\u2013122.","DOI":"10.1007\/BFb0053968"},{"key":"R29","unstructured":"D. S. Hochbaum, ed.\n                      Approximation Algorithms for NP-hard Problems\n                      , PWS Publishing Company, Boston, MA, 1995."},{"key":"R30","unstructured":"N. Immorlica, D. Karger, M. Minkoff, and V. Mirrokni,\n                      On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems\n                      , in Proceedings of ACM-SIAM SODA, ACM, New York, SIAM, Philadelphia, 2004, pp. 691\u2013700."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"L. Jia, G. Lin, G. Noubir, R. Rajaraman, and R. Sundaram,\n                      Universal approximations for TSP, Steiner Tree, and Set Cover\n                      , in Proceedings of ACM STOC, ACM, New York, 2005, pp. 386\u2013395.","DOI":"10.1145\/1060590.1060649"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"J.H. Lin and J. S. Vitter,\n                      $\\varepsilon$-approximations with minimum packing constraint violation\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"J. Mestre,\n                      A primal-dual approximation algorithm for partial vertex cover: Making educated guesses\n                      , in Proceedings of RANDOM-APPROX, Berkeley, CA, 2005, pp. 182\u2013191.","DOI":"10.1007\/11538462_16"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.09.004"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194266331"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00182-8"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R41","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer-Verlag, New York, 2001."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070698257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:09Z","timestamp":1787337249000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070698257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":41,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070698257"],"URL":"https:\/\/doi.org\/10.1137\/070698257","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}