Anuj Mehrotra’s research receives “Test of Time” award

The award from INFORMS Journal on Computing honors research papers with significant and enduring influence in the field

By Arun Kumar

Anuj Mehrotra, dean of the Georgia Tech Scheller College of Business, and Michael Trick, dean and chief academic officer of Carnegie Mellon University in Qatar, have received “Test of Time Award” from the INFORMS Journal of Computing.

Mehrotra and Trick received the prestigious award for papers published from 1995-1999 for their paper titled “A Column Generation Approach for Graph Coloring,” which has been recognized as an enduring classic in the field.

READ: Lindenwood University names Dr. Rooji Sugathan VP information management (December 10th, 2024) 

The INFORMS Journal of Computing Test of Time Award honors research papers that have demonstrated significant and enduring influence in the field. This award recognizes papers that remain relevant and impactful even years after publication, celebrating them as “classics” within the journal’s scope.

Test of Time Award citation 1995–1999 notes that “graph coloring has a simple polynomial-sized integer-programming formulation, but, even for modest-sized graphs, the resulting IP models are notoriously difficult to solve.”

“This difficulty is due in large part to the symmetry in the model, where color classes are not distinguished in the IP variables,” it says. “The solution proposed in the Mehrotra-Trick paper is to break the symmetry, creating a model with a variable for each potential color class.”

“The resulting exponential-sized formulation is handled by delayed column generation combined with an ingenious branching rule, designed to maintain the original graph-coloring structure in the newly created subproblems.”

“The paper is beautifully written, developing and explaining difficult concepts in branch-cut-and-price methodology in an easy-to-grasp setting,” according to the citation.

“Their elegant work has long served as an important template in the application of linear programming techniques to the solution of difficult optimization models. It will continue to do so for years to come,” it says.

Citation: Anuj Mehrotra and Michael Trick “A Column Generation Approach for Graph Coloring” INFORMS Journal on Computing, Volume 8, Issue 4, Fall 1996, pp. 344–354.