Home

Семинар 20 июня 2003 года

Пятница, 20 июня, комната 106. Начало в 16:00.

Докладчик: В. Н. Баргачёв (СПбГУ).

Тема: Эффективная конструкция множества перестановок, независимых по 4 относительно минимума.

Abstract

Семейства перестановок обладающие свойством независимости относительно минимума были введены в [1]. Такие семейства оказались полезны для нахождения "почти одинаковых" документов в поисковых системах типа Altavista. Независимые относительно минимума семейства перестановок находят и другие приложения, например при дерандомизации алгоритмов для некоторых NP-полных задач.

Семейство перестановок $ F $ множества $ \{1,\ldots,n\} $ называется независимым по $ k $ относительно минимума, если для любого непустого подмножества $ X $ множества $ \{1,\ldots,n\} $ размера не более $ k $ и любого элемента $ x $ множества $ X $, выполняется

$ |{ ?\in F: ? (x) = \min ? (X) }| = |F| / |X| $.

Первые нетривиальные нижние оценки на размер независимого по k семейства перестановок появились в [2], [3]. В [2] доказывается существование независимого по k относительно минимума множества перестановок размера $ O(n^k) $. В [4] при $ k=4 $ эта оценка улучшается до $ O(n^3) $. В данном докладе мы улучшаем эту оценку:

ТЕОРЕМА. Пусть $ n=2^(2^m) $, $ m>0 $. Тогда существует независимое по 4 семейство перестановок множества $ \{1,\ldots,n\} $ размера $ n(n-1) $.

Нужно отметить, что случаи малых k действительно интересны, так как используются для дерандомизации алгоритмов для задачи k-КНФ, а 3-КНФ является классической NP-полной задачей.

Литература

1. Broder A. Z., Charikar M., Frieze A. M., Mitzenmacher M. "Min-wise independent permutations" // J. Comput. System Sci., 2000, V. 60, P. 630-659.

2. Itoh T., Takei Y., Tarui J. "On permutations with limited independence" // Proc. of SODA'2000, 2000, P. 137-146.

3. Норин С. "Полиномиальная нижняя оценка на размер независимого по k относительно минимума семейства перестановок" // Зап. Научн. Сем. ПОМИ, 2001, Т. 277, С. 104-116.

4. Vsemirnov M. "Automorphisms of projective spaces and min-wise independent sets of permutations" // Quaderni del Seminario Mathematico di Brescia, 2002, N53, P. 1-16.