Я просматривал этот сайт, и там говорится, что люди нашли решения для туров TSP, которые на 0,031% выше, чем оптимальный тур. Не найдя оптимального тура, откуда они знают, какой длины он должен быть?
complexity-theory
approximation
Илья Газман
источник
источник
Ответы:
В общем, когда вы хотите ограничить коэффициент аппроксимации алгоритма, вы ищете легкую нижнюю границу для оптимального значения. Самым простым является частичная релаксация LP (соответствующим образом выбранной) формулировки проблемы ILP. Иногда используются другие вещи, например, для TSP вы также можете использовать вес MST (оптимальный ход минус один край - дерево, поэтому он не может весить меньше, чем MST).
В определенных случаях вы, конечно, все еще можете использовать то, что вы используете в своих доказательствах, то есть вы можете решить LP и сравнить свое эвристическое решение со значением LP. Если у вас больше процессорного времени, вы также можете запустить процесс ветвления и ограничения для решения ILP. Даже если вы не решите ILP полностью, вы получите лучшие нижние границы от дуальности LP.
источник