Вопросы с тегом «primal-dual»

19
Интуитивное / неформальное доказательство LP Duality?

Что было бы хорошим неофициальным / интуитивно понятным доказательством того, что «удар по теме» о дуальности ЛП? Как лучше всего показать, что минимизированная целевая функция действительно является минимальной с интуитивным способом понимания границ? То, как меня учили, дуальность привела только...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

14
Обобщение венгерского алгоритма на общие неориентированные графы?

Венгерский алгоритм - это комбинаторный алгоритм оптимизации, который решает проблему согласования двудольных с максимальным весом за полиномиальное время и предвосхищает дальнейшее развитие важного первично-двойственного метода . Алгоритм был разработан и опубликован Гарольдом Куном в 1955 году,...

14
Достаточно ли, чтобы линейные программные ограничения были выполнены в ожидании?

В статье « Рандомизированный анализ ранга-двойственности RANKING для сопоставления двухчастных он- лайн , доказывая, что алгоритм RANKING является -конкурентоспособным, авторы показывают, что двойственное возможно в ожидание (см. лемму 3 на стр. 5). Мой вопрос:( 1 - 1е)(1-1е)\left(1 -...

10
Почему важна дополнительная расслабленность?

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

10
Когда разрыв в двойственности полуопределенного программирования (SDP) равен нулю?

Я не смог найти в литературе точную характеристику исчезновения разрыва двойственности СДП. Или когда держится «сильная двойственность»? Например, когда кто-то переходит между Лассерром и SDP SDP, в принципе у него есть пробел в дуальности. Однако, почему-то, кажется, есть какая-то «тривиальная»...