APX | Worldlex Wiki

théorie de la complexité algorithmique , la classe APX (abréviation de « approximable ») désigne l'ensemble des problèmes d'optimisation NP admettant des algorithmes d'approximation en temps polynomial dont le facteur d'approximation est borné par une constante (ou algorithmes d'approximation à facteur constant ). Autrement dit, les problèmes de cette classe possèdent des algorithmes efficaces capables de trouver une solution à un facteur multiplicatif près de la solution optimale.

On dit qu'un problème admet un schéma d'approximation en temps polynomial (PTAS) si, pour tout facteur multiplicatif de l'optimum supérieur à 1, il existe un algorithme polynomial permettant de résoudre le problème à ce facteur près. Sauf si P = NP, il existe des problèmes appartenant à APX mais sans PTAS ; la classe des problèmes admettant un PTAS est donc strictement incluse dans APX. Le problème du sac à dos est un exemple de problème admettant un PTAS .

Dureté APX et complétude APX

Un problème est dit APX-difficile s'il admet une réduction PTAS de tout problème appartenant à APX vers ce problème, et APX-complet s'il est à la fois APX-difficile et APX-complet. Par conséquent, si P ≠ NP ⇒ PTAS ≠ APX, aucun problème APX-difficile n'admet de PTAS. En pratique, pour démontrer l'APX-complétude d'un problème, on utilise souvent d'autres schémas de réduction, comme les L-réductions , qui impliquent des réductions PTAS.

Exemples

L'un des problèmes APX-complets les plus simples est MAX-3SAT , une variante du problème de satisfaisabilité booléenne . Dans ce problème, on a une formule booléenne sous forme normale conjonctive où chaque variable apparaît au maximum 3 fois, et on cherche à déterminer le nombre maximal de clauses pouvant être satisfaites simultanément par une seule affectation de valeurs vrai/faux aux variables.

Parmi les autres problèmes liés à APX-complete, on peut citer :

Ensemble indépendant maximal dans les graphes à degré limité (ici, le rapport d'approximation dépend du degré maximal du graphe, mais est constant si le degré maximal est fixé).
Couverture minimale de sommets . Le complémentaire de tout ensemble indépendant maximal doit être une couverture de sommets.
Ensemble dominant minimal dans les graphes à degré borné.
Le problème du voyageur de commerce (TSP) est défini lorsque les distances dans le graphe satisfont aux conditions d'une métrique . Le TSP est NPO-complet dans le cas général.
Le problème de reconfiguration des jetons , via la L-réduction à partir de la couverture d'ensembles.

classes de complexité apparentées

PTAS

P = NP , il existe des problèmes APX qui ne sont ni APX-complets ni APX-complets. On peut considérer ces problèmes comme ayant une difficulté intermédiaire entre les problèmes APX-complets et les problèmes APX-complets, et les qualifier d' APX-intermédiaires . Le problème d'emballage de boîtes est considéré comme APX-intermédiaire. Bien qu'il n'existe pas de PTAS connu pour ce problème, il possède plusieurs algorithmes « PTAS asymptotiques », qui se comportent comme un PTAS lorsque la solution optimale est grande ; de ce fait, il peut intuitivement être considéré comme plus facile que les problèmes APX-difficiles.

Un autre exemple de problème potentiellement intermédiaire pour APX est la coloration minimale des arêtes .

f(n)-APX

On peut également définir une famille de classes de complexité -APX, où -APX regroupe les problèmes admettant un algorithme d'approximation en temps polynomial avec un facteur d'approximation donné. De même, on peut définir des classes -APX-complètes ; certaines de ces classes contiennent des problèmes d'optimisation bien connus. La complétude Log-APX et la complétude Poly-APX sont définies en termes de réductions AP plutôt que de réductions PTAS ; en effet, les réductions PTAS ne sont pas suffisamment fortes pour garantir l'appartenance à Log-APX et Poly-APX, même si elles le sont pour APX.

Log-APX-complet, composé des problèmes les plus difficiles qui peuvent être approximés efficacement à un facteur logarithmique près par rapport à la taille de l'entrée, inclut l'ensemble dominant minimal lorsque le degré est illimité.

Poly-APX-complet, constitué des problèmes les plus difficiles qui peuvent être approximés efficacement à un facteur polynomial près de la taille de l'entrée, inclut l'ensemble indépendant maximal dans le cas général.

Il existe également des problèmes exp-APX-complets, où le facteur d'approximation est exponentiel par rapport à la taille de l'entrée. Cela peut se produire lorsque l'approximation dépend de la valeur des nombres présents dans l'instance du problème ; ces nombres peuvent être exprimés de manière logarithmique dans l'espace, d'où le facteur exponentiel.