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

16

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

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:

15

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 k O ( k ) (vezes um polinômio no tamanho do ILP). Portanto, o ILP está em P quando o número de variáveis ​​é O ( log n / log log n ) . Não tenho certeza se um algoritmo de 2 O ( k ) é conhecido ou se esse algoritmo contradiz o ETH.kkO(k)O(registron/registroregistron)2O(k)

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

  1. HW Lenstra. Programação inteira com um número fixo de variáveis. Mathematics of Operations Research, 8: 538-548, 1983.

  2. R. Kannan. Teorema do corpo convexo de Minkowski e programação inteira. Mathematics of Operations Research, 12: 415-440, 1987.

  3. 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 n é o tamanho da entrada; portanto, um algoritmo de 2 k teria um tempo polinomial se k = O ( log n ) . kn2kk=O(registron)
Michael Lampis
Mas suponha que você tenha apenas variáveis ​​binárias, não seria a força bruta ? 2k
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.
DW
Você não pode adicionar restrições trivialmente verdadeiras para aumentar o tamanho da entrada?
Joro