David Applegate, Associate Professor, Computational & Applied Mathematics, Rice University
|
|
| David Applegate, a leading scientist in the field of discrete
optimization, says he has always been interested in math and
computer science. He became involved in the field of discrete
optimization while pursuing his graduate degree at Carnegie Mellon
University (CMU). "While I was studying theoretical computer science
in graduate school, my advisor was invited to spend a year visiting
the Discrete Mathematics Institute at the University of Bonn, Germany,
and offered me a chance to go there with him," he says. "Bill Cook,
now Noah Harding Professor of Computational and Applied Mathematics
(CAAM) at Rice, was also visiting Bonn at that time. At one point, he
commented that he wished he had a program to generate some inequalities
he wanted to try for a polyhedral approach to the job shop scheduling
program. That was the start of our long-lasting collaboration and
friendship."
Applegate received his B.S. in both computer science and mathematics from the University of Dayton in 1984. He spent the next year working with the Structural Integrity Group at the University of Dayton Research Institute, then went to graduate school at CMU, where he received his Ph.D. in computer science in 1991. Applegate then joined the Mathematical Sciences Research Center of AT&T Bell Labs as a member of the technical staff until accepting his current position in 1996 as an associate professor at CAAM. He also was a John von Newmann Visiting Professor at the Research Institute for Discrete Mathematics at Bonn in 1997-1998. This fall, Applegate accepted a position at AT&T as a technology consultant, effective January 2000. Applegate's most significant research, with Cook, Rice CAAM Professor Robert Bixby and others, is his work on the Traveling Salesman Problem (TSP). The TSP involves finding an optimal path for a salesman to take when traveling through a specified number of cities, and has applications in science and engineering, including the manufacture of circuit boards. (See "CRPC Researchers Solve Traveling Salesman Problem for Record-Breaking 13,509 Cities," Spring/Summer 1998 Parallel Computing Research.) Progress on the TSP is measured against TSPLIB, a library of TSP instances introduced in 1990 at the first workshop ever sponsored by the CRPC. "TSPLIB was created to provide a set of challenges for TSP researchers," says Applegate. "We have advanced the state-of-the-art to the point that we have solved every problem in that TSPLIB." The researchers have also solved several other problems that have been added to TSPLIB since its inception, including a 13,509-city instance. Applegate's currently works in the areas of integer programming, combinatorial optimization, discrete algorithms, and parallel optimization. Primarily, he says, he is "continuing to bash away at the TSP." Applegate was co-organizer of the 1993 Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) workshop on Future Directions for Parallel Optimization and program committee member of the 1996 Symposium on Data Structures and Algorithms (SODA).He is the author or co-author of 16 papers and has been on the CRPC Technical Steering Committee since 1997. |
|
 Other Issues of
PCR | Back to PCR | CRPC Home Page |