если число ненулевых коэффициентов в A является линейным по n , существует алгоритм, который решает эту проблему менее чем за 2n времени.
Вот как это работает. Мы используем стандартную связь между задачей оптимизации и соответствующей ей проблемой решения. Чтобы проверить, существует ли решение где и , мы сформируем решение задачи: мы присоединим ограничение к матрице и проверим существует ли такой , что и . В частности, мы сформируем новую матрицу , взяв и добавив дополнительную строку, содержащую , и мы сформируем , взявxAx≤bcTx≥αcTx≥αAxAx≤b−cTx≤−αA′A−cTb′bи добавление дополнительной строки с . Мы получаем решение задачи: существует ли такое, что ? Ответ на эту проблему решения говорит нам, существует ли решение исходной задачи оптимизации значения или больше. Более того, как объяснено в ответе на ваш предыдущий вопрос , эта проблема решения может быть решена менее чем за раз, если число ненулевых коэффициентов в линейно по (и, таким образом, если число ненулевых нулевые коэффициенты в линейны по ). Теперь мы можем использовать бинарный поиск по−αx∈{0,1}nA′x≤b′α2nA′nAnαрешить вашу проблему оптимизации менее чем за раз.2n
Я благодарен AustinBuchanan и Stefan Schneider за помощь в отладке более ранней версии этого ответа.
Можете ли вы дать более сильный ответ: например, «существует алгоритм времени » или «алгоритм, опережающий , опровергнет ...»? O(2n/2)O(2n)
Остин Бьюкенен
@AustinBuchanan, если число измерений достаточно мало, есть алгоритм , как описано в моем ответе на другой вопрос . Это лучшее, что я знаю, как сделать; Я не знаю, как сделать лучше, чем это. Может быть, другие смогут дать более сильный ответ! bO∗(2n/2)
DW
O∗(2n/2) время удерживается всякий раз, когда число ограничений равно ? O(1)
Остин Бьюкенен
4
Если мы рассмотрим задачу минимизации , то следующее сокращение показывает, что алгоритм работает за время для опровергнет SETH. Переформулировка доказывает тот же результат для намеченной проблемы (версия максимизации).miny{cTy:Ay≥b,y∈{0,1}n}O(2δn/2)δ<1
Учитывая экземпляр CNF-SAT с переменными , сформулируйте 0-1 IP с двумя переменными для каждой переменной в экземпляре SAT. Как обычно, предложение будет представлено как . Затем для каждой переменной в экземпляре SAT добавьте ограничение . Цель состоит в том, чтобы минимизировать . Цель IP будет тогда и только тогда , например SAT выполнима.Φ=∧mi=1Ci{xj}nj=1yj,y¯¯¯jxj(x1∨x¯¯¯2∨x3)y1+y¯¯¯2+y3≥1xjyj+y¯¯¯j≥1∑nj=1(yj+y¯¯¯j)n
Спасибо Стефану Шнайдеру за исправление.
Обновление: в « Проблемах столь сложных, как CNF-Sat», авторы предполагают, что SET COVER не может быть решена за время , , где относится к числу наборов. Если это правда, это покажет, что моя проблема также не может быть решена за время .O(2δn)δ<1nO(2δn)
Обновление 2. Насколько я могу судить, предполагая, что SETH, моя проблема не может быть решена за время , так как было показано, что Набор удара (с базовым набором размера ) не может быть решено за время .O(2δn)nO(2δn)
Поскольку вы удваиваете число переменных, я думаю, что это только показывает, что алгоритм для этой задачи со временем выполнения будет противоречить SETH. O(2δn/2)
Стефан Шнайдер
Подождите ... авторы из по проблемам , как трудно , как CNF-SAT состояния , что «для каждого , алгоритм задерживаясь Set нарушило бы СЕТ.» Разве это не работает? ϵ<1O(2ϵn)…
Если мы рассмотрим задачу минимизации , то следующее сокращение показывает, что алгоритм работает за время для опровергнет SETH. Переформулировка доказывает тот же результат для намеченной проблемы (версия максимизации).miny{cTy:Ay≥b,y∈{0,1}n} O(2δn/2) δ<1
Учитывая экземпляр CNF-SAT с переменными , сформулируйте 0-1 IP с двумя переменными для каждой переменной в экземпляре SAT. Как обычно, предложение будет представлено как . Затем для каждой переменной в экземпляре SAT добавьте ограничение . Цель состоит в том, чтобы минимизировать . Цель IP будет тогда и только тогда , например SAT выполнима.Φ=∧mi=1Ci {xj}nj=1 yj,y¯¯¯j xj (x1∨x¯¯¯2∨x3) y1+y¯¯¯2+y3≥1 xj yj+y¯¯¯j≥1 ∑nj=1(yj+y¯¯¯j) n
Спасибо Стефану Шнайдеру за исправление.
Обновление: в « Проблемах столь сложных, как CNF-Sat», авторы предполагают, что SET COVER не может быть решена за время , , где относится к числу наборов. Если это правда, это покажет, что моя проблема также не может быть решена за время .O(2δn) δ<1 n O(2δn)
Обновление 2. Насколько я могу судить, предполагая, что SETH, моя проблема не может быть решена за время , так как было показано, что Набор удара (с базовым набором размера ) не может быть решено за время .O(2δn) n O(2δn)
источник