Максимальное пересечение кардинальности каждой пары множеств равных размеров

Question

У нас есть N наборов, каждый из которых имеет N целых чисел.

Мы берем каждую пару множеств и находим их множество пересечений S.

Теперь нам интересно найти мощность множества пересечений S, имеющего максимальную мощность.

---

пример

Например, пусть N будет 4, и у нас будет 4 набора каждый из 4 элементов:

A = {1,2,5,6}, B = {2,5,7,6}, C = {3,4,2,6}, D = {1,4,7,8}

Теперь возьмем попарно пересечение этих множеств и множество пересечений, имеющее максимальную мощность = {2,5,6}

Итак, мы возвращаемся 3.

---

Решение о грубой силе может быть выполнено за время Θ (N³). Можем ли мы сделать это более эффективно с помощью другого метода?

Answer 1

Следующее может сократить время работы, если:

1. Существует некоторое α > 0 такое, что (для фиксированного α и увеличения n) существует два множества с по меньшей мере α- долей перекрытия.

2. Многие пары не пересекаются или почти не пересекаются (уточняется позже).

3. Вы готовы использовать алгоритм Монте-Карло с высокой вероятностью (вероятность ошибки уменьшается с n).

Предположим, вы сначала преобразовали каждый набор в хеш-таблицу. Это займет (ожидается) Θ (n ²) время. Теперь для каждой пары наборов (т. Е. Петли n ²) выберите √n случайных элементов из первого набора и посчитайте количество совпадений во втором наборе (ожидаемое время O(√ n)).

Комбинируя мультипликативную границу Черноффа и границу объединения, вы можете сохранить только пары, для которых число попаданий было не менее 1/2 α √ n.

Таким образом, с высокой вероятностью вы можете сузить n ² пар до некоторого β n ² пар со временем только O (n ^2,5). С этого момента продолжайте с грубой силой. Это либо полезно, либо не зависит от того, как β растет как функция от n.