The Center for

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

and

Theoretical Computer Science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

(DIMACS) is a collaboration between

Rutgers University Rutgers University ( ), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of three campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's C ...

Princeton University Princeton University is a private university, private Ivy League research university in Princeton, New Jersey, United States. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial ...

, and the research firms

AT&T AT&T Inc., an abbreviation for its predecessor's former name, the American Telephone and Telegraph Company, is an American multinational telecommunications holding company headquartered at Whitacre Tower in Downtown Dallas, Texas. It is the w ...

Bell Labs Nokia Bell Labs, commonly referred to as ''Bell Labs'', is an American industrial research and development company owned by Finnish technology company Nokia. With headquarters located in Murray Hill, New Jersey, Murray Hill, New Jersey, the compa ...

, Applied Communication Sciences, and

NEC is a Japanese multinational information technology and electronics corporation, headquartered at the NEC Supertower in Minato, Tokyo, Japan. It provides IT and network solutions, including cloud computing, artificial intelligence (AI), Inte ...

. It was founded in 1989 with money from the

National Science Foundation The U.S. National Science Foundation (NSF) is an Independent agencies of the United States government#Examples of independent agencies, independent agency of the Federal government of the United States, United States federal government that su ...

. 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. Past directors have included Fred S. Roberts,

Daniel Gorenstein Daniel E. Gorenstein (January 1, 1923 – August 26, 1992) was an American mathematician best remembered for his contribution to the classification of finite simple groups. Gorenstein mastered calculus at age 12 and subsequently matriculated at ...

, András Hajnal, and Rebecca N. Wright.A history of mathematics at Rutgers
Charles Weibel.

The DIMACS challenges

DIMACS sponsors implementation challenges to determine practical algorithm performance on problems of interest. There have been eleven DIMACS challenges so far. * 1990−1991: Network flows and matching * 1992−1992:

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

problems: Max Clique,

Graph Coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...

, and

SAT The SAT ( ) is a standardized test widely used for college admissions in the United States. Since its debut in 1926, its name and Test score, scoring have changed several times. For much of its history, it was called the Scholastic Aptitude Test ...

* 1993−1994: Parallel algorithms for combinatorial problems * 1994−1995: Computational giology: 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 In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...

* 2005−2005: The shortest-path problem * 2011−2012:

Graph partition In mathematics, a graph partition is the reduction of a Graph (discrete mathematics), graph to a smaller graph by partition of a set, partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the g ...

ing and graph clusteringbr>
* 2013−2014:

Steiner tree problem In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a ...

s * 2020−2021:

Vehicle routing problem The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises ...

References

External links

DIMACS Website
1989 establishments in New Jersey Combinatorics Discrete mathematics Rutgers University Mathematical institutes {{Math-org-stub