Programação linear inteira em número logarítmico de variáveis

Eu li que a programação linear inteira é solucionável em tempo polinominal se o número de variáveis for fixo, ou seja, . Se o número de variáveis cresce logaritmicamente, ou seja, para uma determinada entrada de tamanho , o problema ainda pode ser solucionado no tempo polinominal ou é um problema em aberto? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem user3613886
fonte

Você não pode adicionar restrições trivialmente verdadeiras para aumentar o tamanho da entrada?

Joro

Por que você deseja aumentar o tamanho da entrada?

precisa saber é o seguinte

Para tornar a entrada tão grande, o número de variáveis é logarítmico e se encaixa na sua pergunta.

joro

mas na questão já assumimos que as variáveis são logarítmicas em comparação com o tamanho da entrada

user3613886

Pensei em criar todas as instâncias como sua, mas isso pode aumentar exponencialmente a entrada.

joro

Respostas:

Só posso dar uma resposta parcial a esta pergunta.

Um resultado de Lenstra (posteriormente aprimorado por Kannan, e Frank e Tardos) afirma que o ILP com variáveis pode ser resolvido no tempo (vezes um polinômio no tamanho do ILP). Portanto, o ILP está em P quando o número de variáveis é . Não tenho certeza se um algoritmo de é conhecido ou se esse algoritmo contradiz o ETH. $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

Encontrei essa informação na dissertação de Daniel Lokshtanov. Aqui estão as referências relevantes.

HW Lenstra. Programação inteira com um número fixo de variáveis. Mathematics of Operations Research, 8: 538-548, 1983.
R. Kannan. Teorema do corpo convexo de Minkowski e programação inteira. Mathematics of Operations Research, 12: 415-440, 1987.
Andras Frank e Eva Tardos. Uma aplicação de aproximação diofantina simultânea na otimização combinatória. Combinatorica, 7: 49–65, 1987.

Michael Lampis
fonte

Eu acho que você precisaria de um algoritmo O (k ^ p) para um p fixo, já que mesmo um algoritmo com 2 ^ O (k) seria exponencial?

precisa saber é o seguinte

Desculpe, usei uma notação diferente da pergunta. Por

quero dizer o número de variáveis, e

é o tamanho da entrada; portanto, um algoritmo de

teria um tempo polinomial se

k

$k$

n

$n$

2^{k}

$2^{k}$

k = O (\log n)

$k=O(\log n)$

Michael Lampis

Mas suponha que você tenha apenas variáveis binárias, não seria a força bruta

2^{k}

$2^k$

precisa saber é o seguinte

@ user3613886, claro, claro, mas esse é um problema / pergunta diferente. Não nos prometeram na pergunta que as variáveis são binárias.

Você não pode adicionar restrições trivialmente verdadeiras para aumentar o tamanho da entrada?

Joro