View in EDS

A polyhedral study of the maximum-impact coloring problem on hypergraphs.

Saved in:
Bibliographic Details
Title: A polyhedral study of the maximum-impact coloring problem on hypergraphs.
Authors: Singer, Jessica1 (AUTHOR), Marenco, Javier1,2 (AUTHOR) javier.marenco@utdt.edu
Source: Discrete Applied Mathematics. Nov2025, Vol. 375, p105-121. 17p.
Subjects: Polyhedral combinatorics, Integer programming, NP-hard problems, Lectures & lecturing, Classrooms, Hypergraphs
Abstract: Given a graph G = (V , E) and a hypergraph H = (V , F) over the same set of vertices, and a finite color set C , the maximum-impact coloring problem on hypergraphs asks for a C -coloring of G maximizing the number of hyperedges of H whose vertices are assigned the same color. This problem arises in the context of classroom assignment to courses, in which we need to assign a classroom to each lecture and we wish to assign the same classroom to all lectures from the same course. Since imposing this last concern as a constraint may be too restrictive, we seek to maximize the number of courses such that all of its lectures are assigned to the same classroom. In this work we present an integer programming formulation for this NP-hard problem and we explore the associated polytope. We present three families of facet-inducing inequalities, and we report computational experiments suggesting that the dynamic addition of these inequalities within a branch and cut environment may be effective in practice. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Given a graph G = (V , E) and a hypergraph H = (V , F) over the same set of vertices, and a finite color set C , the maximum-impact coloring problem on hypergraphs asks for a C -coloring of G maximizing the number of hyperedges of H whose vertices are assigned the same color. This problem arises in the context of classroom assignment to courses, in which we need to assign a classroom to each lecture and we wish to assign the same classroom to all lectures from the same course. Since imposing this last concern as a constraint may be too restrictive, we seek to maximize the number of courses such that all of its lectures are assigned to the same classroom. In this work we present an integer programming formulation for this NP-hard problem and we explore the associated polytope. We present three families of facet-inducing inequalities, and we report computational experiments suggesting that the dynamic addition of these inequalities within a branch and cut environment may be effective in practice. [ABSTRACT FROM AUTHOR]
ISSN:0166218X
DOI:10.1016/j.dam.2025.05.042