Top

Published in:

2016 | OriginalPaper | Chapter

On Residual Approximation in Solution Extension Problems

Authors : Mathias Weller, Annie Chateau, Rodolphe Giroudeau, Jean-Claude König, Valentin Pollet

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Complexity of Bounded Deletion Propagation

next chapter On the Parameterized Parallel Complexity and the Vertex Cover Problem

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)MathSciNetCrossRefMATH

Arkin, E.M., Hassin, R., Klein, L.: Restricted delivery problems on a network. Networks 29(4), 205–216 (1997)MathSciNetCrossRefMATH

Avidor, A., Zwick, U.: Approximating MIN 2-SAT and MIN 3-SAT. Theory Comput. Syst. 38(3), 329–345 (2005). ISSN 1433–0490MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981)MathSciNetCrossRefMATH

Biró, M., Hujter, M., Tuza, Z.: Precoloring extension. i. interval graphs. Discrete Math. 100(1–3), 267–279 (1992)MathSciNetCrossRefMATH

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)MATH

10.

Gendreau, M., Laporte, G., Hertz, A.: An approximation algorithm for the traveling salesman problem with backhauls. Oper. Res. 45(4), 639–641 (1997)MathSciNetCrossRefMATH

11.

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)MathSciNetCrossRefMATH

12.

Gusfield, D., Pitt, L.: A bounded approximation for the minimum cost 2-SAT problem. Algorithmica 8(2), 103–117 (1992)MathSciNetCrossRefMATH

13.

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)MathSciNetCrossRefMATH

14.

Hujter, M., Tuza, Z.: Precoloring extension. ii. graphs classes related to bipartite graphs. Acta Math. Univ. Comenian. (N.S.) 62(1), 1–11 (1993)MathSciNetMATH

15.

Jansen, K.: An approximation algorithm for the general routing problem. Inf. Process. Lett. 41(6), 333–339 (1992)MathSciNetCrossRefMATH

16.

Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4), 797–811 (2015)MathSciNetCrossRefMATH

17.

Marx, D.: Precoloring extension on unit interval graphs. Discrete Appl. Math. 154(6), 995–1002 (2006)MathSciNetCrossRefMATH

18.

Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4(1), 35–64 (1974)MathSciNetCrossRefMATH

19.

Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Proceedings of 11th SODA, pp. 770–779 (2000)

20.

Simchi-Levi, D.: New worst-case results for the bin packing problem. Naval Res. Logist. 41, 579–585 (1994)MathSciNetCrossRefMATH

21.

Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(Suppl. 14), S2 (2015)CrossRef

22.

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 CrossRef

Title: On Residual Approximation in Solution Extension Problems
Authors: Mathias Weller
Annie Chateau
Rodolphe Giroudeau
Jean-Claude König
Valentin Pollet
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-48749-6_34

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner