{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:04:10Z","timestamp":1761894250715},"publisher-location":"Berlin, Heidelberg","reference-count":19,"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_70","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T11:50:30Z","timestamp":1140177030000},"page":"769-780","source":"Crossref","is-referenced-by-count":10,"title":["Minimum Cost Source Location Problems with Flow Requirements"],"prefix":"10.1007","author":[{"given":"Mariko","family":"Sakashita","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoru","family":"Fujishige","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"70_CR1","unstructured":"Andreev, K., Garrod, C., Maggs, B.: Simultaneous source location, SCS Technical Report CMU-CS-03-162, Carnegie Mellon University, Pittsburgh"},{"key":"70_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/jagm.2001.1203","volume":"42","author":"K. Arata","year":"2002","unstructured":"Arata, K., Iwata, S., Makino, K., Fujishige, S.: Locating sources to meet flow demands in undirected networks. J. Algorithms\u00a042, 54\u201368 (2002)","journal-title":"J. Algorithms"},{"key":"70_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.orl.2004.07.005","volume":"33","author":"M. B\u00e1r\u00e1sz","year":"2005","unstructured":"B\u00e1r\u00e1sz, M., Becker, J., Frank, A.: An algorithm for source location in directed graphs. Operations Research Letters\u00a033, 221\u2013230 (2005)","journal-title":"Operations Research Letters"},{"key":"70_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"70_CR5","first-page":"480","volume":"E83-D","author":"T. Fujito","year":"2000","unstructured":"Fujito, T.: Approximation algorithms for submodular set cover with applications. IEICE Trans.\u00a0E83-D, 480\u2013487 (2000)","journal-title":"IEICE Trans."},{"key":"70_CR6","unstructured":"Goel, A., Estrin, D.: Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In: Proceedings of 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 499\u2013505 (2003)"},{"key":"70_CR7","volume-title":"Computers and Intractability: A Guide to the Theory NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory NP-Completeness. Freeman, New York (1979)"},{"key":"70_CR8","unstructured":"van den Heuvel, J., Johnson, M.: Transversals of subtree hypergraphs and the source location problem in digraphs, CDAM Research Report, LSE-CDAM-2004-10, London School of Economics"},{"key":"70_CR9","unstructured":"Ishii, T., Fujita, H., Nagamochi, H.: Minimum cost source location problem with local 3-vertex-connectivity requirements. In: Computing Theory: The Australian Theory Symposium, pp. 97\u2013105 (2005)"},{"key":"70_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1002\/net.10034","volume":"40","author":"H. Ito","year":"2002","unstructured":"Ito, H., Ito, M., Itatsu, Y., Uehara, H., Yokoyama, M.: Source location problems considering vertex-connectivity and edge-connectivity simultaneously. Networks\u00a040, 63\u201370 (2002)","journal-title":"Networks"},{"key":"70_CR11","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1080\/1055-6780309510593","volume":"18","author":"H. Ito","year":"2003","unstructured":"Ito, H., Makino, K., Arata, K., Honami, S., Itatsu, Y., Fujishige, S.: Source location problem with flow requirements in directed networks. Optimization Methods and Software\u00a018, 427\u2013435 (2003)","journal-title":"Optimization Methods and Software"},{"key":"70_CR12","first-page":"551","volume-title":"Handbooks in OR & MS","author":"M. Labbe","year":"1995","unstructured":"Labbe, M., Peeters, D., Thisse, J.-F.: Location on networks. In: Ball, M.O., et al. (eds.) Handbooks in OR & MS, vol.\u00a08, pp. 551\u2013624. North-Holland, Amsterdam (1995)"},{"key":"70_CR13","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\u00a041, 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"70_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0020-0190(01)00183-1","volume":"80","author":"H. Nagamochi","year":"2001","unstructured":"Nagamochi, H., Ishii, T., Ito, H.: Minimum cost source location problem with vertex-connectivity requirements in digraphs. Information Processing Letters\u00a080, 287\u2013294 (2001)","journal-title":"Information Processing Letters"},{"key":"70_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/11602613_9","volume-title":"Algorithms and Computation","author":"M. Sakashita","year":"2005","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimizing a monotone concave function with laminar covering constraints. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 71\u201381. Springer, Heidelberg (2005)"},{"key":"70_CR16","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimum cost source location problems with flow requirements (unpublished manuscript)"},{"key":"70_CR17","first-page":"1989","volume":"E73","author":"H. Tamura","year":"1990","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Location problems on undirected flow networks. IEICE Trans.\u00a0E73, 1989\u20131993 (1990)","journal-title":"IEICE Trans."},{"key":"70_CR18","first-page":"678","volume":"E75-A","author":"H. Tamura","year":"1992","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Some covering problems in location theory on flow networks. IEICE Trans.\u00a0E75-A, 678\u2013683 (1992)","journal-title":"IEICE Trans."},{"key":"70_CR19","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02, 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_70","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T06:57:52Z","timestamp":1552373872000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11682462_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}