{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:04Z","timestamp":1759639084916,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T00:00:00Z","timestamp":1474243200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["11371001, 11531014"],"award-info":[{"award-number":["11371001, 11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["283106"],"award-info":[{"award-number":["283106"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["11501412"],"award-info":[{"award-number":["11501412"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s10878-016-0080-2","type":"journal-article","created":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T15:12:24Z","timestamp":1474297944000},"page":"264-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["An approximation algorithm for k-facility location problem with linear penalties using local search scheme"],"prefix":"10.1007","volume":"36","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":[[2016,9,19]]},"reference":[{"key":"80_CR1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer A, Bateni M, Hajiaghayi M, Karloff H (2011) Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J Comput 40:309\u2013332","journal-title":"SIAM J Comput"},{"key":"80_CR2","doi-asserted-by":"crossref","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 (2004) Local search heuristics for \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -median and facility location problems. SIAM J Comput 33:544\u2013562","journal-title":"SIAM J Comput"},{"key":"80_CR3","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock D, Goemans MX, Simchi-Levi D, Williamson D (1993) A note on the prize collecting traveling salesman problem. Math Program 59:413\u2013420","journal-title":"Math Program"},{"key":"80_CR4","doi-asserted-by":"crossref","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 (2000) Multiprocessor scheduling with rejection. SIAM J Discret Math 13:64\u201378","journal-title":"SIAM J Discret Math"},{"key":"80_CR5","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar M, Guha S (2005) Improved combinatorial algorithms for facility location problems. SIAM J Comput 34:803\u2013824","journal-title":"SIAM J Comput"},{"key":"80_CR6","unstructured":"Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp 642\u2013651"},{"key":"80_CR7","unstructured":"Gupta N, Gupta S (2014) Approximation algorithms for capacitated facility location problem with penalties. CoRR, abs\/1408.4944v4"},{"key":"80_CR8","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1007\/s00453-011-9547-9","volume":"63","author":"M Hajiaghayi","year":"2012","unstructured":"Hajiaghayi M, Khandekar R, Kortsarz G (2012) Local search algorithms for the red-blue median problem. Algorithmica 63:795\u2013814","journal-title":"Algorithmica"},{"key":"80_CR9","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Heuristics for the fixed cost median problem. Math Program 22:148\u2013162","journal-title":"Math Program"},{"key":"80_CR10","doi-asserted-by":"crossref","unstructured":"Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. In: Proceedings of STOC, pp 731\u2013740","DOI":"10.1145\/509907.510012"},{"key":"80_CR11","doi-asserted-by":"crossref","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 VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795\u2013824","journal-title":"J ACM"},{"key":"80_CR12","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48:274\u2013296","journal-title":"J ACM"},{"key":"80_CR13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","volume":"222","author":"S Li","year":"2013","unstructured":"Li S (2013) A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf Comput 222:45\u201358","journal-title":"Inf Comput"},{"key":"80_CR14","doi-asserted-by":"crossref","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 (2015) Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica 73:460\u2013482","journal-title":"Algorithmica"},{"key":"80_CR15","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10951-012-0303-z","volume":"16","author":"D Shabtay","year":"2013","unstructured":"Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3\u201328","journal-title":"J Sched"},{"key":"80_CR16","doi-asserted-by":"crossref","unstructured":"Wang Y, Xu D, Du D, Wu C (2015) Local search algorithms for k-median and k-facility location problems with linear penalties. In: Proceedings of COCOA, pp 60\u201371","DOI":"10.1007\/978-3-319-26626-8_5"},{"key":"80_CR17","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.tcs.2007.05.024","volume":"384","author":"P Zhang","year":"2007","unstructured":"Zhang P (2007) A new approximation algorithm for the \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -facility location problem. Theor Comput Sci 384:126\u2013135","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-0080-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0080-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0080-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T12:20:22Z","timestamp":1528201222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-0080-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,19]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["80"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-0080-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2016,9,19]]}}}