Collection de problèmes difficiles APX

Tout le monde connaît "Garey & Johnson", qui est ma référence à chaque fois que j'ai besoin d'un problème de transformation pour une preuve de dureté NP. Cependant, j'ai récemment eu besoin d'une preuve de dureté APX, et je me demande s'il existe une collection similaire (et plus à jour ..?) De problèmes qui se sont révélés être durs APX.

Quelqu'un sait-il quelque chose comme ça? J'ai du mal à croire qu'il n'y a pas de site web qui recueille systématiquement de tels problèmes, mais mes compétences Google semblent insuffisantes.

complexity-theory reference-request time-complexity complexity-classes Lukas Barth
la source

Réponses:

J'ai utilisé ce recueil à quelques reprises ... Est-ce ce que vous visiez?

Parzan
la source

C'est déjà très joli, merci! Cependant, l'optimum serait quelque chose d'encore plus complet, et consultable pour la dureté APX ... Je verrai si autre chose apparaît.

Lukas Barth

Pouvez-vous fournir des informations de citation qui vous aideront à trouver ces informations si le lien cesse de fonctionner? Nous voulons que les réponses restent utiles même si le lien cesse de fonctionner (et nous préférerions ne pas être simplement une ferme de liens).

Il semble que cette collection fasse partie d'un livre, à savoir: Ausiello, Giorgio, et al. Complexité et approximation: problèmes d'optimisation combinatoire et leurs propriétés d'approximation. Springer Science & Business Media, 2012. springer.com/us/book/9783540654315 DOI: 10.1007 / 978-3-642-58412-1

Lukas Barth