Меня интересует параметризованная сложность того, что я буду называть проблемой d-мерного ударного множества: с учетом пространства диапазона (т. Е. Системы множеств / гиперграфа) S = (X, R) с VC-размерностью не более d и натуральное число k, содержит ли X подмножество размера k, которое попадает в...
Рассмотрим задачу покрытия минимального набора со следующими ограничениями: каждый набор содержит не более элементов, а каждый элемент юниверса встречается не более чем в f наборах.kkkfff Пример: случай и f = 2 эквивалентен задаче минимального покрытия вершин в графах с максимальной степенью...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Учитывая набор S из nxn матриц перестановок (который является лишь малой долей из n! Возможных матриц перестановок), как мы можем найти подмножества T минимального размера в S, чтобы при добавлении матриц T было по крайней мере 1 в каждой позиции? Меня интересует эта проблема, где S - небольшая...
Как называется следующий вариант обложки набора? Для заданного набора S, набора C подмножеств S и целого положительного числа K существуют ли K наборов в C, так что каждая пара элементов S лежит в одном из выбранных подмножеств. Примечание. Нетрудно понять, что эта проблема является NP-полной:...
Рассмотрим набор множеств над базовым множеством где и , и пусть будет положительным целым числом.F = { F 1 , F 2 , … , F n } U = { e 1 , e 2 , … , e n } | F i | « П е я ∈ F я кF={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\}U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\}|Fi||F_i| ≪\ll nnei∈Fie_i \in F_ikk Цель...
Input вселенная и семейство подмножеств , скажем, . Будем считать , что подмножества можно покрыть , то есть, .U F ⊆ 2 U F U ⋃ E ∈ F E = UUUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Инкрементный последовательность покрытие представляет собой...
Таким образом, проблема покрытия множеств является тривиальной, если ни один из наборов кандидатов не пересекается друг с другом. Однако что, если размер пересечения для любой пары наборов кандидатов был не больше 1? Эта проблема NP-сложная? Я был бы признателен за любое понимание. Спасибо...
Многие здесь, вероятно, знают о недавних суперлинейных нижних оценках Алона для сетей в естественной геометрической обстановке [PDF] . Я хотел бы знать, что, во всяком случае, такая нижняя граница подразумевает в отношении аппроксимируемости связанных задач Set Cover / Hitting Set. ϵϵ\epsilon Чтобы...
Предположим, у меня есть простой многоугольник и целое число k . Каковы некоторые существующие подходы для нахождения наименьшего радиуса ¨R таким образом, что я могу покрыть S с K окружностей радиуса г ? Как насчет, если г фиксирован, и я хочу минимизировать к...
Насколько сложна проблема Set Cover, если число элементов ограничено некоторой функцией (например, ), где - размер экземпляра задачи. Формально,nlognlogn\log nnnn Пусть и где и . Насколько сложно решить следующую проблему?F = { S 1 , ⋯ , S n } S i ⊆ U m = O ( log n )U= { е1, ⋯ ,...
Я пытаюсь показать, что определенная проблема недопустима из-за сокращения охвата. Мое сокращение превращает экземпляр с базовым набором размера и устанавливает в экземпляр моей проблемы, где определенный параметр имеет размер . Затем я могу показать, что экземпляр установленного покрытия, где...