Całkowite programowanie liniowe w logarytmicznej liczbie zmiennych

Czytałem, że całkowite programowanie liniowe jest rozwiązywalne w czasie wielomianowym, jeśli liczba zmiennych jest stała, tj. . Jeśli liczba zmiennych rośnie logarytmicznie, tj. dla danych wejściowych o rozmiarze , czy problem jest nadal możliwy do rozwiązania w czasie wielomianowym, czy jest to problem otwarty? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem

— użytkownik3613886
źródło

Czy nie można dodać trywialnie prawdziwych ograniczeń, aby zwiększyć rozmiar danych wejściowych?

— joro

Dlaczego warto zwiększyć rozmiar danych wejściowych?

— user3613886,

Aby dane wejściowe były tak duże, aby liczba zmiennych była logarytmiczna i pasowała do twojego pytania.

— joro

ale w pytaniu zakładamy, że zmienne są logarytmiczne w porównaniu do wielkości wejściowej

— 3613886

Pomyślałem o stworzeniu wszystkich instancji jako własnych, ale może to wykładniczo zwiększyć dane wejściowe.

— joro

Mogę tylko częściowo odpowiedzieć na to pytanie.

Wynik Lenstry (później poprawiony przez Kannana, Franka i Tardosa) stwierdza, że ILP ze zmiennymi można rozwiązać w czasie $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

Znalazłem tę informację w rozprawie Daniela Lokshtanova. Oto odpowiednie odniesienia.

HW Lenstra. Programowanie liczb całkowitych ze stałą liczbą zmiennych. Mathematics of Operations Research, 8: 538–548, 1983.
R. Kannan. Twierdzenie wypukłego ciała Minkowskiego i programowanie liczb całkowitych. Mathematics of Operations Research, 12: 415–440, 1987.
Andras Frank i Eva Tardos. Zastosowanie równoczesnego zbliżenia diofantyny w optymalizacji kombinatorycznej. Combinatorica, 7: 49–65, 1987.

— Michael Lampis
źródło

Myślę, że potrzebujesz algorytmu O (k ^ p) dla stałego p, ponieważ nawet algorytm z 2 ^ O (k) byłby wykładniczy?

— user3613886

Przepraszam, użyłem innej notacji niż pytanie. Przez

rozumiem liczbę zmiennych, a

jest rozmiarem danych wejściowych, więc algorytm

byłby czasem wielomianowym, gdyby

k

$k$

n

$n$

2^{k}

$2^{k}$

k = O (\log n)

$k=O(\log n)$

Ale załóżmy, że masz tylko zmienne binarne, nie byłaby to brutalna siła

2^{k}

$2^k$

@ user3613886, oczywiście, ale to inny problem / pytanie. Nie obiecano nam, że zmienne są binarne.

— DW

Czy nie można dodać trywialnie prawdziwych ograniczeń, aby zwiększyć rozmiar danych wejściowych?

— joro