L'étude structurelle vise à déterminer les propriétés intrinsèques des problèmes qui permettent de garantir (ou, au contrainte, d'interdire) un certain degré d'approximation.

Tout d'abord, l'approche locale à partir de voisinages h-bornés : à la lumiére des exemples présentés [MPT03], cette approche pose trois axes d'étude. Quelle est l'influence de la taille du voisinage (ex. : positive pour MaxK3-free Partial Subgraph, nulle pour MaxkSat) ? Quelle est l'influence des solutions opposées (ex. : pour MinDS, les optima locaux vis-à-vis du voisinage h-borné sont une 0-approximation tandis que la prise en compte de la solution opposée produit une 1/2-approximation ; pour Min2CCSP, on améliore le rapport classique d'approximation locaux de 1/4 à 1/3) ? Quelle est l'influence de la fonction objectif considérée (ex. : pour MaxkSat, en considérant conjointement les solutions opposées et un objectif altéré, le rapport de k/(k+1) est porté à 2k/(2k+1)) ?

De plus, la diversité des problèmes [MPT03] dont nous avons montré qu'ils avaient des optima locaux de qualité garantie (ex. : MinMS(k) admet un schéma d'approximation et garantit la qualité de ses optima locaux ; MinTSP(k) n'admet pas de schéma d'approximation mais garantit la qualité de ses optima locaux ; enfin MaxKS(k){0,1}, bien que polynomial, ne garantit pas la qualité de ses optima locaux) incite à poursuivre dans la voie de la caractérisation des problèmes se comportant bien, de par leur modèle mathématique ou leurs propriétés combinatoires, plutôt que d'apporter des réponses de façon isolée. Par exemple, nous avons établi que les problèmes de partitionnement héréditaires ont tous des optima locaux de qualité différentielle garantie ; or, cette famillle comporte des problèmes de statut hétérogène vis-à-vis de leur degré d'approximation : MinBP qui admet un schéma différentiel d'approximation, MinC qui "n'est qu"'approximable à rapport constant. Cette volonté de caractérisation a également motivé l'étude des problèmes radiaux.

Mais la notion d'optimalité locale pourrait garantir la qualité des solutions au-delà des voisinages de type h-bornés. Par exemple, la couverture d'ensemble considérée dans [BMPS04] est le complémentaire d'un optimum 2-local pour un certain objectif ; aller chercher la solution approchée dans un ensemble complémentaire est une voie à systématiser. Autre voie prometteuse : l'identification d'un problème maître "difficile" et d'un sous-problème "facile" quand la solution du problème maître est connue (c'est le cas des problèmes de localisation d'émetteurs et d'arbre couvrant de profondeur k) ; alors, appliquer la notion de voisinage au seul problème maître pourrait mener à de nouvelles caractérisations a priori du degré d'approximation des problèmes d'optimisation combinatoire.

Enfin, au-delà même de l'approche locale, c'est la confrontation des approches heuristiques simples à des modèles génériques qu'il conviendrait de faire : je pense notamment aux techniques de réparation ou de décomposition, qui s'avèrent souvent très efficaces et dont il semblerait pertinent de généraliser la portée (plutôt, une fois encore, que d'en faire l'analyse pour des problèmes spécifiques).

[BMPS04] C. Bazgan, J. Monnot, V. Th. Paschos, F. Serrière
Differential approximations for min set cover
(soumis)

[MPT03] J. Monnot, V. Th. Paschos, S. Toulouse,
Approximation polynomiale des problèmes NP-difficiles - Optima locaux et rapport différentiel
Hermes Science, janvier 2003