Рассмотрим задачу покрытия минимального набора со следующими ограничениями: каждый набор содержит не более элементов, а каждый элемент юниверса встречается не более чем в f наборах.
- Пример: случай и f = 2 эквивалентен задаче минимального покрытия вершин в графах с максимальной степенью 4.
Пусть будет наибольшим значением, так что нахождение a ( k , f ) -аппроксимации задачи покрытия минимального множества с параметрами k и f является NP-трудным.
- Пример: ( Berman & Karpinski 1999 ).
Вопрос: у нас есть ссылка, которая суммирует самые сильные известные нижние оценки ? В частности, меня интересуют конкретные значения в случае, когда k и f малы, но f > 2 .
Ограниченные версии проблемы заданного покрытия часто удобны в сокращениях; как правило , есть некоторая свобода в выборе значения и е , а также дополнительную информацию о виде ( К , е ) поможет выбрать правильные значения , которые обеспечивают самые сильные результаты твердости. Ссылки здесь , здесь и здесь обеспечивают отправную точку, но информация несколько устарела и фрагментарна. Мне было интересно, есть ли более полный и современный источник?
Ответы:
Игнорируя ,k
Единственный известный мне результат, который объединяет два параметра:
Существует связь между этой проблемой и проблемой (слабого) независимого набора, но я не совсем уверен, как они связаны с точки зрения приближенности. Я бы порекомендовал изучить это, возможно, начиная здесь: [PDF] .
источник
Используя, как и в ответе Джеймса Кинга, обозначение для наилучшего приближения полиномиального времени покрытия вершин в равномерных гиперграфах степени не более , мы также имеемa(Δ,k) k Δ
(1)a(Δ,k)≤lnΔ+O(1)
из алгоритма жадного приближения для покрытия множеств: покрытие вершин в гиперграфах степени не более аналогично задаче покрытия множеств с наборами размеров не более , для которой жадный алгоритм имеет коэффициент приближения не более , где - гармоническая функция.Д Н Д Н п = 1 + 1 / 2 + ... 1 / п ≤ пер п + O ( 1 )Δ Δ HΔ Hn=1+1/2+…1/n≤lnn+O(1)
В этой статье я показываю, что
(2)supk{a(Δ,k)}≥lnΔ−O(lnlnΔ)
если только , изменив параметры при уменьшении по Фейге.P=NP
источник
На тот случай, если вы еще не нашли его; Самым последним результатом твердости для покрытия вершин ограниченной степени, которое я нашел в недавних поисках, является Chlebik & Chlebikova , например, около 1,01 твердости в кубических графах.
источник
Это не совсем отвечает на ваш вопрос, но, возможно, это может помочь - есть статья [Dinur et al. 2004], которая охватывает f> 2 (но, кажется, не фиксирует k).
источник