Симплексы вместо эллипсоидов

[Mihail Gladkov]

Добрый вечер!
Я изучаю полиномиальные алгоритмы для решения задач линейного программирования.
Существует алгоритм аналогичный методу эллипсодов, но вместо эллипсоидов используютя симплексы. Вроде бы этим подходом занимался Дикин И.И. Не могу найти ни его работ на эту тему, ни описаний этого метода. Если кому-то этот метод знаком опубликуйте или подскажите, где читать.
Спасибо. С уважением, Михаил.

[Vassil]

Не знаю ответ на Ваш вопрос.
Но, поиском в Google по Дикин И привел (как обычно бывает, в перемешку с однофамильными политиками и подозреваемыми в преступлении) примерно к такому линку

http://www.botik.ru/PSI/lib/new05/new9.html

где можно найти ссылку

12
ДИКИН И.И.
Решение задач линейного программирования методом внутренних точек. - Иркутск: Ин-т систем энергетики, 2005. - 35 с. - (Препринт ИСЭМ СО РАН, 2005, № 2).

Близко, мне кажется, к этой проблематики явно можно найти следующие интересные публикации на английском:

http://www.cs.cmu.edu/~guyb/realworld.html

и там посмотреть Lecture Notes (Fall 97) по линку

http://www.cs.cmu.edu/afs/cs/project/ps ... orld.ps.gz

, и в частности раздели LP1 и LP2.

По этой же теме, думаю можно в Интернете поиском в Google по Wang, O'Leary interior point methods in linear programming получить свободно краткую статью об адаптивном использовании итеративных методов внутренной точки --- pdf.

Надеюсь на снисхождение, если не отвечаю прямо в спрашиваемое.

[Mihail Gladkov]

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