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

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. $\sqrt{\frac{m}{p}}$ . Przydałaby się również funkcja, która nie zależy od $q$ , ale działa tylko dla określonego zakresu $q$ (ale nie $q=O(1)$ ).

W rzeczywistości jesteśmy po granicach formy $p^{1-\epsilon}$ , przy czym $\epsilon>0$ tak duże, jak to możliwe ...

combinatorics

— Thomas S.
źródło

W terminologii graficznej: mając liczbę całkowitą

i wykres

krawędziach, przy czym każdy wierzchołek ma stopień co najwyżej

, znajdź

podrozdziały

gdzie

, takie, że

oraz

p

$p$

G = (V, E)

$G=(V,E)$

m

$m$

q

$q$

p

$p$

G_{1}, G_{2}, \dots, G_{p}

$G_1, G_2, \ldots, G_p$

G_{i} = (V_{i}, E_{i})

$G_i=(V_i, E_i)$

V = ⋃_{i} V_{i}

$V=\bigcup_i V_i$

{E_{i}}_{i}

$\{E_i\}_i$

E

$E$

p

$p$

m / p

$m/p$

v \in V

$v\in V$

k

$k$

(max_{v} | {i : v \in V_{i}} | \leq k)

$(\max_v |\{i : v\in V_i\}| \le k)$

k

$k$

k

$k$

m

$m$

p

$p$

q

$q$

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

$p$

p^{1 - ϵ}

$p^{1-\epsilon}$

ϵ > 0

$\epsilon>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żeniu

n \geq 1

$n \ge 1$

(\binom{n}{2})

$n\choose 2$

K_{n}

$K_n$

n

$n$

(n - 1) / 2

$(n-1)/2$

O (n^{1 - ϵ})

$O(n^{1-\epsilon})$

ϵ > 0

$\epsilon>0$

ϵ < 1 / 2

$\epsilon<1/2$

n

$n$

n^{1 - ϵ}

$n^{1-\epsilon}$

n^{1 - ϵ}

$n^{1-\epsilon}$

(i, j)

$(i,j)$

n^{1 - 2 ϵ}

$n^{1-2\epsilon}$ 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.

\sqrt{n}

$\sqrt{n}$

\sqrt{n}

$\sqrt{n}$

I \times J

$I\times J$

\sqrt{n}

$\sqrt{n}$

ϵ = \frac{1}{2}

$\epsilon=\frac{1}{2}$

— 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.

n - 1

$n-1$

r

$r$

r

$r$

p

$p$

p

$p$

q

$q$

— Neal Young,

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$ $\{E_i\}_i$ $O(\textsf{the desired size})$

Napraw dowolny wykres i liczbę całkowitą . Niech $G=(V,E)$ $p\ge 1$ $s=\lceil |E|/p\rceil$

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. $\{G'_j=(V'_j,E'_j)\}_j$ $\{E'_j\}_j$ $E$ $O(s)$

M = max_{v \in V} | {j : v \in V_{j}^{'}} |

$M = \max_{v\in V} |\{j : v\in V'_j\}|$

Następnie są subgraphs tak, że dzieli na dokładnie częściach o wielkości co najwyżej i $p$ $\{G_i=(V_i,E_i)\}_i$ $\{E_i\}_i$ $E$ $p$ $s=\lceil |E|/p\rceil$

max_{v \in V} | {i : v \in V_{i}} | = O (M) .

$\max_{v\in V} |\{i : v\in V_i\}| = 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ęc $E'_1, E'_2, \ldots, E'_{p'}$ $E'_j$ $e_1, e_2, \ldots, e_m$ $E$ $E'_j$ $\{e_a, e_{a+1}, \ldots, e_b\}$ $p$ $s$ $E_i$ $i$ $E_i = \{e_{i\,s+1}, e_{i\,s+1}, \ldots, 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 OKAZANIA $E'_j$ $O(s)$ $E_j$ $E_p$ $s$ $\{E_i\}_i$ $E'_j$ $O(1)$ $\{E_i\}_i$ $M$ $\{E'_j\}_j$ $O(M)$ $\{E_i\}_i$

— Neal Young
źródło