Programmation linéaire entière en nombre logarithmique de variables

J'ai lu que la programmation linéaire entière est résoluble en temps polynominal si le nombre de variables est fixe, c'est-à-dire . Si le nombre de variables croît logarithmiquement, c'est-à-dire pour une entrée donnée de taille , le problème est-il toujours résoluble en temps polynominal ou s'agit-il d'un problème ouvert? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem user3613886
la source

Ne pouvez-vous pas ajouter des contraintes trivialement vraies pour augmenter la taille de l'entrée?

joro

Pourquoi voudriez-vous augmenter la taille de l'entrée?

user3613886

Pour rendre l'entrée si grande, le nombre de variables est logarithmique et correspond à votre question.

joro

mais dans la question, nous supposons déjà que les variables sont logarithmiques par rapport à la taille d'entrée

user3613886

J'ai pensé à faire de toutes les instances les vôtres, mais cela pourrait augmenter de façon exponentielle l'entrée.

joro

Réponses:

Je ne peux que répondre partiellement à cette question.

Un résultat de Lenstra (amélioré par la suite par Kannan et Frank et Tardos) indique que l'ILP avec variables peut être résolu en temps (fois un polynôme de la taille de l'ILP). Par conséquent, ILP est en P lorsque le nombre de variables est . Je ne sais pas si un algorithme est connu, ou si un tel algorithme serait en contradiction avec l'ETH. $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

J'ai trouvé cette information dans la thèse de Daniel Lokshtanov. Voici les références pertinentes.

HW Lenstra. Programmation entière avec un nombre fixe de variables. Mathématiques de la recherche opérationnelle, 8: 538-548, 1983.
R. Kannan. Théorème de corps convexe de Minkowski et programmation entière. Mathématiques de la recherche opérationnelle, 12: 415-440, 1987.
Andras Frank et Eva Tardos. Une application de l'approximation diophantienne simultanée en optimisation combinatoire. Combinatorica, 7: 49–65, 1987.

Michael Lampis
la source

Je pense que vous auriez besoin d'un algorithme O (k ^ p) pour un p fixe, car même un algorithme avec 2 ^ O (k) serait exponentiel?

user3613886

Désolé, j'ai utilisé une notation différente de la question. Par

k

$k$ Je veux dire le nombre de variables, et

n

$n$ est la taille de l'entrée, donc un

2^{k}

$2^{k}$ l'algorithme serait polynomial si

k = O (\log n)

$k=O(\log n)$ .

Michael Lampis

Mais supposons que vous n'ayez que des variables binaires, ce ne serait pas de la force brute

2^{k}

$2^k$ ?

user3613886

@ user3613886, bien sûr, mais c'est un problème / question différent. On ne nous avait pas promis dans la question que les variables étaient binaires.

Ne pouvez-vous pas ajouter des contraintes trivialement vraies pour augmenter la taille de l'entrée?

joro