Discussion:Inégalité de réarrangement

à faire

• Démonstrations instructives à reprendre de la page allemande : par contradiction, ou bien en réduisant petit à petit le nombre d'inversions de σ ce qui ne fait qu'augmenter la fonctionnelle de σ qui apparaît dans le terme de droite. Ce qui permet de discuter le fait que ${\mathfrak {S}}_{n}\$ est engendré par les transpositions.
• Donner des applications, par exemple :
  • pour la résolution de problèmes élémentaires d'ordonnancement : un énoncé typique serait : minimiser le temps total d'attente des individus $\scriptstyle \ i\in [\![1,n]\!],\$ dans une file d'attente, sachant que le temps nécessaire pour traiter l'individu i est $\scriptstyle \ x_{i},\$ et sachant que $\scriptstyle \ x_{1}\leq x_{2}\leq \dots \leq x_{n}.\$ On applique alors l'"inégalité de réarrangement" avec $\scriptstyle \ y_{i}=n+1-i,\$ $\scriptstyle \ \sigma (i)\$ désignant le rang de l'individu i dans la file. Comme on minimise au lieu de maximiser, et comme la suite $\scriptstyle \ y_{i}=n+1-i,\$ est décroissante plutôt que croissante, la solution optimale est encore σ=Id, si je me rappelle bien : dans la queue au supermarché, il faut donc faire passer d'abord ceux qui ont le caddy le moins plein ... Cela doit s'appeler un problème de flow-shop ??? sous réserve ??? (appel à l'aide aux spécialistes de recherche opérationnelle ...)
  • en particulier pour l'optimisation d'algorithmes basiques de rangement.

Chassaing 5 août 2009 à 21:48 (CEST)

FAIT Chassaing 3 septembre 2009 à 00:49 (CEST)

Monge

• typiquement, le fait que les réarrangées croissantes réalisent la distance de Wasserstein L2 est une conséquence d'une version continue de l'inégalité de réarrangement. Regarder ce qu'on peut trouver comme page sur le Problème de Monge-Kantorovich, Monge etc ... Chassaing 7 août 2009 à 09:07 (CEST)

FAIT Chassaing 3 septembre 2009 à 00:51 (CEST)

Inégalité de Vince

Parler de l'Inégalité de Vince qui est la généralisation la plus immédiate de l'inégalité de réarrangement (voir le bouquin de Steele cité à la fin de l'article). Chassaing 16 août 2009 à 00:06 (CEST)