Couverture de Set parallèle et appariement d'hypergraphes via un échantillonnage aléatoire uniforme

Le problème de SetCover a été largement étudié dans de nombreux modèles de calcul différents, y compris les environnements parallèles et distribués. D'un point de vue d'approximation, il existe deux garanties standard : une approximation O () (où est la taille maximale du set) et une approximation O (f) (où f est le nombre maximum de sets contenant un élément donné). Dans cet article, nous introduisons une nouvelle approche indépendante du modèle, étonnamment simple, pour résoudre SetCover dans des graphes non pondérés. Nous obtenons plusieurs algorithmes améliorés dans les modèles MPC et CRCW PRAM. Tout d'abord, dans le modèle MPC avec un espace sublinéaire par machine, nos algorithmes peuvent calculer une approximation O (f) pour SetCover en O (+ f) tours, où nous utilisons la notation O (x) pour supprimer les termes poly x et poly n, et une approximation O () en O (^3/2 n) tours. De plus, dans le modèle PRAM, nous donnons un algorithme approximatif O (f) utilisant un travail linéaire et une profondeur O (n). Tous ces bornes améliorent les bornes de complexité en tours/profondeur existantes d'un facteur ^ (1) n. De plus, notre approche mène à de nombreux autres nouveaux algorithmes, y compris des algorithmes améliorés pour le problème HypergraphMatching dans le modèle MPC, ainsi que des algorithmes SetCover plus simples qui correspondent aux bornes existantes.