Несоответствие перестановок

Несоответствие перестановок — это раздел теории несоответствия , который занимается балансирующими интервалами, вызванными перестановками элементов. Имеется набор из n элементов, и в этом наборе есть m различных перестановок. Общий вопрос исследования: можем ли мы раскрасить каждый элемент в один из двух разных цветов (например, черный и белый), чтобы в каждой перестановке каждый интервал содержал примерно одинаковое количество элементов каждого цвета?

Формально невязка интервала определяется как разница между количеством белых элементов и количеством черных элементов в этом интервале; цель состоит в том, чтобы раскрасить элементы так, чтобы максимальное расхождение интервала в каждой из перестановок было как можно меньшим.

Определения

Пусть p ₁ , ..., pm _— перестановки [ n ] . Набор интервалов перестановки — это набор всех подмножеств [ n ], смежных друг с другом в перестановке. Например, если n = 4 и одна из перестановок равна (1,2,3,4), то ее набор интервалов содержит, например, ребра (1,2), (1,2,3), (2,3 ), (2,3,4) и т. д.

Расхождение перестановок p ₁ , ..., pm _чисел есть минимальная по всем черно-белым раскраскам целых чисел из [ n ] максимальная по всем интервалам разность между количеством белых и черных целых в интервале. ^{[ 1 ]}

Оффлайн раскраски

Когда есть только одна перестановка, возможно расхождение в 1, если просто раскрасить целые числа поочередно в белый, черный, белый, черный и т. д.
При наличии двух перестановок возможно расхождение в 2; это было доказано Спенсером в 1987 году. ^{[ 1 ]}

Для любых m перестановок расхождение не превышает $8m\log {n}$ , и такая раскраска может быть эффективно вычислена. ^{[ 2 ]}
предположил, что для любых трех перестановок Бек расхождение постоянно. Однако эта гипотеза была опровергнута: для любого n , являющегося степенью 3, существуют 3 перестановки, невязка которых равна $\lceil (\log _{3}{n})/3+1\rceil$ . Точнее, для любой раскраски {1,-1}, если сумма всех цветов равна d , то существует некоторое целое число q такое, что во всех трех перестановках сумма первых q цветов не превосходит $(-\log _{3}{n}+2d-2)/3$ . ^{[ 3 ]}^{: Кор.2} Это имеет последствия для проблемы упаковки контейнеров .

Цзян, Кулкарни и Сингла ^{[ 1 ]} изучите онлайн-режим со стохастическим прибытием точки и докажите, что:

Случайная раскраска дает ожидаемое расхождение ${\tilde {O}}({\sqrt {n}})$ .
Существует эффективный алгоритм, гарантирующий $O(n^{c/\log {\log {n}}})$ несоответствие для некоторой универсальной постоянной c с высокой вероятностью . Они показывают применение этого результата к онлайн-ярмаркам .

Онлайн раскраски

Иногда элементы не доступны заранее, а поступают один за другим, и каждый элемент должен быть раскрашен сразу по прибытии. Эта онлайн-постановка сложна даже для одной перестановки. Цзян, Кулкарни и Сингла называют эту ситуацию одной перестановкой: Несоответствие интервалов онлайн. Они доказывают это: ^{[ 1 ]}^{: Раздел 3.2}

Ни один онлайн-алгоритм не может гарантировать постоянное расхождение.
Случайная раскраска дает ${\tilde {O}}({\sqrt {n}})$ ожидаемое несоответствие.
Если прибытие является состязательным, несоответствие любого онлайн-алгоритма $\Omega ({\sqrt {n}})$ .
Если прибытие стохастическое, существует эффективный алгоритм, гарантирующий $O(n^{c/\log {\log {n}}})$ несоответствие для некоторой универсальной константы c с высокой вероятностью (т. е. с вероятностью 1-1/poly( n ), где показатель степени многочлена зависит от c ).

Доказательство распространяется на случай двух перестановок, которые они называют онлайн-расхождением полос.

Приложения

Результаты по несоответствию перестановок были использованы при вычислении Согласованных подмножеств , а также в разделе Онлайн-ярмарки . ^{[ 1 ]}

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Цзян, Хаотянь; Кулкарни, Джанардхан; Сингла, Сахил (2019-10-02), Онлайн-геометрическое несоответствие для стохастических поступлений с применением минимизации зависти , doi : 10.48550/arXiv.1910.01073 , получено 21 июля 2024 г.
^ Бохус, Геза (1990). «О несовпадении 3-х перестановок» . Случайные структуры и алгоритмы . 1 (2): 215–220. дои : 10.1002/rsa.3240010208 . ISSN 1098-2418 .
^ Ньюман, А.; Нейман, О.; Николов, А. (01 октября 2012 г.). «Гипотеза Бека о трёх перестановках: контрпример и некоторые последствия» . 2012 53-й ежегодный симпозиум IEEE по основам информатики . стр. 253–262. дои : 10.1109/FOCS.2012.84 . ISBN 978-0-7695-4874-6 . S2CID 14442594 .

[:22-1] Jump up to: ^а ^б ^с ^д ^и Цзян, Хаотянь; Кулкарни, Джанардхан; Сингла, Сахил (2019-10-02), Онлайн-геометрическое несоответствие для стохастических поступлений с применением минимизации зависти , doi : 10.48550/arXiv.1910.01073 , получено 21 июля 2024 г.

[2] Бохус, Геза (1990). «О несовпадении 3-х перестановок» . Случайные структуры и алгоритмы . 1 (2): 215–220. дои : 10.1002/rsa.3240010208 . ISSN 1098-2418 .

[3] Ньюман, А.; Нейман, О.; Николов, А. (01 октября 2012 г.). «Гипотеза Бека о трёх перестановках: контрпример и некоторые последствия» . 2012 53-й ежегодный симпозиум IEEE по основам информатики . стр. 253–262. дои : 10.1109/FOCS.2012.84 . ISBN 978-0-7695-4874-6 . S2CID 14442594 .

[ 1 ]

[ 2 ]

[ 3 ]