.png){kind=icon}
返回
The maximum-impact coloring polytope
.png){kind=icon}
PRE
AI
DOI：10.1111/itor.12265.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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:VC of G, denoted I(c), is the number of edges ijEH 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 desirablebut not mandatoryto 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 study the associated polytope. We provide several families of valid inequalities, and we study under which conditions these inequalities define 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.
Keyword:
coloring
integer programming
facets
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.9
论文数:
1.8K
被引数:
3.7K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容