The maximum-impact coloring polytope

Revista con referato

Detalles Bibliográficos
Autores principales: Braga, Mónica Andrea, Marenco, Javier, Delle Donne, Diego, Linfati, Rodrigo
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: Wiley 2025
Materias:
Coloring
Integer Programming
Facets
Matemáticas
Acceso en línea:http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2037
Aporte de:
Repositorio Institucional Digital de Acceso Abierto (UNGS) de Universidad Nacional de General Sarmiento
id I71-R177-UNGS-2037
record_format dspace
spelling I71-R177-UNGS-20372025-02-05T15:23:27Z The maximum-impact coloring polytope Braga, Mónica Andrea Marenco, Javier Delle Donne, Diego Linfati, Rodrigo Coloring Integer Programming Facets Matemáticas Revista con referato Fil: Braga, Mónica. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Marenco, Javier. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Delle Donne, Diego. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Linfati, Rodrigo. Universidad del Bío-Bío; Chile. Given two graphs G = (V, EG) and H = (V, EH) over the same set of vertices and given a set of colors C, the impact on H of a coloring c : V ! C of G, denoted I(c), is the number of edges ij 2 EH such that c(i) = c(j). In this setting, the maximum-impact coloring problem asks for a proper coloring of G maximizing the impact I(c) on H. This problem naturally arises in the assignment of classrooms to courses, where it is desirable {but not mandatory{ to assign lectures from the same course to the same classroom. Since the maximum-impact coloring problem is NP-hard, we propose in this work an integer-programming-based approach for tackling this problem. To this end, we present an integer programming formulation and we study the associated polytope. We provide several families of valid inequalities, and we study under which conditions these inequalities dene facets of the associated polytope. Finally, we show computational evidence over real-life instances suggesting that some of these families may be useful in a cutting-plane environment. 2025-02-05T15:23:27Z 2025-02-05T15:23:27Z 2016 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Braga, M., Delle Donne, D., Linfati, R. y Marenco, J. (2017). The maximum-impact coloring polytope. International Transactions in Operational Research, 24, 303-324. 0969-6016 http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2037 eng http://dx.doi.org/10.1111/itor.12265 info:eu-repo/semantics/restrictedAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Wiley International Transactions in Operational Research. Ene.-Mar. 2017; 24: 303-324 https://onlinelibrary.wiley.com/toc/14753995/2017/24/1-2
institution Universidad Nacional de General Sarmiento
institution_str I-71
repository_str R-177
collection Repositorio Institucional Digital de Acceso Abierto (UNGS)
language Inglés
orig_language_str_mv eng
topic Coloring
Integer Programming
Facets
Matemáticas
spellingShingle Coloring
Integer Programming
Facets
Matemáticas
Braga, Mónica Andrea
Marenco, Javier
Delle Donne, Diego
Linfati, Rodrigo
The maximum-impact coloring polytope
topic_facet Coloring
Integer Programming
Facets
Matemáticas
description Revista con referato
format Artículo
Artículo
publishedVersion
author Braga, Mónica Andrea
Marenco, Javier
Delle Donne, Diego
Linfati, Rodrigo
author_facet Braga, Mónica Andrea
Marenco, Javier
Delle Donne, Diego
Linfati, Rodrigo
author_sort Braga, Mónica Andrea
title The maximum-impact coloring polytope
title_short The maximum-impact coloring polytope
title_full The maximum-impact coloring polytope
title_fullStr The maximum-impact coloring polytope
title_full_unstemmed The maximum-impact coloring polytope
title_sort maximum-impact coloring polytope
publisher Wiley
publishDate 2025
url http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2037
work_keys_str_mv AT bragamonicaandrea themaximumimpactcoloringpolytope
AT marencojavier themaximumimpactcoloringpolytope
AT delledonnediego themaximumimpactcoloringpolytope
AT linfatirodrigo themaximumimpactcoloringpolytope
AT bragamonicaandrea maximumimpactcoloringpolytope
AT marencojavier maximumimpactcoloringpolytope
AT delledonnediego maximumimpactcoloringpolytope
AT linfatirodrigo maximumimpactcoloringpolytope
_version_ 1824528686881177600

Ejemplares similares