{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:14:12Z","timestamp":1761293652176,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,11,12]],"date-time":"2017-11-12T00:00:00Z","timestamp":1510444800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10878-017-0202-5","type":"journal-article","created":{"date-parts":[[2017,11,12]],"date-time":"2017-11-12T03:07:16Z","timestamp":1510456036000},"page":"1195-1220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On residual approximation in solution extension problems"],"prefix":"10.1007","volume":"36","author":[{"given":"Mathias","family":"Weller","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4760-8171","authenticated-orcid":false,"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":[[2017,11,12]]},"reference":[{"key":"202_CR1","volume-title":"Network flows: theory, algorithms, and applications","author":"R Ahuja","year":"1993","unstructured":"Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Upper Saddle River"},{"issue":"1\u20132","key":"202_CR2","doi-asserted-by":"crossref","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 (1999) A 5\/3-approximation algorithm for the clustered traveling salesman tour and path problems. Oper Res Lett 24(1\u20132):29\u201335","journal-title":"Oper Res Lett"},{"key":"202_CR3","volume-title":"The traveling salesman problem","author":"DL Applegate","year":"2006","unstructured":"Applegate DL, Bixby RM, Chv\u00e1tal V, Cook WJ (2006) The traveling salesman problem. Princeton University Press, Princeton"},{"issue":"4","key":"202_CR4","doi-asserted-by":"crossref","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 EM, Hassin R, Klein L (1997) Restricted delivery problems on a network. Networks 29(4):205\u2013216","journal-title":"Networks"},{"key":"202_CR5","doi-asserted-by":"crossref","unstructured":"Avidor A, Zwick U (2005) Approximating MIN 2-SAT and MIN 3-SAT. Theory Comput Syst 38(3):329\u2013345. ISSN 1433-0490","DOI":"10.1007\/s00224-005-1140-7"},{"issue":"3","key":"202_CR6","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna V, Berman P, Fujito T (1999) A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J Discrete Math 12(3):289\u2013297","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"202_CR7","doi-asserted-by":"crossref","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 (1981) A linear-time approximation algorithm for the weighted vertex cover problem. J Algorithms 2(2):198\u2013203","journal-title":"J Algorithms"},{"issue":"1","key":"202_CR8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman R (1962) Dynamic programming treatment of the travelling salesman problem. J ACM 9(1):61\u201363","journal-title":"J ACM"},{"key":"202_CR9","doi-asserted-by":"crossref","unstructured":"Berman P, Karpinski M (2006) 8\/7-approximation algorithm for (1, 2)-tsp. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms, (SODA 2006), pp 641\u2013648. ACM Press","DOI":"10.1145\/1109557.1109627"},{"issue":"1\u20133","key":"202_CR10","doi-asserted-by":"crossref","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 (1992) Precoloring extension. I. Interval graphs. Discrete Math 100(1\u20133):267\u2013279","journal-title":"Discrete Math"},{"key":"202_CR11","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund A, Husfeldt T, Taslaman N (2012) Shortest cycle through specified elements. In: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms (SODA 2012), pp 1747\u20131753","DOI":"10.1137\/1.9781611973099.139"},{"key":"202_CR12","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jda.2013.04.002","volume":"21","author":"H B\u00f6ckenhauer","year":"2013","unstructured":"B\u00f6ckenhauer H, M\u00f6mke T, Steinov\u00e1 M (2013) Improved approximations for TSP with simple precedence constraints. J Discrete Algorithms 21:32\u201340","journal-title":"J Discrete Algorithms"},{"key":"202_CR13","first-page":"129","volume":"73","author":"B Cherkassky","year":"1993","unstructured":"Cherkassky B, Goldberg AV, Radzik T (1993) Shortest paths algorithms: theory and experimental evaluation. Math Program 73:129\u2013174","journal-title":"Math Program"},{"key":"202_CR14","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. TR 388, Graduate School of Industrial Administration, Carnegie Mellon University"},{"key":"202_CR15","doi-asserted-by":"crossref","unstructured":"Gabow HN (1983) An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th annual ACM symposium on theory of computing (STOC 1983), pp 448\u2013456. ACM","DOI":"10.1145\/800061.808776"},{"key":"202_CR16","unstructured":"Gabow HN (1990) Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the 1st annual ACM-SIAM symposium on discrete algorithms (SODA 1990), pp 434\u2013443. SIAM"},{"key":"202_CR17","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco"},{"issue":"4","key":"202_CR18","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1287\/opre.45.4.639","volume":"45","author":"M Gendreau","year":"1997","unstructured":"Gendreau M, Laporte G, Hertz A (1997) An approximation algorithm for the traveling salesman problem with backhauls. Oper Res 45(4):639\u2013641","journal-title":"Oper Res"},{"issue":"4","key":"202_CR19","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans MX, Williamson DP (1994) New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J Discrete Math 7(4):656\u2013666","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"202_CR20","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF01758838","volume":"8","author":"D Gusfield","year":"1992","unstructured":"Gusfield D, Pitt L (1992) A bounded approximation for the minimum cost 2-SAT problem. Algorithmica 8(2):103\u2013117","journal-title":"Algorithmica"},{"issue":"4","key":"202_CR21","doi-asserted-by":"crossref","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 (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28(4):422\u2013437","journal-title":"Algorithmica"},{"key":"202_CR22","unstructured":"Hartvigsen DB (September 1984) Extensions of matching theory. Ph.D. thesis, Department of Mathematics, Carnegie-Mellon University, Pittsburgh"},{"issue":"2","key":"202_CR23","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1147\/sj.42.0136","volume":"4","author":"M Held","year":"1965","unstructured":"Held M, Karp RM (1965) The construction of discrete dynamic programming algorithms. IBM Syst J 4(2):136\u2013147","journal-title":"IBM Syst J"},{"issue":"1","key":"202_CR24","first-page":"1","volume":"62","author":"M Hujter","year":"1993","unstructured":"Hujter M, Tuza Z (1993) Precoloring extension. II. Graphs classes related to bipartite graphs. Acta Math Univ Comenian (NS) 62(1):1\u201311","journal-title":"Acta Math Univ Comenian (NS)"},{"issue":"2","key":"202_CR25","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R (2001) On the complexity of $$k$$ k -SAT. J Comput Syst Sci 62(2):367\u2013375","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"202_CR26","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512\u2013530","journal-title":"J Comput Syst Sci"},{"issue":"6","key":"202_CR27","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0020-0190(92)90161-N","volume":"41","author":"K Jansen","year":"1992","unstructured":"Jansen K (1992) An approximation algorithm for the general routing problem. Inf Process Lett 41(6):333\u2013339","journal-title":"Inf Process Lett"},{"key":"202_CR28","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp RM (1975) On the complexity of combinatorial problems. Networks 5:45\u201368","journal-title":"Networks"},{"issue":"4","key":"202_CR29","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1007\/s00453-013-9827-7","volume":"71","author":"M Knauer","year":"2015","unstructured":"Knauer M, Spoerhase J (2015) Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4):797\u2013811","journal-title":"Algorithmica"},{"key":"202_CR30","unstructured":"Korte B, Vygen J (2008) Combinatorial optimization: theory and algorithms. Chapter the traveling salesman problem, pp 527\u2013562. Springer"},{"key":"202_CR31","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48\u201350","journal-title":"Proc Am Math Soc"},{"key":"202_CR32","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov D, Marx D, Saurabh S (2011) Lower bounds based on the exponential time hypothesis. Bull EATCS 105:41\u201372","journal-title":"Bull EATCS"},{"issue":"6","key":"202_CR33","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1016\/j.dam.2005.10.008","volume":"154","author":"D Marx","year":"2006","unstructured":"Marx D (2006) Precoloring extension on unit interval graphs. Discrete Appl Math 154(6):995\u20131002","journal-title":"Discrete Appl Math"},{"issue":"1","key":"202_CR34","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1002\/net.3230040105","volume":"4","author":"CS Orloff","year":"1974","unstructured":"Orloff CS (1974) A fundamental problem in vehicle routing. Networks 4(1):35\u201364","journal-title":"Networks"},{"key":"202_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C Papadimitriou","year":"1993","unstructured":"Papadimitriou C, Yannakakis M (1993) The travelling salesman problem with distances one and two. Math Oper Res 18:1\u201311","journal-title":"Math Oper Res"},{"key":"202_CR36","volume-title":"Computational complexity","author":"CM Papadimitriou","year":"1994","unstructured":"Papadimitriou CM (1994) Computational complexity. Addison-Wesley, Reading"},{"key":"202_CR37","unstructured":"Robins G, Zelikovsky A (2000) Improved steiner tree approximation in graphs. In: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms (SODA 2000), pp 770\u2013779"},{"issue":"3","key":"202_CR38","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555\u2013565","journal-title":"J ACM"},{"key":"202_CR39","doi-asserted-by":"crossref","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 (1994) New worst-case results for the bin packing problem. Naval Res Logist 41:579\u2013585","journal-title":"Naval Res Logist"},{"key":"202_CR40","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin"},{"issue":"Suppl 14","key":"202_CR41","doi-asserted-by":"crossref","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 (2015a) Exact approaches for scaffolding. BMC Bioinform 16(Suppl 14):S2","journal-title":"BMC Bioinform"},{"key":"202_CR42","doi-asserted-by":"crossref","unstructured":"Weller M, Chateau A, Giroudeau R (2015b) On the complexity of scaffolding problems: From cliques to sparse graphs. In: Proceedings of the 9th international conference on combinatorial optimization and applications (COCOA 2015), vol 9486 of LNCS, pp 409\u2013423. Springer","DOI":"10.1007\/978-3-319-26626-8_30"},{"key":"202_CR43","doi-asserted-by":"crossref","unstructured":"Weller M, Chateau A, Giroudeau R, K\u00f6nig J, Pollet V (2016) On residual approximation in solution extension problems. In: Proceedings of the 10th international conference on combinatorial optimization and applications (COCOA 2016), pp 463\u2013476","DOI":"10.1007\/978-3-319-48749-6_34"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0202-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0202-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0202-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T21:47:34Z","timestamp":1570312054000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0202-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,12]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["202"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0202-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,11,12]]}}}