DIMACS , the Center for Discrete Mathematics and Theoretical Computer Science, conducts research, education and outreach programs in discrete mathematics and theoretical computer science. These areas are the underlying models of much recent progress in digital computing, optimization, communications, and increasingly in areas such as molecular biology. The advent of digital computing and communication has both enabled scientific progress in many disciplines and become a grand challenge for science in its own right.
This page introduces just 3 of DIMACS accomplishments. The home page for DIMACS gives a broad overview.
DIMACS is training 4 postdoctoral fellows concentrating on mathematical and computational problems arising from molecular biology; conducted a 3 week program of tutorials to introduce fellows, graduate students and researchers to this emerging research area; is sponsoring 13 workshops on topics ranging from determining family trees via genetic analysis (phylogeny) to HIV sequence analysis; and is sponsoring a series of 10 distinguished lecturers .
Leadership program alumni have incorporated discrete mathematics in their classrooms, have hosted Workshops in Your District programs to reach an additional 300 teachers per year, have led workshops for their teaching peers to reach over 10,000 teachers in the US. Other impacts include a group of alumni who have developed a curriculum for a discrete mathematics course that has been adopted for the New York City curriculum; Greatest Hits in Discrete Mathematics, a book in preparation of tested classroom activities that were developed and written by alumni, a regular newsletter reaching over 3000 teachers, and incorporating discrete mathematics in the New Jersey Curriculum Framework, a curriculum being developed by the NJ Math Coalition and the NJ Dept. of Education, in cooperation with the NJ-SSI.
In work that grew out of the 1992-93 challenge, Vasek Chvatal, William Cook and Robert Bixby have made enormous strides on solving the Traveling Salesman Problem, the best known NP-Complete problem which seeks the shortest path to visit all the cities on a map. They have set several international records for largest maps solved, including: 3038 cities in 1992; 4461 cities in 1993; and 7397 cities in 1994. Their work illustrates the doubled impact of combining basic mathematical research on the combinatorial models of the problem with steady improvements in implementations and access to faster computers.