Точные алгоритмы экспоненциального времени для программ 0-1 с неотрицательными данными

9

Существуют ли известные алгоритмы для следующей задачи, которые побеждают наивный алгоритм?

Входные данные: матрица и векторы , где все элементы являются неотрицательными целыми числами.Ab,cA,b,c

Вывод: оптимальное решение от до .xmax{cTx:Axb,x{0,1}n}

Этот вопрос является уточненной версией моего предыдущего вопроса Точные алгоритмы экспоненциального времени для программирования 0-1 .

Остин Бьюкенен
источник

Ответы:

5

если число ненулевых коэффициентов в A является линейным по n , существует алгоритм, который решает эту проблему менее чем за 2n времени.

Вот как это работает. Мы используем стандартную связь между задачей оптимизации и соответствующей ей проблемой решения. Чтобы проверить, существует ли решение где и , мы сформируем решение задачи: мы присоединим ограничение к матрице и проверим существует ли такой , что и . В частности, мы сформируем новую матрицу , взяв и добавив дополнительную строку, содержащую , и мы сформируем , взявxAxbcTxαcTxαAxAxbcTxαAAcTbbи добавление дополнительной строки с . Мы получаем решение задачи: существует ли такое, что ? Ответ на эту проблему решения говорит нам, существует ли решение исходной задачи оптимизации значения или больше. Более того, как объяснено в ответе на ваш предыдущий вопрос , эта проблема решения может быть решена менее чем за раз, если число ненулевых коэффициентов в линейно по (и, таким образом, если число ненулевых нулевые коэффициенты в линейны по ). Теперь мы можем использовать бинарный поиск поαx{0,1}nAxbα2nAnAnαрешить вашу проблему оптимизации менее чем за раз.2n

Я благодарен AustinBuchanan и Stefan Schneider за помощь в отладке более ранней версии этого ответа.

DW
источник
Можете ли вы дать более сильный ответ: например, «существует алгоритм времени » или «алгоритм, опережающий , опровергнет ...»? O(2n/2)O(2n)
Остин Бьюкенен
@AustinBuchanan, если число измерений достаточно мало, есть алгоритм , как описано в моем ответе на другой вопрос . Это лучшее, что я знаю, как сделать; Я не знаю, как сделать лучше, чем это. Может быть, другие смогут дать более сильный ответ! bO(2n/2)
DW
O(2n/2) время удерживается всякий раз, когда число ограничений равно ? O(1)
Остин Бьюкенен
4

Если мы рассмотрим задачу минимизации , то следующее сокращение показывает, что алгоритм работает за время для опровергнет SETH. Переформулировка доказывает тот же результат для намеченной проблемы (версия максимизации).miny{cTy:Ayb,y{0,1}n}O(2δn/2)δ<1

Учитывая экземпляр CNF-SAT с переменными , сформулируйте 0-1 IP с двумя переменными для каждой переменной в экземпляре SAT. Как обычно, предложение будет представлено как . Затем для каждой переменной в экземпляре SAT добавьте ограничение . Цель состоит в том, чтобы минимизировать . Цель IP будет тогда и только тогда , например SAT выполнима.Φ=i=1mCi{xj}j=1nyj,y¯jxj(x1x¯2x3)y1+y¯2+y31xjyj+y¯j1j=1n(yj+y¯j)n

Спасибо Стефану Шнайдеру за исправление.

Обновление: в « Проблемах столь сложных, как CNF-Sat», авторы предполагают, что SET COVER не может быть решена за время , , где относится к числу наборов. Если это правда, это покажет, что моя проблема также не может быть решена за время .O(2δn)δ<1nO(2δn)

Обновление 2. Насколько я могу судить, предполагая, что SETH, моя проблема не может быть решена за время , так как было показано, что Набор удара (с базовым набором размера ) не может быть решено за время .O(2δn)nO(2δn)

Остин Бьюкенен
источник
3
Поскольку вы удваиваете число переменных, я думаю, что это только показывает, что алгоритм для этой задачи со временем выполнения будет противоречить SETH. O(2δn/2)
Стефан Шнайдер
Подождите ... авторы из по проблемам , как трудно , как CNF-SAT состояния , что «для каждого , алгоритм задерживаясь Set нарушило бы СЕТ.» Разве это не работает? ϵ<1O(2ϵn)
Остин Бьюкенен