Rozkład relacji binarnej na pojemniki w taki sposób, że każdy element znajduje się w niewielkiej liczbie pojemników

10

Dostajemy pary obiektów (powiedzmy liczby). Każdy obiekt pojawia się w co najwyżej q parach. Naszym celem jest rozdzielenie par na pojemniki o równej wielkości, tak aby każdy obiekt występował w jak najmniejszej liczbie różnych pojemników.

Dokładniej, interesuje nas funkcja f z właściwością, że dla każdej relacji binarnej z parami m co najwyżej q par na obiekt istnieje rozkład par na p przedziały, tak że każdy przedział odbiera pary m/p ( p powinien dzielić m ) i żaden obiekt nie występuje w więcej niż f(m,q,p) przedziałach.

To pytanie pojawiło się w naszych badaniach dotyczących równoległej oceny zapytań. Można się spodziewać, że m jest duże w porównaniu do p . „Właściwy” rozmiar q jest mniej wyraźny. Interesującym rozmiarem q może być np. mp . Przydałaby się również funkcja, która nie zależy odq, ale działa tylko dla określonego zakresuq(ale nieq=O(1)).

W rzeczywistości jesteśmy po granicach formy p1ϵ , przy czym ϵ>0 tak duże, jak to możliwe ...

Thomas S.
źródło
3
W terminologii graficznej: mając liczbę całkowitą i wykres G = ( V , E ) o m krawędziach, przy czym każdy wierzchołek ma stopień co najwyżej q , znajdź p podrozdziały G 1 , G 2 , , G p gdzie G i = ( V i , E i ) , takie, że V = i V i oraz { E i } ipG=(V,E)mqpG1,G2,,GpGi=(Vi,Ei)V=iVi{Ei}iEpm/pvVkk k m p q(maxv|{i:vVi}|k)kkmpq
Zgadza się. Pod względem wykresów. Odpowiedź na pytanie brzmi: . Rzeczywiście, jak napisano powyżej, jesteśmy zainteresowani granicami formy i nie mamy takich ograniczeń dla . p 1 - ϵ ϵ > 0pp1ϵϵ>0
Thomas S
Specjalny przypadek na początek: niech będzie nieparzystą liczbą całkowitą. Czy można podzielić krawędzie pełnego wykresu na podzbiorów wielkości tak, że dla każdego wierzchołka liczba podzbiorów zawierających krawędzie padające na ten wierzchołek wynosi , dla niektórych ? Założę się, że tak dla każdego --- weź losowe podzbiory wierzchołków o rozmiarze każdy. Następnie z dużym prawdopodobieństwem każdy wierzchołek znajduje się w około podzbiorów wierzchołków, a każda para jest w przybliżeniun1(n2)Knn(n1)/2O(n1ϵ)ϵ>0ϵ<1/2nn1ϵn1ϵ(i,j)n12ϵ podzbiorów. Teraz przypisz pary do podzbiorów ...
Neal Young,
W takim przypadku węzły można najpierw rozdzielić na zestawy wielkości (pomyśl o odstępach). Następnie każdy bin otrzymuje iloczyn dwóch takich zestawów (rozważam pełny ukierunkowany wykres, który łatwiej jest określić i asymptotycznie niewiele różni się). Dlatego każdy wierzchołek występuje w przedziałach, czyli w tym przypadku. nnI×Jnϵ=12
Thomas S
W przypadku wykresu gwiazdowego ( krawędzie padające na jeden wierzchołek ) wierzchołek musi znajdować się w każdym podgrrafie , więc w takim przypadku ograniczenie mniejsze niż nie jest możliwe. Chyba dlatego ograniczasz maksymalny stopień ? Być może mógłbyś powiedzieć coś bardziej definitywnego na ten temat, ponieważ wydaje się to kluczowe założenie. Tymczasem zostawiłem obserwację (nie odpowiedź, ale zbyt dużą, by zmieściła się w komentarzu!) Jako odpowiedź poniżej. n1rrppq
Neal Young,

Odpowiedzi:

1

To nie jest odpowiedź. To tylko dość trywialna obserwacja, że ​​WLOG można złagodzić wymóg, aby istniały dokładnie podzestawy krawędzi dokładnie tego samego rozmiaru, i zamiast tego po prostu szukać dowolnej liczby podzbiorów krawędzi o rozmiarze . Może to pomaga pomyśleć o problemie.p{Ei}iO(the desired size)

Napraw dowolny wykres i liczbę całkowitą . NiechG=(V,E)p1s=|E|/p

Lemat. Załóżmy, że istnieją podgrupy takie, że dzieli na (dowolną liczbę) części o rozmiarze . Niech być maksymalną liczbą części, w których znajduje się dowolny wierzchołek.{Gj=(Vj,Ej)}j{Ej}jEO(s)

M=maxvV|{j:vVj}|

Następnie są subgraphs tak, że dzieli na dokładnie częściach o wielkości co najwyżej i p{Gi=(Vi,Ei)}i{Ei}iEps=|E|/p

maxvV|{i:vVi}|=O(M).

Dowód. Zaczynając od sekwencji , zamień każdą część w sekwencji na dowolną uporządkowaną sekwencję krawędzi zawartych w tej części. Niech będą sekwencją wynikową (permutacja taka, że ​​każda część jest pewnym „przedziałem” krawędzi w sekwencja). Teraz podziel tę sekwencję na ciągłych tak aby każdy oprócz ostatniego miał rozmiar , i niech zawierać krawędzie w ciągłym podciągu. (WięcE1,E2,,EpEje1,e2,,emEEj{ea,ea+1,,eb}psEiiEi={eis+1,eis+1,,e(i+1)s} dla .)i<p

Z założenia każda część ma rozmiar , a zgodnie z projektem każda część z wyjątkiem ostatniej części ma rozmiar , więc (ze względu na sposób zdefiniowania ) krawędzie w dowolnej części są podzielone na części w . To i założenie, że każdy wierzchołek występuje w co najwyżej części w , oznacza, że ​​każdy wierzchołek występuje w co najwyżej części w . CO BYŁO DO OKAZANIAEjO(s)EjEps{Ei}iEjO(1){Ei}iM{Ej}jO(M){Ei}i

Neal Young
źródło