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

Автор: Бастраков С.И., Золотых Н.Ю.

Журнал: Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика @vestnik-susu-mmph

Статья в выпуске: 1 т.9, 2017 года.

Бесплатный доступ

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

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

Короткий адрес: https://sciup.org/147158930

IDR: 147158930 | DOI: 10.14529/mmph170101

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

Черников, С.Н. Линейные неравенства/С.Н. Черников. -М.: Наука, 1968. -488 с.
Емеличев, В.А. Многогранники, графы, оптимизация/В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. -М.: Наука, 1981. -344 с.
Схрейвер, А. Теория линейного и целочисленного программирования/А. Схрейвер. -М.: Мир, 1991. -Том 1. -360 с.
Циглер, Г. Теория многогранников/Г. Циглер. -М.: МЦНМО, 2014. -586 с.
Метод двойного описания/Т.С. Моцкин, Х. Райфа, Д.Л. Томпсон, Р.М. Тролл//Матричные игры: сб. науч. тр. -М.: Физматгиз, 1961. -С. 81-109.
Черникова, Н.Б. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств/Н.Б. Черникова//Журн. вычисл. математики и мат. физики. -1965. -Т. 5, № 2. -С. 334-337.
Avis, D. A Pivoting Algorithm for Convex Hull and Vertex Enumeration of Arrangements and Polyhedra/D. Avis, K. Fukuda//Discrete and Computational Geometry. -1992. -Vol. 8. -Issue 3. -P. 295-313.
Chazelle, B. An Optimal Convex Hull Algorithm in Any Fixed Dimension/B. Chazelle//Discrete and Computational Geom. -1993. -Vol. 10. -Issue 4. -P. 377-409.
Barber, C.B. The Quickhull Algorithm for Convex Hulls/C.B. Barber, D.P. Dobkin, H. Huhdanpaa//ACM Transactions on Mathematical Software. -1996. -Vol. 22, no. 4. -P. 469-483.
Bremner, D. Primal-Dual Methods for Vertex and Facet Enumeration/D. Bremner, K. Fukuda, A. Marzetta//Discrete and Computational Geometry. -1998. -Vol. 20. -Issue 3. -P. 333-357.
Шевченко, В.Н. Модификация алгоритма Фурье-Моцкина для построения триангуляции/В.Н. Шевченко, Д.В. Груздев//Дискретный анализ и исследование операций. Сер. 2. -2003. -Т. 10, № 1. -С. 53-64.
Панюков, А.В. Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования/А.В. Панюков, В.В. Горбик//Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». -2011. -Вып. 9. -№ 25(242). -C. 107-118.
Панюков, А.В. Представление суммы Минковского для двух полиэдров системой линейных неравенств/А.В. Панюков//Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». -2012. -Вып. 14, № 40(299). -C. 108-119.
Панюков, А.В. Подход к решению систем линейных алгебраических уравнений с интервальной неопределенностью в исходных данных/А.В. Панюков, В.А. Голодов//Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». -2013. -T. 6, № 2 -C. 108-119.
Amato, G. Efficient Constraint/Generator Removal from Double Description of Polyhedra/G. Amato, F. Scozzari, E. Zaffanella//Electronic Notes in Theoretical Computer Science. -2014. -Vol. 307. -P. 3-15.
Cousot, P. Automatic discovery of linear restraints among variables of a program/P. Cousot, N. Halbwachs//Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages. -1978. -P. 84-96.
Bagnara, R. Applications of polyhedral computations to the analysis and verification of hardware and software systems/R. Bagnara, P.M. Hill, E. Zaffanella//Theoretical Computer Science. -2009. -Vol. 410. -P. 4672-4691.
Avis, D. How Good are Convex Hull Algorithms?/D. Avis, D. Bremner, R. Seidel//Computational Geometry. -1997. -Vol. 7, Issues 5-6. -P. 265-301.
Burger, E. Uber homogene lineare Ungleihungssysteme/E. Burger//Zeitschrift Angewandte Math. Mehanik. -1956. -Vol. 36. -Issue 3-4. -P. 135-139.
Fukuda, K. Double Desription Method Revisited/K. Fukuda, A. Prodon//Lecture Notes in Computer Science. -1996. -Vol. 1120. -P. 91-111.
Terzer, M. Accelerating the Computation of Elementary Modes Using Pattern Trees/M. Terzer, J. Stelling//Lecture Notes in Computer Science. -2006. -Vol. 4175. -P. 333-343.
Золотых, Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса/Н.Ю. Золотых//Журн. вычисл. математики и мат. физики. -2012. -Т. 52, № 1. -С. 153-163.
Бастраков, С.И. Алгоритмические вопросы построения двойственного описания выпуклого полиэдра: дис. … канд. физ.-мат. наук/С.И. Бастраков. -Н. Новгород, 2016. -100 с.
Bremner, D. Incremental Convex Hull Algorithms Are Not Output Sensitive/D. Bremner//Discrete and Computational Geometry. -1999. -Vol. 21. -Issue 1. -P. 57-68.

Еще

Статья научная