Алгоритм решения системы линейных неравенств

[Новичок]

Меня интересует алгоритм Черниковой Н.Е., который опубликован, в частности, в широкоизвестной монографии - Черников С.Н. Линейные неравенства. М.: Наука, 1968.
Как известно из этой монографии, алгоритм разработан для нахождения минимальной системы образующих элементов конуса неотрицательных решений произвольной системы однородных линейных неравенств. К сожалению, в самой монографии не приведена оценка сложности алгоритма.
Мне удалось найти две статьи, в которых утверждается, что данная оценка строго полиномиальна относительно числа переменных и числа неравенств решаемой системы линейных неравенств: Богоявленский Ю.А., Дуплихин М.Ю. (Петрозаводский государственный университет) СИАЛП - система для исследования алгоритмов линейного программирования // Тезисы докладов на международной конференции-выставке "Информационные технологии в непрерывном образовании" 5 июня - 9 июня 1995 г., Петрозаводск; Лукацкий А.М., Шапот Д.В. Конструктивный алгоритм свертывания систем линейных неравенств высокой размерности // Институт энергетических исследований РАН. Статьи 2008 года.
Однако самой формулы полиномиальной оценки и доказательства полиномиальной сложности алгоритма Черниковой найти не удалось.
Если Вам известен источник, в котором приведены интересующие меня формула и доказательство, то убедительная просьба – сообщить на форуме или по электронной почте сведения об этом источнике.

[K-3]

Цитата:

данная оценка строго полиномиальна относительно числа переменных и числа неравенств решаемой системы линейных неравенств

Этого не может быть. Полиномиального алгоритма построения системы образующих многогранного конуса не существует, так как в самой этой системе может быть экспоненциально (от числа неизвестных) много векторов. Про алгоритм Черниковой можно только сказать, что он полиномиален при фиксированном числе неизвестных. Оценка сложности (в зависимости от модификации) примерно $O(m^{[n/2]+1})$ ($n$ - число неизвестных - фиксировано, $m$ - число неравенств).

[Новичок]

Уважаемый (ая) К-3, что-то я в определениях запутался. Подскажите, в современной терминологии оценка $O(m^{[n/2]+1})$ трактуется как полиномиальная или, строго говоря, нет?
И, в любом случае, подскажите, где можно ознакомиться с выводом оценки сложности алгоритма Черниковой.

[K-3]

Если $n$ фиксировано, то это полином (от $m$).
А так - это экспонента от $n$.

[Новичок]

К-3, спасибо за консультацию. Но как насчет вывода оценки сложности алгоритма Черниковой. А то у меня верхняя оценка сложности - степень в степени получается. Ваша оценка мне нравится гораздо больше. Если опубликованного источника нет, то может я через личное сообщение передам Вам адрес своей электронной почты, и Вы мне передадите хотя бы общую идею вывода? Если доказательство строгое, то само-собой соавторство в публикации (алгоритм Черниковой и оценка его сложности идут в статье самостоятельным разделом).

[K-3]

Я считаю этот результат фольклором. Оценка выводится, например, в http://www.uic.nnov.ru/~zny/papers/disser.ps. См. приложение. Б. Никак не претендуя на первенство, этот результат я описал в приложении. Подумаю и поищу, где есть более сильная оценка.

[Новичок]

С интересом ознакомился с Вашей работой (в первую очередь с приложениями А и Б). По большому счету ответ на свой основной вопрос я получил. Но кое-какие "темные пятна" остались. Если вспомнить монографию Черникова С.Н., то даже в ней на примере применения схемы Черниковой для построения формулы вычисления всех решений системы линейных неравенств автор показал, что получаемая по схеме система векторов, определяющих решения, может быть избыточна и содержать зависимые векторы. А это наводит на мысли, что сложность алгоритма несколько больше за счет затрат на построение зависимых векторов. Или я что-то не так понял (я специализируюсь в прикладной области, извиняюсь за наивные вопросы)? И еще два вопроса по терминам. Если использовать термин "квазиполиномиальность" без определения, то его поймут так, как указано в Вашей работе, или все-таки лучше процитировать определение? И второй вопрос. Если в статье сделать акцент на теорию, а не на вычислительную практику, то как корректно назвать алгоритм построения остова конуса: алгоритм Моцкина-Бургера или алгоритм Черниковой?

[K-3]

Цитата:

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

- Это только для самого простого варианта алгоритма. "Настоящий" алгоритм (именно его трудоемкость оценивалась) свободен от этого недостатка.

Цитата:

термин "квазиполиномиальность"

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

Цитата:

как корректно назвать алгоритм построения остова конуса: алгоритм Моцкина-Бургера или алгоритм Черниковой?

Лично я предпочитаю название "метод двойного описания" (double description method), хотя его называют по-разному и, например, даже алгоритмом Фурье-Моцкина (так как с более общих позиций метод двойного описания и алгоритм Фурье-Моцкина - это один и тот же алгоритм), в частности, Шевченко и Груздев http://www.mathnet.ru/php/journal.phtml?fpage=77&issue=1&jrnid=da&lpage=94&paperid=19&volume=13&wshow=paper&year=2006
http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=da&paperid=163&option_lang=rus. Кстати у них, по-моему, и имеется более сильная оценка сложности алгоритма.
Быстрые реализации метода: cdd K.Fukuda http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html и мой Skeleton http://www.uic.nnov.ru/~zny/skeleton/ (в настоящее время на многих задачах быстрее cdd)

[Новичок]

Статьи прочитал, спасибо за ссылки. Теперь с вопросом сложности алгоритма Черниковой (или как там его) все ясно. Хотел было закрыть тему, но вспомнил для чего мне нужен был алгоритм Черниковой. Изначально требовалось из системы линейных неравенств удалить зависимые. Черников в своей монографии указал, что для этого можно воспользоваться алгоритмом Черниковой определенным образом. Стоит отметить, что даже в одном из примеров монографии, где демонстрировался порядок применения алгоритма Черниковой, этот алгоритм не распознал явно зависимое неравенство. Т.е., действительно, за один проход алгоритм Черниковой не выявит все зависимые неравенства (вернее - это не гарантированно). Мой опыт применения алгоритма Черниковой показал, что зависимое неравенство будет точно выявлено в том случае, если отвечающий этом неравенству столбец в таблице Т (обозначение как в монографии) будет рассматриваться в качестве основного в последнюю очередь. А это значит, что в худшем случае, мне придется применить к системе неравенств алгоритм Черниковой m раз, поочередно ставив на последнее место каждое из неравенств (в том случае, если зависимых неравенств нет), и только после этого можно будет утверждать, что система не содержит зависимых неравенств. Может из-за этого в оценке сложности в степени стоит "+1"? "Настоящие" алгоритмы свободны от этого недостатка?

[K-3]

Вот один из способов выкинуть зависимые неравенства: по неравенствам найти систему образующих, а затем, наоборот, - неравенства.

[Новичок]

Ну вот теперь все. Большое спасибо К-3 за консультацию. С одним из авторов статей, которые я указал в начале темы, связался по телефону. Также проявил заинтересованнось к оценке сложности. Мне он пояснил, что в своей статье он имел ввиду, что оценка сложности алгоритма решения системы линейных неравенств "не лучше" чем полиномиальная. Передам ему по электронной почте весь наш диалог.
Еще раз спасибо. Мое первое общение на форуме оказалось весьма плодотворным. Эй, модератор, тему можно закрывать.