{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:59:42Z","timestamp":1725544782306},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540327554"},{"type":"electronic","value":"9783540327561"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_41","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T06:50:30Z","timestamp":1140159030000},"page":"435-446","source":"Crossref","is-referenced-by-count":10,"title":["Cut Problems in Graphs with a Budget Constraint"],"prefix":"10.1007","author":[{"given":"Roee","family":"Engelberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: Proc. of STOC 2004, pp. 222\u2013231 (2004)","key":"41_CR1","DOI":"10.1145\/1007352.1007355"},{"doi-asserted-by":"crossref","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: Proc. of STOC 2005, pp. 553\u2013562 (2005)","key":"41_CR2","DOI":"10.1145\/1060590.1060673"},{"doi-asserted-by":"crossref","unstructured":"Aura, T., Bishop, M., Sniegowski, D.: Analyzing single-server network inhibition. In: Proc. of CSFW 2000, pp. 108\u2013117 (2000)","key":"41_CR3","DOI":"10.1109\/CSFW.2000.856930"},{"issue":"3","key":"41_CR4","first-page":"564","volume":"60","author":"G. C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An Improved Approximation Algorithm for Multiway Cut. JCSS\u00a060(3), 564\u2013574 (2000)","journal-title":"JCSS"},{"unstructured":"Chawla, S., Gupta, A., R\u00e4cke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In: Proc. of SODA 2005, pp. 102\u2013111 (2005)","key":"41_CR5"},{"key":"41_CR6","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The Complexity of Multiterminal Cuts. SIAM J. on Computing\u00a023, 864\u2013894 (1994); Preliminary version appeared in Proc. of the 24th ACM Symposium on Theory of Computing, pp. 241\u2013251 (1992)","journal-title":"SIAM J. on Computing"},{"key":"41_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica\u00a018, 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"41_CR8","first-page":"551","volume":"9","author":"R. Gomory","year":"1961","unstructured":"Gomory, R., Hu, T.: Multiterminal network flows. J. of SIAM\u00a09, 551\u2013570 (1961)","journal-title":"J. of SIAM"},{"doi-asserted-by":"crossref","unstructured":"Harrelson, C., Hidrum, K., Rao, S.: A polynomial time tree decomposition to minimize congestion. In: Proc. of SPAA 2003, pp. 34\u201343 (2003)","key":"41_CR9","DOI":"10.1145\/777412.777419"},{"key":"41_CR10","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. of the ACM\u00a022, 463\u2013468 (1975)","journal-title":"J. of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. In: STOC 1999, pp. 668\u2013678 (1999)","key":"41_CR11","DOI":"10.1145\/301250.301430"},{"issue":"1","key":"41_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The Budgeted Maximum Coverage Problem. Information Processing Letters\u00a070(1), 39\u201345 (1999)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Minimizing congestion in general networks. In: FOCS 2002, pp. 43\u201352 (2002)","key":"41_CR13","DOI":"10.1109\/SFCS.2002.1181881"},{"key":"41_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H. Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. SIAM J. on Comp.\u00a024, 101\u2013108 (1995)","journal-title":"SIAM J. on Comp."},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M. Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters\u00a032, 41\u201343 (2004)","journal-title":"Operations Research Letters"},{"issue":"2","key":"41_CR16","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0166-218X(93)90006-A","volume":"43","author":"R.V. Vohra","year":"1993","unstructured":"Vohra, R.V., Hall, N.G.: A probabilistic analysis of the maximal covering location problem. Discrete Applied Mathematics\u00a043(2), 175\u2013183 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"41_CR17","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"L. Wolsey","year":"1982","unstructured":"Wolsey, L.: Maximizing real-valued submodular functions: primal and dual heuristics for location problems. Mathematics of Operations Research\u00a07, 410\u2013425 (1982)","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,11]],"date-time":"2018-10-11T12:43:17Z","timestamp":1539261797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11682462_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}