Programación lineal entera en número logarítmico de variables

Leí que la programación lineal entera se puede resolver en tiempo polinominal si el número de variables es fijo, es decir, . Si el número de variables crece logarítmicamente, es decir, para una entrada dada de tamaño , ¿el problema aún se puede resolver en tiempo polinominal o es un problema abierto? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem usuario3613886
fuente

¿No puede agregar restricciones trivialmente verdaderas para aumentar el tamaño de la entrada?

joro

¿Por qué debería querer aumentar el tamaño de la entrada?

user3613886

Para que la entrada sea tan grande que el número de variables sea logarítmico y se ajuste a su pregunta.

joro

pero en la pregunta ya asumimos que las variables son logarítmicas en comparación con el tamaño de entrada

user3613886

Pensé en hacer todas las instancias como suyas, pero esto podría aumentar exponencialmente la entrada.

joro

Respuestas:

Solo puedo dar una respuesta parcial a esta pregunta.

Un resultado de Lenstra (luego mejorado por Kannan y Frank y Tardos) afirma que ILP con variables se pueden resolver en el tiempo (multiplicado por un polinomio en el tamaño de ILP). Por lo tanto, ILP está en P cuando el número de variables es . No estoy seguro de si se conoce un algoritmo de , o si dicho algoritmo contradeciría el ETH. $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

Encontré esta información en la disertación de Daniel Lokshtanov. Aquí están las referencias relevantes.

HW Lenstra. Programación de enteros con un número fijo de variables. Mathematics of Operations Research, 8: 538–548, 1983.
R. Kannan. Teorema del cuerpo convexo de Minkowski y programación de enteros. Mathematics of Operations Research, 12: 415–440, 1987.
Andras Frank y Eva Tardos. Una aplicación de aproximación de diofantina simultánea en la optimización combinatoria. Combinatorica, 7: 49–65, 1987.

Michael Lampis
fuente

Creo que necesitarías un algoritmo O (k ^ p) para una p fija, ya que incluso un algoritmo con 2 ^ O (k) sería exponencial?

user3613886

Lo siento, usé una notación diferente de la pregunta. Por

quiero decir el número de variables, y

es el tamaño de la entrada, por lo que un algoritmo de

sería de tiempo polinomial si

k

$k$

n

$n$

2^{k}

$2^{k}$

k = O (\log n)

$k=O(\log n)$

Michael Lampis

Pero supongamos que tiene solo variables binarias, ¿no sería fuerza bruta

2^{k}

$2^k$

user3613886

@ user3613886, claro, por supuesto, pero ese es un problema / pregunta diferente. No se nos prometió en la pregunta que las variables son binarias.

¿No puede agregar restricciones trivialmente verdaderas para aumentar el tamaño de la entrada?

joro