Vasek Chvatal awarded Canada Research Chair

The Canada Research Chair in Combinatorial Optimization has been awarded to Vasek Chvatal, who will join Concordia’s Department of Computer Science on June 1, 2004. He comes from Rutgers, the State University of New Jersey.

At Rutgers, Chvatal received the Alexander von Humboldt Distinguished Senior Scientist Award and the Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming. He is also the author of a popular textbook and more than 100 articles. His appointment through the Canada Research Chairs program is through a NSERC Tier 1 award.

“The appointment of Dr. Chvatal fulfils the principal purpose of the federal program to attract to Canada a first-class scientist who has the potential of mentoring a new school of excellence in discovery at Concordia,” said Nabil Esmail, Dean of Engineering and Computer Science.

Chvatal’s research field, combinatorial optimization, can be presented the following way: What do a semiconductor manufacturer, a group of genome scientists, and a team of engineers working on a NASA project have in common?

The semiconductor manufacturer wants to minimize the length of “scan chains,” which are routes included on a chip for testing purposes; the genome scientists want to integrate local radiation hybrid maps into a single consistent map of a genome; and the NASA engineers want to save fuel when manoeuvring the pair of satellites used in its StarLight space interferometer mission.

These are all examples of what can be called the “travelling salesman problem:” Given a finite number of cities along with the cost of travel between any two of them, find the least expensive route that takes you through all the cities and brings you back home.

In the 1990s, Chvatal and three collaborators developed a computer code for solving certain instances of the “travelling salesman problem.” Some of their groundbreaking techniques may be applicable to a wide class of combinatorial optimization problems, where one aims to find the most economical option among a finite, but often astronomically large, number of possibilities. At Concordia, Chvatal and his research team will be investigating this potential.

Combinatorial optimization problems have many applications in industry and management. Classical applications include manpower, production, and facility planning; job sequencing and scheduling; manufacturing layout design; retail seasonal planning. The 1980s brought new applications in “very large-scale integration” (VLSI) design; the 1990s brought new applications in computational molecular biology.

The most recent applications are largely dominated by the Internet revolution and advances in genomics. They include broadband satellite communications, telecommunication network design, e-commerce, computational finance, and biotechnology and bioinformatics.