Целочисленное линейное программирование в логарифмическом числе переменных

Я читал, что целочисленное линейное программирование разрешимо за полиноминальное время, если число переменных фиксировано, т.е. . Если число переменных растет логарифмически, т. для заданного входного значения размера , проблема все еще разрешима за полиноминальное время или это открытая проблема? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem user3613886
источник

Разве вы не можете добавить тривиально истинные ограничения, чтобы увеличить размер ввода?

Joro

Почему вы хотите увеличить размер ввода?

user3613886

Чтобы сделать ввод таким большим, чтобы количество переменных было логарифмическим и соответствовало вашему вопросу.

Joro

но в вопросе мы уже предполагаем, что переменные являются логарифмическими по сравнению с размером ввода

user3613886

Я думал о создании всех экземпляров как ваших, но это может экспоненциально увеличить вход.

Joro

Ответы:

Я могу дать только частичный ответ на этот вопрос.

Результат Ленстры (позже улучшенный Каннаном, Фрэнком и Тардосом) утверждает, что ILP с переменными может быть решена за время (умноженное на полином по размеру ILP). Поэтому ILP находится в P, когда число переменных равно . Я не уверен, известен ли алгоритм или такой алгоритм противоречил бы ETH. $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

Я нашел эту информацию в диссертации Данила Локштанова. Вот соответствующие ссылки.

HW Lenstra. Целочисленное программирование с фиксированным числом переменных. Математика исследования операций, 8: 538–548, 1983.
Р. Каннан. Теорема Минковского о выпуклом теле и целочисленное программирование. Математика исследования операций, 12: 415–440, 1987.
Андрас Франк и Ева Тардос. Применение одновременной диофантовой аппроксимации в комбинаторной оптимизации. Combinatorica, 7: 49–65, 1987.

Майкл Лэмпис
источник

Я думаю, что вам понадобится алгоритм O (k ^ p) для фиксированного p, поскольку даже алгоритм с 2 ^ O (k) будет экспоненциальным?

user3613886

k

$k$

n

$n$

2^{k}

$2^{k}$

k = O (\log n)

$k=O(\log n)$

2^{k}

$2^k$

@ user3613886, конечно, конечно, но это другая проблема / вопрос. Мы не были обещаны в вопросе, что переменные являются двоичными.

Разве вы не можете добавить тривиально истинные ограничения, чтобы увеличить размер ввода?

Joro