La programmation linéaire admet-elle un algorithme fortement polynomial?

12

Le problème de programmation linéaire: trouver un algorithme de temps fortement polynomial qui pour une matrice donnée A ∈ Rm × n et b ∈ Rm décide s'il existe x ∈ Rn avec Ax ≥ b.

Je sais que Steve Smale énumère certains des problèmes non résolus en mathématiques. Mais un tel problème de programmation linéaire est-il jusqu'à présent insoluble?

algorithms polynomial-time linear-programming Krebto
la source
Les problèmes de programmation linéaire semblent être résolus en temps polynomial en utilisant l'algorithme Simplex, c'est juste la preuve qui manque. Plus le problème qu'il pourrait y avoir des contre-exemples, mais ils semblent très difficiles à trouver.
gnasher729
2
@ gnasher729 Il existe des contre-exemples connus, par exemple le cube Klee-Minty . D'un autre côté, il existe des algorithmes de points intérieurs connus pour fonctionner en temps (faiblement) polynomial.
Tavian Barnes
Cet article est lié: cc.gatech.edu/~vempala/papers/affine.pdf
Erel Segal-Halevi

Réponses:

12

Ce problème est toujours ouvert. Voir par exemple Wikipédia , qui, bien que n'étant pas une source fiable en général, sera probablement mis à jour si un algorithme temporel fortement polynomial est jamais trouvé.

Yuval Filmus
la source