{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T15:42:07Z","timestamp":1743003727992,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319266251"},{"type":"electronic","value":"9783319266268"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-26626-8_5","type":"book-chapter","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T04:08:43Z","timestamp":1449634123000},"page":"60-71","source":"Crossref","is-referenced-by-count":2,"title":["Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties"],"prefix":"10.1007","author":[{"given":"Yishui","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,9]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40, 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for \n                      \n                        \n                      \n                      $$k$$\n                      \n                        \n                          k\n                        \n                      \n                    -median and facility location problems. SIAM J. Comput. 33, 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413\u2013420 (1993)","journal-title":"Math. Program."},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1137\/S0895480196300522","volume":"13","author":"Y Bartal","year":"2000","unstructured":"Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13, 64\u201378 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for \n                      \n                        \n                      \n                      $$k$$\n                      \n                        \n                          k\n                        \n                      \n                    -median, and positive correlation in budgeted optimization. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 737\u2013756 (2015)","DOI":"10.1137\/1.9781611973730.50"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys D.B.: A constant-factor approximation algorithm for the \n                      \n                        \n                      \n                      $$k$$\n                      \n                        \n                          k\n                        \n                      \n                    -median problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"5_CR7","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642\u2013651 (2001)"},{"key":"5_CR8","unstructured":"Gupta, N., Gupta, S.: Approximation algorithms for capacitated facility location problem with penalties (2014). \n                      ArXiv: 1408.4944"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-31594-7","volume-title":"Automata, Languages, and Programming","author":"A Czumaj","year":"2012","unstructured":"Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R.: A dependent LP-rounding approach for the k-median problem. In: Charikar, M., Li, S. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 194\u2013205. Springer, Heidelberg (2012)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM. 50, 795\u2013824 (2003)","journal-title":"J. ACM."},{"key":"5_CR11","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 \n                      \n                        \n                      \n                      $$k$$\n                      \n                        \n                          k\n                        \n                      \n                    -median problems using the primal-dual schema and Lagrangian relaxation. J. ACM. 48, 274\u2013296 (2001)","journal-title":"J. ACM."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Y Li","year":"2015","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica 73, 460\u2013482 (2015)","journal-title":"Algorithmica"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-012-0303-z","volume":"16","author":"D Shabtay","year":"2013","unstructured":"Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16, 3\u201328 (2013)","journal-title":"J. Sched."},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.tcs.2007.05.024","volume":"384","author":"P Zhang","year":"2007","unstructured":"Zhang, P.: A new approximation algorithm for the \n                      \n                        \n                      \n                      $$k$$\n                      \n                        \n                          k\n                        \n                      \n                    -facility location problem. Theor. Comput. Sci. 384, 126\u2013135 (2007)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26626-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T17:05:28Z","timestamp":1559322328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26626-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319266251","9783319266268"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26626-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}