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

Odpowiedzi:

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.

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

joro