Correspondance en ligne sur des hypergraphes à 3-uniformes

Le problème de correspondance en ligne a été introduit par Karp, Vazirani et Vazirani (STOC 1990) sur des graphes bipartis avec des arrivées de sommets. Il est bien connu que le ratio compétitif optimal est 1-1/e pour les versions intégrales et fractionnaires du problème. Depuis, des efforts considérables ont été déployés pour trouver des ratios compétitifs optimaux pour d'autres contextes connexes. Dans ce travail, nous allons au-delà du cas graphique et étudions le problème de correspondance en ligne sur des hypergraphes k-uniformes. Pour k=3, nous proposons un algorithme fractionnaire primal-dual optimal, qui atteint un ratio compétitif de (e-1) / (e+1) 0.4621. En tant que notre principale contribution technique, nous présentons une instance adversariale soigneusement construite, qui montre que ce ratio est en fait optimal. Cela combine des idées issues d'instances dures connues pour des graphes bipartis sous les modèles d'arrivée d'arêtes et d'arrivée de sommets. Pour k ≥ 3, nous donnons un algorithme intégral simple qui fonctionne mieux que glouton lorsque les nœuds en ligne ont un degré borné. Comme corollaire, il atteint le ratio compétitif optimal de 1/2 sur des hypergraphes à 3-uniformes lorsque chaque nœud en ligne a un degré d'au plus 2. Cela est dû au fait que le cas particulier où chaque nœud en ligne a un degré 1 est équivalent au modèle d'arrivée d'arêtes sur des graphes, pour lequel une borne supérieure de 1/2 est connue.