Skip to main content

2016 | OriginalPaper | Buchkapitel

On Residual Approximation in Solution Extension Problems

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

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat 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 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
3.
4.
Zurück zum Zitat 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 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
5.
Zurück zum Zitat Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981)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
6.
7.
Zurück zum Zitat Björklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In Proceedings of 23rd SODA, pp. 1747–1753 (2012) Björklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In Proceedings of 23rd SODA, pp. 1747–1753 (2012)
8.
Zurück zum Zitat 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) 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)
9.
Zurück zum Zitat 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 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.
Zurück zum Zitat Gendreau, M., Laporte, G., Hertz, A.: An approximation algorithm for the traveling salesman problem with backhauls. Oper. Res. 45(4), 639–641 (1997)MathSciNetCrossRefMATH 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.
Zurück zum Zitat 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 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.
13.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
16.
Zurück zum Zitat Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4), 797–811 (2015)MathSciNetCrossRefMATH Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4), 797–811 (2015)MathSciNetCrossRefMATH
19.
Zurück zum Zitat Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Proceedings of 11th SODA, pp. 770–779 (2000) Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Proceedings of 11th SODA, pp. 770–779 (2000)
21.
Zurück zum Zitat Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(Suppl. 14), S2 (2015)CrossRef Weller, M., Chateau, A., Giroudeau, R.: Exact approaches for scaffolding. BMC Bioinform. 16(Suppl. 14), S2 (2015)CrossRef
22.
Zurück zum Zitat 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 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
Metadaten
Titel
On Residual Approximation in Solution Extension Problems
verfasst von
Mathias Weller
Annie Chateau
Rodolphe Giroudeau
Jean-Claude König
Valentin Pollet
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-48749-6_34