ADVERTISEMENTs
.png)
Anuj Mehrotra wins "Test of Time" Award for computing research
The INFORMS Journal on Computing praised the paper as "beautifully written," highlighting its role as a template for applying linear programming to complex optimization models.
.jpg)
Dean Anuj Mehrotra. / Georgia Tech
The INFORMS Journal on Computing has honored Anuj Mehrotra, dean of the Georgia Tech Scheller College of Business, with the "Test of Time Award."
The award, which recognizes research papers with lasting influence, was bestowed for his 1996 paper, “A Column Generation Approach for Graph Coloring,” also authored by Michael Trick, dean, and chief academic officer of Carnegie Mellon University in Qatar.
Their work, published during the 1995-1999 eligibility period, has been lauded as a "classic" in computational research. It addresses the complexity of solving graph-coloring problems using integer programming (IP). While graph coloring has a simple polynomial-sized IP formulation, the symmetry of color classes often creates computational challenges.
Mehrotra's breakthrough involved breaking this symmetry by creating a model with variables for each potential color class. The approach utilized an exponential-sized formulation, managed through delayed column generation and an innovative branching rule that preserved the graph’s structure in subproblems.
The INFORMS Journal on Computing praised the paper as "beautifully written," highlighting its role as a foundational template for applying linear programming to complex optimization models. The methodology has since guided numerous applications in operations research, computational optimization, and beyond.
The "Test of Time Award" is a testament to the paper’s continued relevance and influence within the field. It celebrates the enduring impact of research that advances theory and practice, reaffirming the significance of Mehrotra and Trick's contributions nearly three decades after publication.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
E Paper
ADVERTISEMENT
.jpg)
Video
Comments
Start the conversation
Become a member of New India Abroad to start commenting.
Sign Up Now
Already have an account? Login