Abstract
The solution extension variant of a problem consists in, being given an instance and a partial solution, finding the best solution comprising the given partial solution. Many problems have been studied with a similar approach. For instance the Precoloring Extension problem, the clustered variant of the Travelling Salesman problem, or the General Routing Problem are in a way typical examples of solution extension variant problems. Motivated by practical applications of such variants, this work aims to explore different aspects around extension on classical optimization problems. We define residue-approximations as algorithms whose performance ratio on the non-prescribed part can be bounded, and corresponding complexity classes. Using residue-approximation, we classify several problems according to their residue-approximability.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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–2), 29–35 (1999)
Arkin, E.M., Hassin, R., Klein, L.: Restricted delivery problems on a network. Networks 29(4), 205–216 (1997)
Avidor, A., Zwick, U.: Approximating MIN 2-SAT and MIN 3-SAT. Theory Comput. Syst. 38(3), 329–345 (2005). ISSN 1433–0490
Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289–297 (1999)
Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981)
Biró, M., Hujter, M., Tuza, Z.: Precoloring extension. i. interval graphs. Discrete Math. 100(1–3), 267–279 (1992)
Björklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In Proceedings of 23rd SODA, pp. 1747–1753 (2012)
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)
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)
Gendreau, M., Laporte, G., Hertz, A.: An approximation algorithm for the traveling salesman problem with backhauls. Oper. Res. 45(4), 639–641 (1997)
Goemans, M.X., Williamson, D.P.: New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656–666 (1994)
Gusfield, D., Pitt, L.: A bounded approximation for the minimum cost 2-SAT problem. Algorithmica 8(2), 103–117 (1992)
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–437 (2000)
Hujter, M., Tuza, Z.: Precoloring extension. ii. graphs classes related to bipartite graphs. Acta Math. Univ. Comenian. (N.S.) 62(1), 1–11 (1993)
Jansen, K.: An approximation algorithm for the general routing problem. Inf. Process. Lett. 41(6), 333–339 (1992)
Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4), 797–811 (2015)
Marx, D.: Precoloring extension on unit interval graphs. Discrete Appl. Math. 154(6), 995–1002 (2006)
Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4(1), 35–64 (1974)
Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Proceedings of 11th SODA, pp. 770–779 (2000)
Simchi-Levi, D.: New worst-case results for the bin packing problem. Naval Res. Logist. 41, 579–585 (1994)
Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(Suppl. 14), S2 (2015)
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–423. Springer, Heidelberg (2015). doi:10.1007/978-3-319-26626-8_30
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Weller, M., Chateau, A., Giroudeau, R., König, JC., Pollet, V. (2016). On Residual Approximation in Solution Extension Problems. In: Chan, TH., Li, M., Wang, L. (eds) Combinatorial Optimization and Applications. COCOA 2016. Lecture Notes in Computer Science(), vol 10043. Springer, Cham. https://doi.org/10.1007/978-3-319-48749-6_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-48749-6_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48748-9
Online ISBN: 978-3-319-48749-6
eBook Packages: Computer ScienceComputer Science (R0)