Cтраница 2
Можно сформулировать приведенные выше доводы иначе, заметив, что метод эллипсоидов сводит за полиномиальное время задачу нахождения совершенного паросочетания с максимальным весом к задаче о У ( С) - разрезе с минимальным весом. Рассуждения очень похожи на те, которые можно привести, чтобы показать, что задачу о К ( Сг) - разрезе с минимальным весом можно свести к задаче о совершенном паросочетаний с максимальным весом. Таким образом, метод эллипсоидов устанавливает эквивалентность этих двух задач в рамках полиномиально временных алгоритмов. Нам известны комбинаторные алгоритмы, решающие данные задачи непосредственно - это, соответственно, алгоритмы Эдмондса и Падберга - Рао. Весьма удивительно, что некоторые общие геометрические методы вроде метода эллипсоидов указывают нам на то, что решение одной из этих задач автоматически влечет за собой решение другой задачи, по крайней мере в свете интересующей нас полиномиальности времени работы алгоритмов. [16]
Следовательно, собственные векторы этого тензора второго ранга направлены вдоль главных осей эллипса сечения. В соответствии с (4.3.8) значения п определяются длинами главных осей. Это доказывает эквивалентность метода эллипсоида показателей преломления и метода, описанного в предыдущем разделе. [17]
До некоторой степени, однако, некоторые границы нечетки. Линейное программирование, например, имеет аномальный статус - наиболее широко используемые на практике алгоритмы решения таких задач нехороши в теоретическом смысле, а те, что хороши теоретически, нехороши для практики. Одним из примеров является метод эллипсоидов, бывший объектом пристального внимания шесть лет назад. Он выполнялся за полиномиальное время, но полином был такой высокой степени, что этот метод хорош лишь в смысле формального соответствия теоретическому критерию и неэффективен на практике. Причина состоит в том, что понятие полиномиального по времени алгоритма неточно передает содержание интуитивного представления об эффективных алгоритмах, - объясняет Карп. Когда степень полинома доходит до 5 или 6, то трудно назвать такой алгоритм действительно эффективным. Таким образом, предложенное Эдмондсом понятие хорошего алгоритма - недостаточно совершенная формализация хорошего в интуитивном смысле. Далее, симплекс-алгоритм хорош на практике во всех отношениях, замечает Карп, но недостаточно хорош в соответствии со стандартной парадигмой теории сложности. Последнее добавление к решениям линейного программирования - алгоритм, построенный Нарендой Кармаркаром и, по мнению некоторых, бросающий вызов симплекс-алгоритму, хорош в техническом смысле и также, видимо, вполне эффективен на практике, говорит Карп. [18]
Во-первых, в линейном программировании не был известен алгоритм, выполняемый за полиномиальное время, а во-вторых, даже если бы мы отбросили это препятствие как несущественное с практической точки зрения - ведь есть метод симплекса, весьма эффективный на практике, - оставшаяся трудность заключалась бы в том, что перечень неравенств, указанный в теореме 7.3.1, для графов общего вида экспоненциально велик. Напомним, однако ( см. Вставку 7В), что метод эллипсоидов не только полиномиален даже в худшем случае, но, к тому же, не требует полного перечня всех ограничений. [19]