ДИМАКС

Центр дискретной математики и теоретической информатики ( DIMACS ) является результатом сотрудничества Университета Рутгерса , Принстонского университета и исследовательских фирм AT&T , Bell Labs , Applied Communication Sciences и NEC . Он был основан в 1989 году на деньги Национального научного фонда . Его офисы расположены в кампусе Рутгерса, и 250 членов из шести учреждений являются его постоянными членами.

DIMACS занимается как теоретическим развитием, так и практическим применением дискретной математики и теоретической информатики. Он занимается разнообразной евангелизацией, включая поощрение, вдохновение и содействие исследователям в этих предметных областях, а также спонсирование конференций и семинаров.

Фундаментальные исследования в области дискретной математики применяются в различных областях, включая криптологию, инженерию, сетевые технологии и поддержку управленческих решений.

Среди прошлых директоров были Фред С. Робертс , Дэниел Горенштейн , Андраш Хайнал и Ребекка Н. Райт .

Проблемы DIMACS

DIMACS спонсирует задачи по реализации, чтобы определить практическую эффективность алгоритма при решении интересующих задач. На данный момент было зарегистрировано одиннадцать проблем с DIMACS.

• 1990–1991: Сетевые потоки и сопоставление
• 1992–1992: NP-сложные задачи: Макс Клика , раскраска графов и SAT
• 1993–1994: Параллельные алгоритмы решения комбинаторных задач.
• 1994–1995: Вычислительная биология: сборка фрагментов и перестройка генома.
• 1995–1996: очереди приоритетов, словари и многомерные наборы точек.
• 1998–1998: Обыски ближайших соседей
• 2000-2000: Полуопределенные и связанные с ними проблемы оптимизации
• 2001–2001: Проблема коммивояжера
• 2005–2005: Задача о кратчайшем пути
• 2011–2012: Разбиение графов и кластеризация графов [1]
• 2013–2014: Проблемы с деревом Штайнера
• 2020-2021: Проблемы с маршрутизацией транспортных средств

Внешние ссылки

• Веб-сайт ДИМАКС