{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:48:53Z","timestamp":1743155333985,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_34","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"463-476","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Residual Approximation in Solution Extension Problems"],"prefix":"10.1007","author":[{"given":"Mathias","family":"Weller","sequence":"first","affiliation":[]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[]},{"given":"Jean-Claude","family":"K\u00f6nig","sequence":"additional","affiliation":[]},{"given":"Valentin","family":"Pollet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"issue":"1\u20132","key":"34_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0167-6377(98)00046-7","volume":"24","author":"S Anily","year":"1999","unstructured":"Anily, S., Bramel, J., Hertz, A.: A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems. Oper. Res. Lett. 24(1\u20132), 29\u201335 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"34_CR2","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/(SICI)1097-0037(199707)29:4<205::AID-NET3>3.0.CO;2-J","volume":"29","author":"EM Arkin","year":"1997","unstructured":"Arkin, E.M., Hassin, R., Klein, L.: Restricted delivery problems on a network. Networks 29(4), 205\u2013216 (1997)","journal-title":"Networks"},{"issue":"3","key":"34_CR3","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s00224-005-1140-7","volume":"38","author":"A Avidor","year":"2005","unstructured":"Avidor, A., Zwick, U.: Approximating MIN 2-SAT and MIN 3-SAT. Theory Comput. Syst. 38(3), 329\u2013345 (2005). ISSN 1433\u20130490","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"34_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"34_CR5","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"1\u20133","key":"34_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M., Tuza, Z.: Precoloring extension. i. interval graphs. Discrete Math. 100(1\u20133), 267\u2013279 (1992)","journal-title":"Discrete Math."},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In Proceedings of 23rd SODA, pp. 1747\u20131753 (2012)","DOI":"10.1137\/1.9781611973099.139"},{"key":"34_CR8","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. TR 388, Graduate School of Industrial Administration. Carnegie Mellon University (1976)"},{"key":"34_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"4","key":"34_CR10","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1287\/opre.45.4.639","volume":"45","author":"M Gendreau","year":"1997","unstructured":"Gendreau, M., Laporte, G., Hertz, A.: An approximation algorithm for the traveling salesman problem with backhauls. Oper. Res. 45(4), 639\u2013641 (1997)","journal-title":"Oper. Res."},{"issue":"4","key":"34_CR11","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"34_CR12","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01758838","volume":"8","author":"D Gusfield","year":"1992","unstructured":"Gusfield, D., Pitt, L.: A bounded approximation for the minimum cost 2-SAT problem. Algorithmica 8(2), 103\u2013117 (1992)","journal-title":"Algorithmica"},{"issue":"4","key":"34_CR13","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s004530010045","volume":"28","author":"N Guttmann-Beck","year":"2000","unstructured":"Guttmann-Beck, N., Hassin, R., Khuller, S., Raghavachari, B.: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28(4), 422\u2013437 (2000)","journal-title":"Algorithmica"},{"issue":"1","key":"34_CR14","first-page":"1","volume":"62","author":"M Hujter","year":"1993","unstructured":"Hujter, M., Tuza, Z.: Precoloring extension. ii. graphs classes related to bipartite graphs. Acta Math. Univ. Comenian. (N.S.) 62(1), 1\u201311 (1993)","journal-title":"Acta Math. Univ. Comenian. (N.S.)"},{"issue":"6","key":"34_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0020-0190(92)90161-N","volume":"41","author":"K Jansen","year":"1992","unstructured":"Jansen, K.: An approximation algorithm for the general routing problem. Inf. Process. Lett. 41(6), 333\u2013339 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"34_CR16","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/s00453-013-9827-7","volume":"71","author":"M Knauer","year":"2015","unstructured":"Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4), 797\u2013811 (2015)","journal-title":"Algorithmica"},{"issue":"6","key":"34_CR17","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1016\/j.dam.2005.10.008","volume":"154","author":"D Marx","year":"2006","unstructured":"Marx, D.: Precoloring extension on unit interval graphs. Discrete Appl. Math. 154(6), 995\u20131002 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"34_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1002\/net.3230040105","volume":"4","author":"CS Orloff","year":"1974","unstructured":"Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4(1), 35\u201364 (1974)","journal-title":"Networks"},{"key":"34_CR19","unstructured":"Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Proceedings of 11th SODA, pp. 770\u2013779 (2000)"},{"key":"34_CR20","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"D Simchi-Levi","year":"1994","unstructured":"Simchi-Levi, D.: New worst-case results for the bin packing problem. Naval Res. Logist. 41, 579\u2013585 (1994)","journal-title":"Naval Res. Logist."},{"issue":"Suppl. 14","key":"34_CR21","doi-asserted-by":"publisher","first-page":"S2","DOI":"10.1186\/1471-2105-16-S14-S2","volume":"16","author":"M Weller","year":"2015","unstructured":"Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(Suppl. 14), S2 (2015)","journal-title":"BMC Bioinform."},{"key":"34_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-26626-8_30","volume-title":"Combinatorial Optimization and Applications","author":"M Weller","year":"2015","unstructured":"Weller, M., Chateau, A., Giroudeau, R.: On the complexity of scaffolding problems: from cliques to sparse graphs. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 409\u2013423. Springer, Heidelberg (2015). doi:\n                      10.1007\/978-3-319-26626-8_30"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:19:28Z","timestamp":1558477168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conference.cs.cityu.edu.hk\/cocoa2016\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}