Le problème du voyageur de commerce (TSP) consiste, étant donné un graphe complet muni d'une fonction de distance sur les arêtes, à trouver un tour de distance minimale. Dans un graphe non orienté, un tour est un cycle sélémentaire qui passe une et une seule fois par chaque sommet du graphe. La valeur d'une solution est la somme des distances des arêtes qui la composent.
[MTP032] TSPab (problème du voyageur de commerce, versions minimisation et maximisation, instances métriques particulières où la fonction distance est à valeur dans {ab}) est 3/4-approximable en différentiel, MaxTSP12 est 7/8-approximable en classique  l'algorithme analysé, comme celui de [PY93], se base sur un 2-couplage parfait sans triangle de poids optimal.

Le problème du partitionnement des sommets d'un graphe par des chaînes de longueur 3 (P4P) consiste, étant donné un graphe complet non orienté muni d'une fonction de distance sur les arêtes, à trouver un ensemble de chaînes de longueur 3 deux à deux sommet-disjointes qui couvre les sommets du graphe (tout sommet doit appartenir à une chaîne de la partition) et qui soit de distance minimale. La valeur d'une partition est donnée par la somme des distances des arêtes qui composent ses chaînes.
[MT05] Les instances métriques MinMetricP4P, MinP4P12 et MaxP4P12 sont respectivement 3/2-, 7/6- et 9/10-approximables en classique  en différentiel, P4P (versions minimisation et maximisation) est 1/2-approximable tandis que la restriction P4Pab à une fonction de distance bivalente est 2/3-approximable. L'algorithme analysé est celui proposé dans [HR97] et consiste à construire deux couplages parfaits imbriqués de poids optimal.

Les problèmes de logique jouent un rôle central en théorie de la complexité puisqu'ils sont fournisseurs de problèmes complets en décision comme en approximation. Or, en différentiel, ces problèmes sont difficiles à approcher, bien que leur statut ne soit pas encore décidé. Néanmoins, on sait par exemple que MinSat [MTP031], même lorsque l'on se restreint à des clauses de Horn, n'est pas approximable à rapport différentiel constant. Pire encore, la programmation linéaire en 01 est non-approximable à mieux que 0.

[HR97] R. Hassin, S. Rubinstein},
An Approximation Algorithm for Maximum Packing of 3-Edge Paths
Information Processing Letters, 1997, 63: 63-67

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

[MPT032] J. Monnot, V. Th. Paschos, S. Toulouse,
Differential approximation results for traveling salesman problem with distances 1 and 2,
European Journal of Operational Research, 145 (2003) 557-568

[MT05] J. Monnot, S. Toulouse,
Approximation results for the weighted P4-partition problem
Rapport LIPN 2005-01 - soumis

[PY93] C. Papadimitriou, M. Yannakakis,
The traveling salesman problem with distances one and two
Mathematics of Operations Research, 1993, 18(1): 1-11