{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T22:39:29Z","timestamp":1769726369542,"version":"3.49.0"},"publisher-location":"Cham","reference-count":50,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319711461","type":"print"},{"value":"9783319711478","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-71147-8_23","type":"book-chapter","created":{"date-parts":[[2017,11,15]],"date-time":"2017-11-15T13:33:21Z","timestamp":1510752801000},"page":"333-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach"],"prefix":"10.1007","author":[{"given":"Eric","family":"Angel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nguyen Kim","family":"Thang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shikha","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,16]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proceedings of the 23rd Symposium on Discrete Algorithms, pp. 1228\u20131241 (2012)","DOI":"10.1137\/1.9781611973099.97"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Lucarelli, G., Thang, N.K.: Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow time problems. In: Proceedings of the 23rd European Symposium on Algorithms, pp. 35\u201346 (2015)","DOI":"10.1007\/978-3-662-48350-3_4"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/3-540-61422-2_127","volume-title":"Algorithm Theory \u2014 SWAT\u201996","author":"Y Asahiro","year":"1996","unstructured":"Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 136\u2013148. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61422-2_127"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $${O}(n^{1\/4})$$ approximation for densest k-subgraph. In: Proceedings of the 42nd Symposium on Theory of Computing, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"issue":"1","key":"23_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/s00453-007-9142-2","volume":"55","author":"B Birnbaum","year":"2009","unstructured":"Birnbaum, B., Goldman, K.J.: An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica 55(1), 42\u201359 (2009)","journal-title":"Algorithmica"},{"issue":"3","key":"23_CR6","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A Blum","year":"1994","unstructured":"Blum, A.: New approximation algorithms for graph coloring. J. ACM 41(3), 470\u2013516 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"23_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A Blum","year":"1997","unstructured":"Blum, A., Karger, D.: An \u00f5 (n314)-coloring algorithm for 3-colorable graphs. Inf. Process. Lett. 61(1), 49\u201353 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"23_CR8","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. J. Comput. Syst. Sci. 50(2), 244\u2013258 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Charikar, M., Raghavachari, B.: The finite capacity dial-a-ride problem. In: Proceedings of the 39th Symposium on Foundations of Computer Science, pp. 458\u2013467 (1998)","DOI":"10.1109\/SFCS.1998.743496"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Choudhury, A.R., Das, S., Garg, N., Kumar, A.: Rejecting jobs to minimize load and maximum flow-time. In: Proceedings of the 26th Symposium on Discrete Algorithms, pp. 1114\u20131133 (2015)","DOI":"10.1137\/1.9781611973730.75"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-msts and k-steiner trees via the primal-dual method and lagrangean relaxation. In: Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pp. 60\u201370 (2001)","DOI":"10.1007\/3-540-45535-3_5"},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-78773-0_20","volume-title":"LATIN 2008: Theoretical Informatics","author":"C Chung","year":"2008","unstructured":"Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: on the exponential boost of one extra server. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 228\u2013239. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78773-0_20"},{"key":"23_CR13","unstructured":"Daniely, A., Linial, N., Saks, M.: Clustering is difficult only when it does not matter. arXiv preprint arXiv:1205.4891 (2012)"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Huang, Z.: Primal dual gives almost optimal energy efficient online algorithms. In: Proceedings of the 25th Symposium on Discrete Algorithms (2014)","DOI":"10.1137\/1.9781611973402.83"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, pp. 427\u2013438 (2009)","DOI":"10.1007\/978-3-642-02927-1_36"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set cover (preliminary version). In: Proceedings of the 28th Symposium on Theory of Computing, pp. 314\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"issue":"2","key":"23_CR17","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174\u2013211 (2001)","journal-title":"J. Algorithms"},{"issue":"3","key":"23_CR18","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: Proceedings of the 17th Symposium on Foundations of Computer Science, pp. 216\u2013227 (1976)","DOI":"10.1109\/SFCS.1976.6"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proceedings of the 37th Symposium on Foundations of Computer Science, pp. 302\u2013309 (1996)","DOI":"10.1109\/SFCS.1996.548489"},{"issue":"2","key":"23_CR21","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"23_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1721837.1721857","volume":"6","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Hajiaghayi, M., Nagarajan, V., Ravi, R.: Dial a ride from k-forest. ACM Trans. Algorithm 6(2), 41 (2010)","journal-title":"ACM Trans. Algorithm"},{"issue":"4","key":"23_CR23","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th Symposium on Discrete Algorithm, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Im, S., Kulkarni, J., Munagala, K.: Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In: Proceedings of the 46th Symposium on Theory of Computing (2014)","DOI":"10.1145\/2591796.2591814"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Im, S., Kulkarni, J., Munagala, K.: Competitive flow time algorithms for polyhedral scheduling. In: Proceedings of the 56th Symposium on Foundations of Computer Science, pp. 506\u2013524 (2015)","DOI":"10.1109\/FOCS.2015.38"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Im, S., Kulkarni, J., Munagala, K., Pruhs, K.: Selfishmigrate: a scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In: Proceedings of the 55th Symposium on Foundations of Computer Science (2014)","DOI":"10.1109\/FOCS.2014.63"},{"issue":"1","key":"23_CR28","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"issue":"2","key":"23_CR29","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"23_CR30","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"23_CR31","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"key":"23_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/3-540-60313-1_165","volume-title":"Algorithms \u2014 ESA \u201995","author":"B Kalyanasundaram","year":"1995","unstructured":"Kalyanasundaram, B., Pruhs, K.R.: The online transportation problem. In: Spirakis, P. (ed.) ESA 1995. LNCS, vol. 979, pp. 484\u2013493. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60313-1_165"},{"issue":"4","key":"23_CR33","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"23_CR34","volume-title":"Approximation Algorithms for NP-Hard Optimization Problems","author":"PN Klein","year":"2010","unstructured":"Klein, P.N., Young, N.E.: Approximation Algorithms for NP-Hard Optimization Problems. Chapman & Hall, Boca Raton (2010)"},{"issue":"4","key":"23_CR35","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann, J., Parekh, O., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489\u2013509 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"23_CR36","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"key":"23_CR37","unstructured":"Lucarelli, G., Thang, N.K., Srivastav, A., Trystram, D.: Online non-preemptive scheduling in a resource augmentation model based on duality. In: Proceedings of the 24th European Symposium on Algorithms (2016)"},{"issue":"5","key":"23_CR38","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"23_CR39","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $${O}(\\sqrt{|V|} |{E}|)$$ algorithm for finding maximum matching in general graphs. In: Proceedigs of the 21st Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"3","key":"23_CR40","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10601-008-9064-x","volume":"14","author":"O Ohrimenko","year":"2009","unstructured":"Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation via lazy clause generation. Constraints 14(3), 357\u2013391 (2009)","journal-title":"Constraints"},{"key":"23_CR41","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $${O}(nm)$$ time, or better. In: Proceedigns of the 45th ACM Symposium on Theory of Computing, pp. 765\u2013774. ACM (2013)","DOI":"10.1145\/2488608.2488705"},{"issue":"2","key":"23_CR42","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2), 163\u2013200 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"23_CR43","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-008-9189-8","volume":"56","author":"D Segev","year":"2010","unstructured":"Segev, D., Segev, G.: Approximate k-steiner forests via the lagrangian relaxation technique with internal preprocessing. Algorithmica 56(4), 529\u2013549 (2010)","journal-title":"Algorithmica"},{"key":"23_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BFb0053974","volume-title":"Approximation Algorithms for Combinatiorial Optimization","author":"A Srivastav","year":"1998","unstructured":"Srivastav, A., Wolf, K.: Finding dense subgraphs with semidefinite programming. In: Jansen, K., Rolim, J. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 181\u2013191. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0053974"},{"key":"23_CR45","doi-asserted-by":"crossref","unstructured":"Thang, N.K.: Lagrangian duality in online scheduling with resource augmentation and speed scaling. In: Proceedigns of the 21st European Symposium on Algorithms, pp. 755\u2013766 (2013)","DOI":"10.1007\/978-3-642-40450-4_64"},{"key":"23_CR46","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. In: 1989 30th Annual Symposium on Foundations of Computer Science, pp. 338\u2013343. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63500"},{"key":"23_CR47","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2013)"},{"issue":"4","key":"23_CR48","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A Wigderson","year":"1983","unstructured":"Wigderson, A.: Improving the performance guarantee for approximate graph coloring. J. ACM 30(4), 729\u2013735 (1983)","journal-title":"J. ACM"},{"key":"23_CR49","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"issue":"1","key":"23_CR50","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"NE Young","year":"2000","unstructured":"Young, N.E.: On-line paging against adversarially biased random inputs. J. Algorithms 37(1), 218\u2013235 (2000)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71147-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T01:01:10Z","timestamp":1750986070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-71147-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319711461","9783319711478"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71147-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"16 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/anl.sjtu.edu.cn\/cocoa2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}