Центр дискретной математики и теоретической информатики ( DIMACS ) является сотрудничество между Университета Рутгерса , Принстонский университет , и исследовательские фирмы AT & T , Bell Labs , Applied связи наук и NEC . Он был основан в 1989 году на деньги Национального научного фонда . Его офисы расположены в кампусе Рутгерса, и 250 членов из шести институтов составляют его постоянные члены.
DIMACS посвящен как теоретическим разработкам, так и практическим приложениям дискретной математики и теоретической информатики. Он участвует в широком спектре евангелизации, включая поощрение, воодушевление и содействие исследователям в этих предметных областях, а также спонсирование конференций и семинаров.
Фундаментальные исследования дискретной математики находят применение в различных областях, включая криптологию, инженерию, сети и поддержку принятия управленческих решений.
В прошлом директорами были Фред С. Робертс , Дэниел Горенштейн , Андраш Хайнал и Ребекка Н. Райт . [1]
Проблемы DIMACS
DIMACS спонсирует задачи внедрения, чтобы определить практическую производительность алгоритмов при решении интересующих задач. На данный момент было решено одиннадцать задач DIMACS.
- 1990-1991: Сетевые потоки и согласование
- 1992-1992: NP-сложные задачи: Max Clique , раскраска графиков и SAT
- 1993-1994: Параллельные алгоритмы для комбинаторных задач
- 1994-1995: Вычислительная биология: сборка фрагментов и перестройка генома
- 1995-1996: очереди приоритетов, словари и многомерные наборы точек
- 1998-1998: Обыск ближайшего соседа
- 2000-2000: полуопределенные и связанные с ними проблемы оптимизации
- 2001-2001: Проблема коммивояжера
- 2005-2005: Проблема кратчайшего пути
- 2011-2012: График Секционирование и график кластеризации [1]
- 2013-2014: Проблемы дерева Штейнера
- 2020-2021: Проблемы с маршрутизацией транспортных средств
Рекомендации
- ^ История математики в Рутгерсе , Чарльз Вейбель.