Comment limiter l'erreur d'une approximation sans connaître la solution optimale?

14

J'ai regardé ce site et il dit que les gens ont trouvé des solutions pour les tournées TSP qui sont juste 0,031% plus élevées que la tournée optimale. Sans trouver le tour optimal, comment savent-ils quelle longueur il est censé être?

complexity-theory approximation Ilya Gazman
la source
4
Les solutions sont AU MOINS 0,031% supérieures à la tournée optimale. Sans trouver le tour optimal, on peut encore trouver des bornes inférieures sur celui-ci et sur l'algorithme d'approximation, ce qui permet donc de "comparer" des solutions approchées avec une solution optimale.
Tpecatte
3
Vous devriez vraiment, vraiment prendre un livre sur la théorie de la complexité et / ou comment résoudre des problèmes NP-difficiles . Vous avez peu d'espoir de réellement résoudre P? = NP au cours de votre vie et de convaincre quiconque que vous l'avez fait si vous continuez à pousser des propositions / questions prouvant que vous n'avez pas compris les concepts de premier cycle. Bien sûr, nous pouvons vous aider à parvenir à cette compréhension.
Raphael
il serait utile de citer la personne qui indique cette limite [TO, idem]. afaik, il n'y a pas une telle limite de temps P connue en général. il existe d'autres limites d'approximation exprimées en fonction des paramètres du problème, par exemple des points, etc.
vzn

Réponses:

8

En général, lorsque vous souhaitez limiter le rapport d'approximation d'un algorithme, vous recherchez une borne inférieure facile sur la valeur optimale. Le plus simple est souvent le relaxation LP d'une formulation ILP (convenablement choisie) du problème. Parfois, d'autres choses sont utilisées, pour TSP par exemple, vous pouvez également utiliser le poids d'un MST (le tour optimal moins un bord est un arbre, donc il ne peut pas peser moins que le MST).

Pour des cas particuliers, vous pouvez bien sûr toujours utiliser ce que vous utilisez dans vos preuves, c'est-à-dire que vous pouvez résoudre le LP et comparer votre solution heuristique à la valeur LP. Si vous disposez de plus de temps processeur, vous pouvez également démarrer un processus de branchement et de liaison pour résoudre l'ILP. Même si vous ne résolvez pas complètement l'ILP, vous obtenez de meilleures limites inférieures de la dualité LP.

adrianN
la source
Pouvez-vous s'il vous plaît expliquer ou me donner un lien pour en savoir plus. Qu'est-ce que LP, ILP, MST
Ilya Gazman
1
J'ai modifié ma réponse pour inclure des liens wikipedia.
adrianN