Распределение бинарного отношения по бинам так, что каждый элемент находится в небольшом количестве бинов

10

Нам даны пары объектов (скажем, числа). Каждый объект появляется не более чем в парах. Наша цель состоит в том, чтобы распределить пары в ячейки одинакового размера так, чтобы каждый объект находился в как можно меньшем количестве разных корзин.q

Точнее, нас интересует функция обладающая тем свойством, что для каждого бинарного отношения с парами, имеющими не более пар на объект, существует распределение пар по бинам, так что каждый бин получает пар ( должен делить ), и ни один объект не встречается в более чем ячейках.fmqpm/ppmf(m,q,p)

Этот вопрос возник в нашем исследовании параллельной оценки запросов. Можно было бы ожидать, что больше по сравнению с . «Правильный» размер менее ясен. Интересный размер для может быть, например, . Функция, которая не зависит от , но работает только для определенного диапазона , также будет полезна (но не ).mpqqmpqqq=O(1)

На самом деле, мы за границами вида , с как можно больше ...p1ϵϵ>0

Томас С
источник
3
В терминологии графа: задано целое число и граф с ребрами, причем каждая вершина имеет степень не более , найти подграфов где так, что и является разбиением на частей, каждая из которых имеет размер , и каждая вершина встречается не более чем в графов . Ваша цель - минимизировать . Какова лучшая верхняя границаpG=(V,E)mqpG1,G2,,GpGi=(Vi,Ei)V=iVi{Ei}iEpm/pvVk(maxv|{i:vVi}|k)kk вы можете показать данные , и ? mpq
Нил Янг
Вот так. С точки зрения графиков. Ответ на вопрос: . Действительно, как написано выше, нас интересуют границы вида и у нас нет такой границы для . pp1ϵϵ>0
Томас С
Особый случай для начала: пусть будет нечетным целым числом. Можно ли разделить ребра полного графа на подмножеств размера , чтобы для каждой вершины число подмножеств, содержащих ребра, инцидентные этой вершине, было , для какого-нибудь ? Бьюсь об заклад, для любого --- беру случайных подмножеств вершин размером каждое. Тогда с высокой вероятностью каждая вершина находится примерно в подмножеств вершин, и каждая пара находится в приблизительноn1(n2)Knn(n1)/2O(n1ϵ)ϵ>0ϵ<1/2nn1ϵn1ϵ(i,j)n12ϵ из подмножеств. Теперь назначьте пары для подмножеств ...
Нил Янг
В этом случае узлы могут быть распределены в первой множество размера (думает интервалы). Затем каждый бин получает произведение двух таких наборов (я рассматриваю полный ориентированный граф, который проще сформулировать и асимптотически не сильно отличается). Следовательно, каждая вершина находится в бинах, то есть в этом случае . nnI×Jnϵ=12
Томас С
Для графа звезд ( ребер, падающих на одну вершину ) вершина должна быть в каждом из подграфов, поэтому в этом случае оценка меньше невозможна. Я думаю, поэтому вы ограничиваете максимальную степень ? Может быть, вы могли бы сказать что-то более определенное об этом, так как это кажется важным предположением. Тем временем я оставил замечание (не ответ, но слишком большой, чтобы его можно было использовать в качестве комментария!) В качестве ответа ниже. n1rrppq
Нил Янг

Ответы:

1

Это не ответ. Это просто несколько тривиальное наблюдение, что WLOG позволяет ослабить требование, чтобы было ровно реберных подмножеств точно такого же размера, и вместо этого просто искать любое количество реберных подмножеств размера . Может быть, это помогает думать о проблеме.p{Ei}iO(the desired size)

Зафиксируем любой граф и целое число . ПустьG=(V,E)p1s=|E|/p

Лемма. Предположим, что есть подграфы такие, что разбивает на (любое количество) частей размера . Пусть быть максимальным количеством частей, в которых находится любая вершина.{Gj=(Vj,Ej)}j{Ej}jEO(s)

M=maxvV|{j:vVj}|

Тогда есть подграфов таких что разбивает ровно на частей, каждая из которых имеет размер не более , и p{Gi=(Vi,Ei)}i{Ei}iEps=|E|/p

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

Доказательство. Начиная с последовательности , замените каждую часть в последовательности любой упорядоченной последовательностью ребер, содержащихся в этой части. Пусть будет результирующей последовательностью (перестановка такая, что каждая часть является некоторым «интервалом» ребер в последовательность). Теперь разбейте эту последовательность на смежных подпоследовательностей так, чтобы каждая, кроме последней, имела размер , и пусть содержит ребра в й смежной подпоследовательности. (ТакE1,E2,,EpEje1,e2,,emEEj{ea,ea+1,,eb}psEiiEi={eis+1,eis+1,,e(i+1)s} для .)i<p

По предположению, каждая часть имеет размер , а по конструкции каждая часть кроме последней части имеет размер , поэтому (из-за способа определения ) ребра в любой данной части разбиты на частей в . Это и предположение, что каждая вершина встречается в не более чем частях в , подразумевает, что каждая вершина встречается в не более чем частей в . QEDEjO(s)EjEps{Ei}iEjO(1){Ei}iM{Ej}jO(M){Ei}i

Нил Янг
источник