Какова верхняя граница симплексного алгоритма для поиска решения линейной программы? Как мне найти доказательства для такого случая? Кажется, что наихудший случай - посещение каждой вершины, то есть . Однако на практике симплексный алгоритм будет работать значительно быстрее, чем этот, для более...
Одним из основных принципов разработки алгоритма является нахождение сильно полиномиального алгоритма для линейного программирования, т. Е. Алгоритма, время выполнения которого ограничено полиномом по числу переменных и ограничений и не зависит от размера представления параметров (при условии...
Насколько я понимаю, все известные детерминированные сводные правила для симплексных алгоритмов имеют конкретные входные данные, для которых алгоритму требуется экспоненциальное время (или, по крайней мере, не полиномиальное), чтобы найти оптимальный. Давайте назовем эти случаи «патологическими»,...
Я написал реализацию алгоритма Куна-Мункреса для задачи идеального соответствия двудольных с минимальным весом на основе лекционных заметок, которые я нашел здесь и там в Интернете. Это работает очень хорошо, даже на тысячах вершин. И я согласен, что теория, стоящая за этим, действительно...
Я заинтересован в реализации SM для задачи LP, однако я слышал о возможных подводных камнях: книга Кормена говорит, что возможно иметь входные данные, которые приведут к тому, что наивная реализация будет вести себя экспоненциально. Я также слышал, что наивная реализация может зацикливаться на...