DIMACS
Encyclopedia
The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is a collaboration between Rutgers University
, Princeton University
, and the research firms AT&T
, Bell Labs
, Telcordia
, and NEC. It was founded in 1989 with money from the National Science Foundation
. Its offices are located on the Rutgers campus, and 250 members from the six institutions form its permanent members.
DIMACS is devoted to both theoretical development and practical applications of discrete mathematics and theoretical computer science. It engages in a wide variety of evangelism including encouraging, inspiring, and facilitating researchers in these subject areas, and sponsoring conferences and workshops.
Fundamental research in discrete mathematics has applications in diverse fields including Cryptology, Engineering, Networking, and Management Decision Support.
The current director of DIMACS is Fred S. Roberts
. Past directors were Daniel Gorenstein
and András Hajnal
.
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
, Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, and the research firms AT&T
AT&T
AT&T Inc. is an American multinational telecommunications corporation headquartered in Whitacre Tower, Dallas, Texas, United States. It is the largest provider of mobile telephony and fixed telephony in the United States, and is also a provider of broadband and subscription television services...
, Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
, Telcordia
Telcordia Technologies
Telcordia Technologies, formerly Bell Communications Research, Inc. or Bellcore, is a telecommunications research and development company based in the United States created as part of the 1982 Modification of Final Judgment that broke up American Telephone & Telegraph...
, and NEC. It was founded in 1989 with money from the National Science Foundation
National Science Foundation
The National Science Foundation is a United States government agency that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National Institutes of Health...
. Its offices are located on the Rutgers campus, and 250 members from the six institutions form its permanent members.
DIMACS is devoted to both theoretical development and practical applications of discrete mathematics and theoretical computer science. It engages in a wide variety of evangelism including encouraging, inspiring, and facilitating researchers in these subject areas, and sponsoring conferences and workshops.
Fundamental research in discrete mathematics has applications in diverse fields including Cryptology, Engineering, Networking, and Management Decision Support.
The current director of DIMACS is Fred S. Roberts
Fred S. Roberts
Fred Stephen Roberts is an American mathematician, a professor of mathematics at Rutgers University and the director of DIMACS.-Biography:...
. Past directors were Daniel Gorenstein
Daniel Gorenstein
Daniel E. Gorenstein was an American mathematician. He earned his undergraduate and graduate degrees at Harvard University, where he earned his Ph.D. in 1950 under Oscar Zariski, introducing in his dissertation Gorenstein rings...
and András Hajnal
András Hajnal
András Hajnal is an emeritus professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.-Biography:Hajnal was born on 13 May 1931, in Hungary....
.
The DIMACS Challenges
DIMACS sponsors implementation challenges to determine practical algorithm performance on problems of interest. There have been nine DIMACS challenges so far.- 1990-1991: Network Flows and Matching
- 1992-1992: NP-HardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
Problems: Max Clique, Graph Coloring, and SATBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE... - 1993-1994: Parallel Algorithms for Combinatorial Problems
- 1994-1995: Computational Biology: Fragment Assembly and Genome Rearrangement
- 1995-1996: Priority Queues, Dictionaries, and Multidimensional Point Sets
- 1998-1998: Near Neighbor Searches
- 2000-2000: Semidefinite and Related Optimization Problems
- 2001-2001: The Traveling Salesman Problem
- 2005-2005: The Shortest Path Problem