Simulated annealing algorithm for the robust spanning tree problem

• Aron, I., van Hentenryck, P.: A constraint satisfaction approach to the robust spanning tree problem with interval data. In: Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, Computer Science Department, Brown University, Maz, Edmonton, Canada, August 1–4, 2002

• Aron, I., van Hentenryck, P.: On the complexity of the robust spanning tree problem with interval data. Oper. Res. Lett. 32, 36–40 (2004)

  Article  MATH  MathSciNet  Google Scholar 

• Ben-Tal, A., Nemirovski, A.: Robust solutions to uncertain programs. Oper. Res. Lett. 25, 1–13 (1999)

  Article  MATH  MathSciNet  Google Scholar 

• Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88, 411–424 (2000)

  Article  MATH  MathSciNet  Google Scholar 

• Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)

  MATH  Google Scholar 

• Kasperski, A., Zielinski, P.: An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett. 97, 177–180 (2006)

  Article  MathSciNet  Google Scholar 

• Kirkpatrick, S.: Optimization by simulated annealing—quantitative studies. J. Stat. Phys. 34, 975–986 (1984)

  Article  MathSciNet  Google Scholar 

• Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated annealing. Science 220, 671–680 (1983)

  Article  MathSciNet  Google Scholar 

• Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic, Norwell (1997)

  MATH  Google Scholar 

• Kozina, G., Perepelitsa, V.: Interval spanning tree problem: solvability and computational complexity. Interval Comput. 1, 42–50 (1994)

  MathSciNet  Google Scholar 

• Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48–50 (1956)

  Article  MathSciNet  Google Scholar 

• Montemanni, R.: A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 174, 1479–1490 (2006)

  Article  MATH  MathSciNet  Google Scholar 

• Montemanni, R., Gambardella, L.: A branch and bound algorithm for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 161, 771–779 (2005)

  Article  MATH  MathSciNet  Google Scholar 

• Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In: Deb et al. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 713–724. Springer, Berlin (2004)

  Google Scholar 

• Nikulin, Y.: Robustness in combinatorial optimization and scheduling theory: an extended annotated bibliography. Manuskripte aus den Instituten für Betriebswirtschaftslehre No. 606, Christian-Albrechts-Universität zu Kiel, Germany (2006). Available on-line: http://www.optimization-online.org/DB_HTML/2004/11/995.html

• Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36, 1389–1401 (1957)

  Google Scholar 

• Steiner, S., Radzik, T.: Solving the biobjective minimum spanning tree problem using a k-best algorithm. Technical Report TR-03-06, Department of Computer Science King’s College London (2003)

• van Laarhoven, P., Aarts, E.: Simulated Annealing: Theory and Applications. Reidel, Dordrecht (1987)

  MATH  Google Scholar 

• Wegener, I.: Simulated annealing beats metropolis in combinatorial optimization. Report No. 8, Electronic Colloquium on Computational Complexity, Dortmund, Germany (2004)

• Yaman, H., Karasan, O., Pinar, M.: The robust spanning tree problem with interval data. Oper. Res. Lett. 29, 31–40 (2001)

  Article  MATH  MathSciNet  Google Scholar 

Download references