Vasek Chvátal is ‘the travelling professor’

By Janice Hamilton

Vasek Chvátal, of the Department of Computer Science, has spent most of his academic life studying a mathematical problem called The Travelling Salesman.

Meanwhile, his own life has taken him from Czechoslovakia to Canada, the United States and back to Montreal. Now he is settling in at Concordia with a new job and a new set of academic challenges, including applications in industry and neuroscience.

Chvátal moved to Concordia last summer to occupy the Canada Research Chair in Combinatorial Optimization. This Tier-1 chair is a seven-year renewable position designed for researchers who are world leaders in their fields.

Chvátal grew up in Czechoslovakia, and in 1968 had just finished a degree in mathematics when Russian tanks moved into the country. “I left three days after the invasion,” he said, and had no difficulty crossing the border.

He went first to Austria, where he worked washing dishes while he waited to see what country would accept him as a refugee. He had a choice between Canada, Australia and the United States, and by late fall was enrolled at the University of New Brunswick. The next year he transferred to the University of Waterloo, where he did his PhD.

In the 1970s, Chvátal worked at McGill, the Université de Montréal and Stanford University, and his field of expertise slid into the mathematical side of computer science. He wrote a popular textbook in 1983, and spent 15 years at Rutgers, the State University of New Jersey. During this period he won several awards for his work, and wrote more than 100 articles.

Now Chvátal is “ecstatic” to be back in Montreal. “I belong here,” he said, adding he is also pleased to be at Concordia. “It is very dynamic. I have always liked the mindset ‘We try harder,’ and Concordia has that.”

The move also offers Chvátal an opportunity to change the focus of his work.

For much of his career, he has worked on a topic called the Travelling Salesman Problem: given a finite number of cities, along with the cost of travel between any two of them, the challenge is to find the least expensive route through all the cities and return home. In the 1990s, Chvátal and three collaborators developed a computer code for solving this problem.

He described TSP as a competitive field where people try to outdo each other solving various problems, such as a 15,112-city problem and a 24,978-city problem.

“We were pretty good at it,” he said. “In doing that, I learned a few tricks, and I didn’t want to throw all that away, but I don’t want to do TSP any more. I’m sick and tired of it.”

He explained that the Canada Research Chair of Combinatorial Optimization will give him the opportunity to apply the software and techniques he developed to combinatorial optimization problems, where the aim is to find the most economical option among a finite, but often extremely large, number of possibilities.

With four graduate students already under his wing and two more PhD students ready to join him in the fall, Chvátal has identified two areas of interest.

He is developing contacts in private industry, and plans to tackle problems involving supply chain management, a field that involves planning efficient scheduling of supply shipments to manufacturers throughout the globe.

Inspired by his wife, who is a neurologist, he is also interested in neuroscience. He hopes to investigate ways of teaching computers to read telltale signs in EEG recordings in order to predict whether an individual is going to have an epileptic seizure in the immediate to near future.

“At present, this problem is wide open and no physician can identify those indicators by examining the EEG recordings — even though dogs can be trained to predict impending epileptic seizures of their owners.”