{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:57:36Z","timestamp":1649120256605},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,3,2]],"date-time":"2012-03-02T00:00:00Z","timestamp":1330646400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00453-012-9633-7","type":"journal-article","created":{"date-parts":[[2012,3,1]],"date-time":"2012-03-01T23:06:39Z","timestamp":1330643199000},"page":"187-210","source":"Crossref","is-referenced-by-count":0,"title":["Donation Center Location Problem"],"prefix":"10.1007","volume":"66","author":[{"given":"Chien-Chung","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zoya","family":"Svitkina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,3,2]]},"reference":[{"key":"9633_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-540-30551-4_3","volume-title":"Proceedings of the 15th International Symposium on Algorithms and Computation","author":"D. Abraham","year":"2004","unstructured":"Abraham, D., Cechl\u00e1rov\u00e1, K., Manlove, D., Mehlhorn, K.: Pareto optimality in house allocation problems. In: Proceedings of the 15th International Symposium on Algorithms and Computation, pp. 3\u201315 (2004)"},{"issue":"4","key":"9633_CR2","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1137\/06067328X","volume":"37","author":"D. Abraham","year":"2007","unstructured":"Abraham, D., Irving, R., Mehlhorn, K., Telikepalli, K.: Popular matchings. SIAM J. Comput. 37(4), 1030\u20131045 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"9633_CR3","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"A.A. Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl. Math. 93(2\u20133), 149\u2013156 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9633_CR4","first-page":"74","volume-title":"Proceedings of the 24th Annual IEEE Conference on Computational Complexity","author":"P. Austrin","year":"2009","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pp. 74\u201380 (2009)"},{"key":"9633_CR5","first-page":"267","volume-title":"Proceedings of 18th Southeast Conference on Combinatorics, Graph Theory, and Computing","author":"D.G. Corneil","year":"1987","unstructured":"Corneil, D.G., Kamula, P.A.: Extensions of permutation and interval graphs. In: Proceedings of 18th Southeast Conference on Combinatorics, Graph Theory, and Computing, pp. 267\u2013276 (1987)"},{"issue":"1","key":"9633_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I. Dagan","year":"1988","unstructured":"Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discrete Appl. Math. 21(1), 35\u201346 (1988)","journal-title":"Discrete Appl. Math."},{"key":"9633_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5355-6","volume-title":"Facility Location: A Survey of Applications and Methods","author":"Z. Drezner","year":"1995","unstructured":"Drezner, Z.: Facility Location: A Survey of Applications and Methods. Springer, Berlin (1995)"},{"key":"9633_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230140102","volume":"14","author":"S. Even","year":"1984","unstructured":"Even, S., Goldreich, O., Moran, S., Tong, P.: On the NP-completeness of certain network testing problems. Networks 14, 1\u201324 (1984)","journal-title":"Networks"},{"issue":"4","key":"9633_CR9","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"9633_CR10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0166-218X(96)00013-3","volume":"74","author":"S. Felsner","year":"1997","unstructured":"Felsner, S., Muller, R., Wernisch, L.: Trapezoid graphs and generalizations, geometry and algorithms. Discrete Appl. Math. 74(1), 13\u201332 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9633_CR11","first-page":"66","volume-title":"Seventh Workshop on Analytic Algorithmics and Combinatorics","author":"L.K. Fleischer","year":"2010","unstructured":"Fleischer, L.K., Svitkina, Z.: Preference-constrained oriented matching. In: Seventh Workshop on Analytic Algorithmics and Combinatorics, pp. 66\u201373 (2010)"},{"issue":"1","key":"9633_CR12","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D. Gale","year":"1962","unstructured":"Gale, D., Shapley, L.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"9633_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9633_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2212\u03f5 . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"4","key":"9633_CR15","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1145\/1198513.1198520","volume":"2","author":"R. Irving","year":"2006","unstructured":"Irving, R., Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Rank-maximal matchings. ACM Trans. Algorithms 2(4), 602\u2013610 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"9633_CR16","first-page":"492","volume-title":"Proceedings of the 14th Annual European Symposium on Algorithms","author":"D. Manlove","year":"2006","unstructured":"Manlove, D., Sng, C.: Popular matchings in the capacitated house allocation problem. In: Proceedings of the 14th Annual European Symposium on Algorithms, pp. 492\u2013503 (2006)"},{"issue":"1\u20133","key":"9633_CR17","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R. McConnell","year":"1999","unstructured":"McConnell, R., Spinrad, J.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"9633_CR18","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1007\/11786986_62","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming","author":"J. Mestre","year":"2006","unstructured":"Mestre, J.: Weighted popular matchings. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, pp. 715\u2013726 (2006)"},{"issue":"1\u20132","key":"9633_CR19","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.tcs.2007.08.004","volume":"389","author":"D. Michail","year":"2007","unstructured":"Michail, D.: Reducing rank-maximal to maximum weight matching. Theor. Comput. Sci. 389(1\u20132), 125\u2013132 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9633_CR20","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1109\/SFCS.2001.959907","volume-title":"Proceedings of the 42nd Annual Symposium on Foundations of Computer Science","author":"M. Pal","year":"2001","unstructured":"Pal, M., Tardos, E., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 329\u2013338 (2001)"},{"key":"9633_CR21","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.A.: Optimization, approximation, and complexity classes. J.\u00a0Comput. Syst. Sci. 43, 425\u2013440 (1991)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9633_CR22","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D. Shmoys","year":"2000","unstructured":"Shmoys, D.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) Approximation Algorithms for Combinatorial Optimization, pp. 27\u201333. Springer, Berlin (2000)"},{"issue":"1","key":"9633_CR23","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"L. Stockmeyer","year":"1982","unstructured":"Stockmeyer, L., Vazirani, V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"key":"9633_CR24","first-page":"453","volume-title":"Proceedings on 33rd Annual ACM Symposium on Theory of Computing","author":"L. Trevisan","year":"2001","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pp. 453\u2013461 (2001)"},{"key":"9633_CR25","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"},{"issue":"2","key":"9633_CR26","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J. Zhang","year":"2005","unstructured":"Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30(2), 389\u2013403 (2005)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9633-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9633-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9633-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,24]],"date-time":"2019-06-24T19:52:31Z","timestamp":1561405951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9633-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,2]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9633"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9633-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,2]]}}}