{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:42Z","timestamp":1759637862267},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_30","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"354-366","source":"Crossref","is-referenced-by-count":11,"title":["Submodular Cost Allocation Problem and Applications"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"given":"Alina","family":"Ene","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (Extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"issue":"3","key":"30_CR2","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for multiway cut. Journal of Computer and System Sciences\u00a060(3), 564\u2013574 (2000), Preliminary version in STOC 1998","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Approximation algorithms for submodular multiway partition (April 2011) (manuscript)","DOI":"10.1109\/FOCS.2011.34"},{"issue":"4","key":"30_CR4","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM Journal on Computing\u00a023(4), 864\u2013894 (1994), Preliminary version in STOC 1992","journal-title":"SIAM Journal on Computing"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Delong, A., Osokin, A., Isack, H.N., Boykov, Y.: Fast approximate energy minimization with label costs. In: IEEE Computer Vision and Pattern Recognition (CVPR), pp. 2173\u20132180 (2010)","DOI":"10.1109\/CVPR.2010.5539897"},{"issue":"1-2","key":"30_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0020-0190(00)00065-X","volume":"75","author":"A. Freund","year":"2000","unstructured":"Freund, A., Karloff, H.J.: A lower bound of 8\/(7+(1\/k)-1) on the integrality ratio of the calinescu-karloff-rabani relaxation for multiway cut. Information Processing Letters\u00a075(1-2), 43\u201350 (2000)","journal-title":"Information Processing Letters"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-642-13036-6_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"T. Fukunaga","year":"2010","unstructured":"Fukunaga, T.: Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 15\u201328. Springer, Heidelberg (2010)"},{"issue":"1","key":"30_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N. Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. Journal of Algorithms\u00a050(1), 49\u201361 (2004), Preliminary version in ICALP 1994","journal-title":"Journal of Algorithms"},{"key":"30_CR9","unstructured":"Ge, D., Ye, Y., Zhang, J.: The Fixed-Hub Single Allocation Problem: A Geometric Rounding Approach (2007), preprint http:\/\/www.stanford.edu\/~yyye\/revisedHub.pdf"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with multi-agent submodular cost functions. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 755\u2013764 (2009)","DOI":"10.1109\/FOCS.2009.81"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Harvey, N.J.A., Iwata, S., Mirrokni, V.S.: Approximating submodular functions everywhere. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 535\u2013544 (2009)","DOI":"10.1137\/1.9781611973068.59"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 671\u2013680 (2009)","DOI":"10.1109\/FOCS.2009.31"},{"issue":"3","key":"30_CR13","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"D.R. Karger","year":"2004","unstructured":"Karger, D.R., Klein, P.N., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding of minimum multiway cut. Mathematics of Operations Research\u00a029(3), 436\u2013461 (2004), Preliminary version in STOC 1999","journal-title":"Mathematics of Operations Research"},{"issue":"5","key":"30_CR14","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1145\/585265.585268","volume":"49","author":"J.M. Kleinberg","year":"2002","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. Journal of the ACM (JACM)\u00a049(5), 616\u2013639 (2002), Preliminary version in FOCS 1999","journal-title":"Journal of the ACM (JACM)"},{"issue":"3","key":"30_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/net.3230030306","volume":"3","author":"E.L. Lawler","year":"1973","unstructured":"Lawler, E.L.: Cutsets and partitions of hypergraphs. Networks\u00a03(3), 275\u2013285 (1973)","journal-title":"Networks"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical Programming: The State of the Art, pp. 235\u2013257 (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica, 1\u201320 (2010), Preliminary version in ISAAC 2009","DOI":"10.1007\/978-3-642-10631-6_8"},{"issue":"1","key":"30_CR18","first-page":"3","volume":"82","author":"M. Queyranne","year":"1998","unstructured":"Queyranne, M.: Minimizing symmetric submodular functions. Mathematical Programming\u00a082(1), 3\u201312 (1998), Preliminary version in SODA 1995","journal-title":"Mathematical Programming"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"Svitkina, Z., Fleischer, L.: Submodular approximation: Sampling-based algorithms and lower bounds. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 697\u2013706 (2008)","DOI":"10.1109\/FOCS.2008.66"},{"key":"30_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-540-27821-4_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Z. Svitkina","year":"2004","unstructured":"Svitkina, Z., Tardos, \u00c9.: Min-max multiway cut. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 207\u2013218. Springer, Heidelberg (2004)"},{"issue":"2","key":"30_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721853","volume":"6","author":"Z. Svitkina","year":"2010","unstructured":"Svitkina, Z., Tardos, \u00c9.: Facility location with hierarchical facility costs. ACM Transactions on Algorithms (TALG)\u00a06(2), 1\u201322 (2010), Preliminary version in SODA 2006","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"30_CR22","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: ACM Symposium on Theory of Computing (STOC), pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"30_CR23","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Symmetry and Approximability of Submodular Maximization Problems. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 651\u2013670 (2010)","DOI":"10.1109\/FOCS.2009.24"},{"key":"30_CR24","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms (2010), preprint http:\/\/www.designofapproxalgs.com","DOI":"10.1017\/CBO9780511921735"},{"issue":"14-15","key":"30_CR25","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1016\/j.ipl.2010.05.003","volume":"110","author":"M. Xiao","year":"2010","unstructured":"Xiao, M.: Finding minimum 3-way cuts in hypergraphs. Information Processing Letters\u00a0110(14-15), 554\u2013558 (2010), Preliminary version in TAMC 2008","journal-title":"Information Processing Letters"},{"issue":"1","key":"30_CR26","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-004-0510-2","volume":"102","author":"L. Zhao","year":"2005","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: Greedy splitting algorithms for approximating multiway partition problems. Mathematical Programming\u00a0102(1), 167\u2013183 (2005)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T12:18:31Z","timestamp":1592655511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}