{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T04:20:00Z","timestamp":1775967600759,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540345978","type":"print"},{"value":"9783540345985","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11764298_4","type":"book-chapter","created":{"date-parts":[[2006,5,19]],"date-time":"2006-05-19T04:37:56Z","timestamp":1148013476000},"page":"36-48","source":"Crossref","is-referenced-by-count":10,"title":["An Incremental Model for Combinatorial Maximization Problems"],"prefix":"10.1007","author":[{"given":"Jeff","family":"Hartline","sequence":"first","affiliation":[]},{"given":"Alexa","family":"Sharp","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","first-page":"40","volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing","author":"C.G. Plaxton","year":"2003","unstructured":"Plaxton, C.G.: Approximation algorithms for hierarchical location problems. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 40\u201349. ACM Press, New York (2003)"},{"key":"4_CR2","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"R.R. Mettu","year":"2000","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Washington, DC, USA, IEEE Computer Society, Los Alamitos (2000)"},{"key":"4_CR3","unstructured":"Hartline, J., Sharp, A.: Hierarchical flow. In: Proceedings of the International Network Optimization Conference, pp. 681\u2013687 (2005)"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Lin, G., Nagarajan, C., Rajaraman, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (2006)","DOI":"10.1145\/1109557.1109684"},{"key":"4_CR5","first-page":"1467","volume-title":"Proceedings of IEEE Micron 2001","author":"Y. Fang","year":"2001","unstructured":"Fang, Y., Lou, W.: A multipath routing approach for secured data delivery. In: Proceedings of IEEE Micron 2001, pp. 1467\u20131473. IEEE Computer Society, Los Alamitos (2001)"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. Gonzalez","year":"1985","unstructured":"Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science\u00a038, 293\u2013306 (1985)","journal-title":"Theoretical Computer Science"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/3-540-45435-7_24","volume-title":"Proceedings of the 15th Annual Conference on Computational Learning Theory","author":"S. Dasgupta","year":"2002","unstructured":"Dasgupta, S.: Performance guarantees for hierarchical clustering. In: Proceedings of the 15th Annual Conference on Computational Learning Theory, pp. 351\u2013363. Springer, Heidelberg (2002)"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Hartline, J., Sharp, A.: An incremental model for combinatorial minimization. Submitted for publication (2006), Available at: www.cs.cornell.edu\/~asharp","DOI":"10.1007\/11764298_4"},{"key":"4_CR9","volume-title":"Online computation and competitive analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, New York (1998)"},{"key":"4_CR10","unstructured":"Online Algorithms, The State of the Art Online Algorithms. In: Fiat, A., Woeginger, G.J. (eds.) Dagstuhl Seminar 1996. LNCS, vol.\u00a01442, Springer, Heidelberg (1998)"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/0212014","volume":"12","author":"E.G. Coffman","year":"1983","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Dynamic bin packing. SIAM Journal on Computing\u00a012, 227\u2013258 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A. Gy\u00e1rf\u00e1s","year":"1988","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: Online and first-fit colorings of graphs. J. Graph Th.\u00a012, 217\u2013227 (1988)","journal-title":"J. Graph Th."},{"key":"4_CR13","first-page":"352","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 352\u2013358. ACM Press, New York (1990)"},{"key":"4_CR14","first-page":"417","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., et al.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 417\u2013426. ACM Press, New York (2004)"},{"key":"4_CR15","unstructured":"Immorlica, N., et al.: On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 691\u2013700 (2004)"},{"key":"4_CR16","unstructured":"Dean, B.C., Goemans, M.X., Vondrak, J.: Adaptivity and approximation for stochastic packing problems. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp. 395\u2013404 (2005)"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1109\/SFCS.1991.185411","volume-title":"Proceedings of the 32nd Annual Symposium on Foundations of Computer Science","author":"S.A. Plotkin","year":"1991","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pp. 495\u2013504. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"4_CR18","first-page":"300","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"N. Garg","year":"1998","unstructured":"Garg, N., Koenemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p. 300. IEEE Computer Society, Los Alamitos (1998)"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM\u00a022, 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research\u00a04, 339\u2013356 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H. Kuhn","year":"1955","unstructured":"Kuhn, H.: The hungarian method for the assignment problem. Naval Research Logistics Quarterly\u00a02, 83\u201397 (1955)","journal-title":"Naval Research Logistics Quarterly"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11764298_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:10:57Z","timestamp":1619493057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11764298_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540345978","9783540345985"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11764298_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}