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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 186641695
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A polyhedral study of the maximum-impact coloring problem on hypergraphs.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Singer%2C+Jessica%22">Singer, Jessica</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Marenco%2C+Javier%22">Marenco, Javier</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> javier.marenco@utdt.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Nov2025, Vol. 375, p105-121. 17p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Polyhedral+combinatorics%22">Polyhedral combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+programming%22">Integer programming</searchLink><br /><searchLink fieldCode="DE" term="%22NP-hard+problems%22">NP-hard problems</searchLink><br /><searchLink fieldCode="DE" term="%22Lectures+%26+lecturing%22">Lectures & lecturing</searchLink><br /><searchLink fieldCode="DE" term="%22Classrooms%22">Classrooms</searchLink><br /><searchLink fieldCode="DE" term="%22Hypergraphs%22">Hypergraphs</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=186641695
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.dam.2025.05.042
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 105
    Subjects:
      – SubjectFull: Polyhedral combinatorics
        Type: general
      – SubjectFull: Integer programming
        Type: general
      – SubjectFull: NP-hard problems
        Type: general
      – SubjectFull: Lectures & lecturing
        Type: general
      – SubjectFull: Classrooms
        Type: general
      – SubjectFull: Hypergraphs
        Type: general
    Titles:
      – TitleFull: A polyhedral study of the maximum-impact coloring problem on hypergraphs.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Singer, Jessica
      – PersonEntity:
          Name:
            NameFull: Marenco, Javier
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 11
              Text: Nov2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 375
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1