Navegar

Colección

Datos Estadísticas

Artículo

Méndez Díaz, I.; Nasini, G.; Severín, D.; Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE "A tabu search heuristic for the equitable coloring problem" (2014) 3rd International Symposium on Combinatorial Optimization, ISCO 2014. 8596 LNCS:347-358
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given. Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances. © 2014 Springer International Publishing.

Registro:

Documento: Artículo
Título:A tabu search heuristic for the equitable coloring problem
Autor:Méndez Díaz, I.; Nasini, G.; Severín, D.; Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
Ciudad:Lisbon
Filiación:Facultad de Ciencias Exactas, Ingeniería Y Agrimensura, Universidad Nacional de Rosario, Rosario, Argentina
CONICET, Rosario, Argentina
Facultad de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Combinatorial optimization; Equitable coloring; Tabu search; Benchmarking; Combinatorial optimization; Heuristic algorithms; Heuristic methods; Arbitrary color; Computational experiment; Equitable coloring; Exact algorithms; Graph coloring problem; Large-sized; Local search; Tabu Search heuristic; Tabu search
Año:2014
Volumen:8596 LNCS
Página de inicio:347
Página de fin:358
DOI: http://dx.doi.org/10.1007/978-3-319-09174-7_30
Título revista:3rd International Symposium on Combinatorial Optimization, ISCO 2014
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p347_MendezDiaz

Referencias:

  • Meyer, W., Equitable coloring (1973) Amer. Math. Mon., 80, pp. 920-922
  • Tucker, A., Perfect graphs and an application to optimizing municipal services (1973) SIAM Rev., 15, pp. 585-590
  • Das, S.K., Finocchi, I., Petreschi, R., Conflict-free star-access in parallel memory systems (2006) J. Parallel Distrib. Comput., 66, pp. 1431-1441
  • Pemmaraju, S.V., Equitable coloring extends Chernoff-Hoeffding bounds (2001) LNCS, 2129, p. 285. , Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX-RANDOM 2001. Springer, Heidelberg
  • Furmanczyk, H., Kubale, M., Equitable coloring of graphs (2004) Graph Colorings, pp. 35-53. , Kubale, M. (ed.) American Mathematical Society, Providence
  • Hajnal, A., Szemerédi, E., Proof of a conjecture of P. Erdös (1970) Combin. Theory and Its App., 2, pp. 601-623
  • Kierstead, H., Kostochka, A., Mydlarz, M., Szemerédi, E., A fast algorithm for equitable coloring (2010) Combinatorica, 30, pp. 217-224
  • Brélaz, D., Nicolier, Y., De Werra, D., Compactness and balancing in scheduling (1977) Math. Methods Oper. Res., 21, pp. 65-73
  • Sulong, G.B., Some balanced colouring algorithms for examination timetabling (1992) Jurnal Teknologi, 19, pp. 57-63
  • Bahiense, L., Frota, Y., Noronha, T.F., Ribeiro, C., A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives (2014) Discrete Appl. Math., 164 (1), pp. 34-46
  • Méndez Díaz, I., Nasini, G., Severín, D., A polyhedral approach for the equitable coloring problem (2014) Discrete Appl. Math., 164 (2), pp. 413-426
  • Méndez Díaz, I., Nasini, G., Severín, D., An exact DSatur-based algorithm for the equitable coloring problem (2013) Electron. Notes Discrete Math., 44, pp. 281-286
  • Galinier, P., Hao, J.-K., Hybrid evolutionary algorithms for graph coloring (1999) J. Comb. Optim., 3 (4), pp. 379-397
  • Galinier, P., Hertz, A., A survey of local search methods for graph coloring (2006) Comput. Oper. Res., 33 (9), pp. 2547-2562
  • Glover, F., McMillan, C., Novick, B., Interactive decision software and computer graphics for architectural and space planning (1985) Ann. Oper. Res., 5 (3), pp. 557-573
  • Hertz, A., De Werra, D., Using tabu search techniques for graph coloring (1987) Computing, 39 (4), pp. 345-351
  • Blöchliger, I., Zufferey, N., A graph coloring heuristic using partial solutions and a reactive tabu scheme (2008) Comput. Oper. Res., 35 (3), pp. 960-975
  • Graph Coloring Benchmark Instances, , http://www.cs.hbg.psu.edu/txn131/graphcoloring.htmlA4 - Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE

Citas:

---------- APA ----------
Méndez Díaz, I., Nasini, G., Severín, D. & Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE (2014) . A tabu search heuristic for the equitable coloring problem. 3rd International Symposium on Combinatorial Optimization, ISCO 2014, 8596 LNCS, 347-358.
http://dx.doi.org/10.1007/978-3-319-09174-7_30
---------- CHICAGO ----------
Méndez Díaz, I., Nasini, G., Severín, D., Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE "A tabu search heuristic for the equitable coloring problem" . 3rd International Symposium on Combinatorial Optimization, ISCO 2014 8596 LNCS (2014) : 347-358.
http://dx.doi.org/10.1007/978-3-319-09174-7_30
---------- MLA ----------
Méndez Díaz, I., Nasini, G., Severín, D., Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE "A tabu search heuristic for the equitable coloring problem" . 3rd International Symposium on Combinatorial Optimization, ISCO 2014, vol. 8596 LNCS, 2014, pp. 347-358.
http://dx.doi.org/10.1007/978-3-319-09174-7_30
---------- VANCOUVER ----------
Méndez Díaz, I., Nasini, G., Severín, D., Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE A tabu search heuristic for the equitable coloring problem. Lect. Notes Comput. Sci. 2014;8596 LNCS:347-358.
http://dx.doi.org/10.1007/978-3-319-09174-7_30