Navegar

Colección

Datos Estadísticas

Artículo

Urrutia, S.; Loiseau, I. "A new metaheuristic and its application to the Steiner problems in graphs" (2001) Proceedings - International Conference of the Chilean Computer Science Society, SCCC. 2001-January:273-281
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Metaheuristics are a set of related ideas that provide a general framework to obtain the approximated solution of combinatorial optimization problems. We present ideas for a new method that we call SN. SN is based on the idea of dividing a given optimization problem into decision subproblems which are easier to solve heuristically. In order to verify the effectiveness of this metaheuristic approach, we developed an algorithm to solve a classic graph theory problem, the Steiner Problem in Graphs. Preliminary results show that the new algorithm is competitive when compared with the best heuristic algorithms known for this problem. © 2001 IEEE.

Registro:

Documento: Artículo
Título:A new metaheuristic and its application to the Steiner problems in graphs
Autor:Urrutia, S.; Loiseau, I.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, Buenos Aires 1428, Argentina
Palabras clave:Combinatorial optimization; Graph theory; Heuristic algorithms; Approximated solutions; Combinatorial optimization problems; ITS applications; Meta heuristics; Meta-heuristic approach; Metaheuristic; Optimization problems; Steiner problems; Optimization
Año:2001
Volumen:2001-January
Página de inicio:273
Página de fin:281
DOI: http://dx.doi.org/10.1109/SCCC.2001.972657
Título revista:Proceedings - International Conference of the Chilean Computer Science Society, SCCC
Título revista abreviado:Proc. Int. Conf. Chilean Comput. Sci. Soc. SCCC
ISSN:15224902
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15224902_v2001-January_n_p273_Urrutia

Referencias:

  • Beasley, J.E., OR-Library: Distributing test problems by electronic mail (1990) Journal of the Operational Research Society, 41, pp. 1069-1072
  • Dongarra, J.J., (1995) Performance of Various Computers Using Standard Linear Equations Software, , Working paper. University of Tennessee, Knoxville
  • Duin, C.W., Volgenant, A., Reduction tests for the Steiner problem in graphs (1989) Networks, 19, pp. 549-567
  • Esbensen, H., Computing near-optimal solutions to the Steiner problems in a graph using a genetic algorithm (1995) Networks, 26, pp. 173-185
  • Gendreau, M., Larochell, J.-F., Brunilde, S., A tabu search for the Steiner Tree Problem (1999) Networks, 34, pp. 162-172
  • Glover, F., Laguna, M., (1997) Tabu Search, , Kluwer
  • Hwang, F.K., Richards, D.S., Steiner Tree Problems (1992) Networks, 22, pp. 55-89
  • Karp, R.M., Reducibility among combinatorial problems (1972) Complexity of Computer Computations, , R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York
  • Michalewicz, Z., (1999) Genetic Algorithms + Data Structures = Evolutions Programas, , Springer
  • Rayward-Smith, V.J., Clare, A., On finding Steiner vertices (1986) Networks, 16, pp. 283-294
  • Ribeiro, C.C., De Souza, M.C., Tabu search for the Steiner problem in graphs (2000) Networks, 36, pp. 138-146
  • Takahashi, H., Matsuyama, A., An approximate solution for the Steiner problem in graphs (1980) Math. Japonica, 24, pp. 573-577
  • Urrutia, S., (2001) SN: Una Nueva Metaheurística, , Tesis de Licenciatura, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires
  • Winter, P., Steiner problem in networks: A survey (1987) Networks, 17, pp. 129-167
  • Winter, P., MacGregor Smith, J., Path-distance heuristics for the Steiner problems in undirected networks (1992) Algorithmica, 7, pp. 309-327

Citas:

---------- APA ----------
Urrutia, S. & Loiseau, I. (2001) . A new metaheuristic and its application to the Steiner problems in graphs. Proceedings - International Conference of the Chilean Computer Science Society, SCCC, 2001-January, 273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657
---------- CHICAGO ----------
Urrutia, S., Loiseau, I. "A new metaheuristic and its application to the Steiner problems in graphs" . Proceedings - International Conference of the Chilean Computer Science Society, SCCC 2001-January (2001) : 273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657
---------- MLA ----------
Urrutia, S., Loiseau, I. "A new metaheuristic and its application to the Steiner problems in graphs" . Proceedings - International Conference of the Chilean Computer Science Society, SCCC, vol. 2001-January, 2001, pp. 273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657
---------- VANCOUVER ----------
Urrutia, S., Loiseau, I. A new metaheuristic and its application to the Steiner problems in graphs. Proc. Int. Conf. Chilean Comput. Sci. Soc. SCCC. 2001;2001-January:273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657