La norme $L_\infty$, pour décriée qu'elle soit quant à sa faiblesse eu égard à la robustesse, présente parfois l'avantage d'offrir une solution facile à calculer, alors que parallèlement la norme $L_p$ ($p$ fini) conduit à des problèmes algorithmiques plus complexes, voire NP-difficiles. L'approximation d'une dissimilarité par une ultramétrique, ou par une distance de type arboré préservant les distances à un point donné, ou l'approximation d'une régression, relative à un ordre partiel, par une régression isotone relèvent de ce cas de figure. Nous présentons les exemples sus-évoqués dans un cadre très général, où il s'agit d'approcher un vecteur x d'un espace vectoriel E de dimension finie, par un élément d'un sous-ensemble K, au sens de la norme $L_\infty$ (relativement à une base de E). Nous montrons qu'une solution simple existe à ce problème, pour peu que K soit tel que x possède un élément sous-dominant dans K, i e. un vecteur x* maximum dans l'ensemble des vecteurs de K inférieurs à x, et que K soit invariant par translation le long de la diagonale principale. Les dissimilarités de Robinson relèvent également de cette problématique, pour un ordre fixé. En revanche, lorsque l'ordre est inconnu, il est montré que l'approximation en norme $L_\infty$ demeure NP-difficile. Nous terminons par l'approximation ultramétrique d'une dissimilarité d sous le double critère, d'être supérieure minimale à d et de minimiser sa distance en norme $L_\infty$ à d.