RUS  ENG
Полная версия
ЖУРНАЛЫ // Автоматика и телемеханика // Архив

Автомат. и телемех., 1993, выпуск 4, страницы 21–26 (Mi at2923)

Детерминированные системы

Многогранники с высокой плотностью графа и полиномиальная разрешимость задач комбинаторной оптимизации

В. А. Бондаренко

Ярославский государственный университет

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

УДК: 519.1

MSC: 90C27


Поступила в редакцию: 25.06.1992


 Англоязычная версия: Automation and Remote Control, 1993, 54:4, 541–545

Реферативные базы данных:


© МИАН, 2024