О динамической задаче построения остова полиэдрального конуса

Сергей Иванович Бастраков, Николай Юрьевич Золотых

Аннотация


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


Ключевые слова


система линейных неравенств; полиэдральный конус; построение двойственного описания, метод двойного описания

Полный текст:

PDF


DOI: http://dx.doi.org/10.14529/mmph170101

Ссылки

  • На текущий момент ссылки отсутствуют.