Обложка для матриц перестановок

16

Учитывая набор S из nxn матриц перестановок (который является лишь малой долей из n! Возможных матриц перестановок), как мы можем найти подмножества T минимального размера в S, чтобы при добавлении матриц T было по крайней мере 1 в каждой позиции?

Меня интересует эта проблема, где S - небольшая подгруппа в S_n. Я задаюсь вопросом, можно ли найти (и реализовать!) Алгоритмы аппроксимации, которые намного быстрее, чем алгоритмы жадных алгоритмов (запускаются много раз, пока не получится «повезло», что является очень медленной процедурой, но, тем не менее, дает почти оптимальные границы в небольших случаях), или гарантирует ли неприемлемость, что я не могу.

Несколько простых фактов об этой проблеме: циклическая группа матриц перестановок длины n решает эту проблему, разумеется, оптимально. (Требуется по крайней мере n матриц, потому что каждая матрица перестановок имеет n единиц, а нужно n ^ 2.)

Множества S, которые меня интересуют, не содержат в себе n-циклическую группу.

Эта проблема представляет собой особый случай установки крышки. Действительно, если мы допустим, чтобы X было множеством (1,2, ... n) * (1,2, ... n) с n ^ 2 элементами, то каждая матрица перестановок соответствует подмножеству размера n, и I ищу наименьшую подгруппу из этих подмножеств, которые охватывают X. Сам набор покрытий не является хорошим способом взглянуть на эту проблему, потому что аппроксимация общей задачи покрытия набора.

Единственная причина, почему эта проблема не слишком медленная при использовании жадного подхода, состоит в том, что симметрия в группе перестановок помогает устранить большую избыточность. В частности, если S является подгруппой, а T является небольшим подмножеством, которое является минимальным покрывающим множеством, то множества sT (умножьте T на любой элемент группы s) все еще находятся в S и все еще являются покрывающим множеством (конечно, того же размера, но все же минимальный.) Если вам интересно, успешное дело имеет n ~ 30 и | S | ~ 1000, а счастливые жадные результаты имеют | T | ~ 37. Случаи с n ~ 50 имеют очень плохие границы, получение которых занимает очень много времени.

Подводя итог, мне интересно, есть ли приближенные подходы к этой задаче или она все еще достаточно общая, чтобы вписаться в некоторую теорему неприемлемости, как это имеет место для общей задачи о покрытии множеств. Какие алгоритмы используются для приближения связанных проблем на практике? Кажется, что может быть что-то возможное, так как все подмножества имеют одинаковый размер, и каждый элемент появляется с одинаковой небольшой частотой 1 / n.

-B

Брайден Уэйр
источник
Вы действительно хотите добавить? Я предполагаю, что вы имеете в виду своего рода «союз», или действительно ORing? потому что в противном случае вы можете получить 2 в записи.
Суреш Венкат
Объединение работает нормально. Если я добавлю, то мне нужно получить по крайней мере 1 в каждой записи. Причина, по которой я представляю это как сложение, заключается в том, что на самом деле я математик, и все еще есть математическое значение в добавлении элементов группы (что не зависит от того, какую группу представляют в виде матриц перестановок), а не в «объединении» матриц.
Brayden Ware
Но нет никакого полезного способа сформулировать это условие без матриц перестановок, так что не стесняйтесь думать об объединении. 2s (и не дай бог 3s и более) будут служить только маркерами того, что мы не находимся в решении сновидения, состоящего из ровно n матриц, добавляющих к матрице all 1s, количества 2s и выше, измеряющих, сколько дополнительных матриц мы использовали. (Каждая дополнительная матрица добавляет n к общей сумме в конце.)
Brayden Ware

Ответы:

10

Вот почти плотный анализ ПРИБЛИЖАЕМОСТИ для случая , когда S является не требуется , чтобы быть подгруппой симметрической группы.

Эта проблема является частным случаем Set Cover, и существует простой жадный алгоритм приближения [Joh74]. Если мы обозначим к й гармоники как H k = ∑ i = 1 k 1 / i , жадный алгоритм достигает отношения аппроксимации H n = ln n + Θ (1). (Существует алгоритм [DF97], который приводит к несколько лучшему коэффициенту аппроксимации H n −1/2.) ( Правка : в редакции 2 и более ранних версиях коэффициент аппроксимации жадного алгоритма был хуже, чем правильное значение.)

Более того, это почти оптимально в следующем смысле:

Теорема . Заданное покрытие для матриц перестановок не может быть аппроксимировано в пределах отношения аппроксимации (1− ε ) ln n для любой постоянной 0 < ε <1, если только NP ⊆ DTIME ( n O (log log n ) ).

Вот набросок доказательства. Мы пишем [ n ] = {1,…, n }. Мы построим сокращение от Set Cover:

Установить
экземпляр обложки : положительное целое число m и набор подмножеств C из [ m ].
Решение : Подмножество D в C такое, что объединение множеств в D равно [ m ].
Цель : минимизировать | D |

Это известный результат Фейге [Fei98], что Set Cover не может быть аппроксимирован в пределах отношения аппроксимации (1 - ε ) ln m для любой постоянной 0 < ε <1, если NP ⊆ DTIME ( n O (log log n ) ).

Пусть ( m , C ) будет экземпляром Set Cover. Мы построим экземпляр ( n , S ) множества покрытий для матриц перестановок.

(0110)(1001)in (где индекс i +2 интерпретируется как модуль n ). Для 0≤ jm определите S j = { P E Q j : EC ∪ {{ m +1}}} и S = S 0 ∪… ∪ S m .

Претензии . Пусть к быть размером с минимальным покрытием [ м ] в C . Тогда размер минимального покрытия в S равен ( k +1) ( m +1).

Эскиз доказательства . Если DC является покрытием из [ m ], мы можем построить покрытие TS размера (| D | +1) ( m +1) с помощью T = { P E Q j : ES ∪ {{ m +1}}, 0≤ jm }.

С другой стороны, пусть TS - покрытие. Обратите внимание, что все матрицы в S 0 являются блочными диагональю с блоками размера 2 × 2, а другие матрицы в S имеют 0 в этих блоках. Следовательно, TS 0 охватывает эти блоки. Кроме того, TS 0 содержит P { m +1}, поскольку в противном случае (2 m +1, 2 m +2) -вход не был бы охвачен. Заметим, что ( TS 0 ) ∖ { P { m +1}} Соответствует набору покрова вC . Следовательно, | TS 0 | ≥ k +1. Аналогично, для любого 0≤ jm , | TS j | ≥ k +1. Следовательно, | T | ≥ ( k +1) ( m +1). Конец контрольного эскиза претензии .

По утверждению, приведенная выше редукция сохраняет коэффициент аппроксимации. В частности, устанавливается теорема.

Ссылки

[DF97] Ронг-Чий Дух и Мартин Фюрер. Аппроксимация покрытия k- множества полулокальной оптимизацией. В материалах двадцать девятого ежегодного симпозиума ACM по теории вычислений (STOC) , с. 256–264, май 1997 г. http://dx.doi.org/10.1145/258533.258599

[Fei98] Уриэль Фейдж. Порог ln n для аппроксимации заданного покрытия. Журнал ACM , 45 (4): 634–652, июль 1998 г. http://dx.doi.org/10.1145/285055.285059

[Joh74] Дэвид С. Джонсон. Аппроксимационные алгоритмы для комбинаторных задач. Журнал компьютерных и системных наук , 9 (3): 256–278, декабрь 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Цуёси Ито
источник
3
Цуёши, твои ответы в последнее время были довольно впечатляющими. Когда-нибудь одно из ваших доказательств на этом сайте будет упомянуто как лемма Ито. :-)
Аарон Стерлинг
@ Аарон: Спасибо за ваш добрый комментарий. Обратите внимание, что самая трудная вещь в вопросе, а именно ограничение на случай подгруппы, полностью игнорируется в этом ответе. Пора подумать!
Цуёси Ито
3
@ Аарон: Я не знаю, сказал ли ты это намеренно, но лемма Ито взята ( en.wikipedia.org/wiki/Ito_lemma ).
Робин Котари
11

За ланчем в Брюсселе мы доказали, что эта проблема является NP-Hard довольно коротким сокращением с 3SAT. Наше доказательство не приводит к результату неприемлемости (пока). Мы подумаем больше об этом.

Грубо говоря, вы преобразуете экземпляр 3-SAT (с n переменными и c предложениями) в последовательность перестановок, структурированных следующим образом:

1 ... n для нумерации n переменных n + 1, используемых гаджетом переменной n + 2, n + 3, представляющих 1-е предложение ... n + 2j, n + 2j + 1, представляющих j-е предложение n + 2c + 2 используется сборщиком мусора

переменная xi представлена ​​перестановкой 1, ..., i-1, n + 1, i + 1, ..., n, i, ... и заменой n + 2j + 1, n + 2j для каждого предложения где j, где появляется xi; и перестановка 1, ..., i-1, n + 1, i + 1, ..., n, i, ... и замена n + 2j + 1, n + 2j для каждого предложения, где j где - XI появляется.

Затем мы используем сборщик мусора, чтобы поместить каждое число в такое положение, чтобы оно не могло появиться иначе. Чтобы поместить x в положение y, мы помещаем y в положение n + 2c + 2 и n + 2c + 2 в положение x. У нас будет ровно n + 2c-1 таких сборщиков мусора для каждой переменной и 2 (n + 2c-1) для каждого предложения. 3SAT выполнимо, если мы можем выбрать точно одну из 2 перестановок для каждой переменной, если крышка набора перестановок имеет решение размера n + (n + 2c-1) (n + 2c).

Вероятно, некоторые мелкие детали отсутствуют.

Стефан.

Стефан Лангерман
источник