Обложка ограниченного множества ограниченных частот: сложность аппроксимации

26

Рассмотрим задачу покрытия минимального набора со следующими ограничениями: каждый набор содержит не более элементов, а каждый элемент юниверса встречается не более чем в f наборах.kf

  • Пример: случай и f = 2 эквивалентен задаче минимального покрытия вершин в графах с максимальной степенью 4.k=4f=2

Пусть будет наибольшим значением, так что нахождение a ( k , f ) -аппроксимации задачи покрытия минимального множества с параметрами k и f является NP-трудным.a(k,f)>1a(k,f)kf

Вопрос: у нас есть ссылка, которая суммирует самые сильные известные нижние оценки ? В частности, меня интересуют конкретные значения в случае, когда k и f малы, но f > 2 .a(k,f)kff>2


Ограниченные версии проблемы заданного покрытия часто удобны в сокращениях; как правило , есть некоторая свобода в выборе значения и е , а также дополнительную информацию о виде ( К , е ) поможет выбрать правильные значения , которые обеспечивают самые сильные результаты твердости. Ссылки здесь , здесь и здесь обеспечивают отправную точку, но информация несколько устарела и фрагментарна. Мне было интересно, есть ли более полный и современный источник?kfa(k,f)

Юкка Суомела
источник
Спасибо за ответы до сих пор! Давайте начнем вознаграждение и посмотрим, сможем ли мы получить больше участия. Ради конкретности, я буду рад наградить щедроты , если кто - то дает указатель на нетривиальном нижней границе на . a(3,3)
Юкка Суомела
... и щедроты пошли к ответу , который дал то , что было ближе к нижнему пределу на , но ради справедливости, я решил принять самый тщательный ответ. Спасибо всем; мне кажется , что дело в ( 3 , 3 ) действительно открыто. a(3,3)a(3,3)
Юкка Суомела

Ответы:

15

(Δ,k)(k,f)kΔkfΔk

ε>0Δ

  • supΔ{a(Δ,k)}k
  • supΔ{a(Δ,k)}k1ε (Dinur et al., 2004) , как отметил Лев.
  • Если гипотеза об уникальных играх верна, то , которая является жесткой (Хот & Регев, 2008) .supΔ{a(Δ,k)}kε

Игнорируя ,k

  • supk{a(Δ,k)}Δ (тривиально).
  • supk{a(4,k)}2ε (Холмерин, 2002)

Единственный известный мне результат, который объединяет два параметра:

  • a(Δ,k)k(1o(1))(k(k1)lnlnΔln(Δ)) для фиксированный или медленно растущий с (Halperin, 2002)kkΔ

Существует связь между этой проблемой и проблемой (слабого) независимого набора, но я не совсем уверен, как они связаны с точки зрения приближенности. Я бы порекомендовал изучить это, возможно, начиная здесь: [PDF] .

Джеймс Кинг
источник
Спасибо за указатели и извинения за использование несколько запутанных параметров. (Я пытался быть последовательным с использованием параметра в «минимальном покрытии набора», и я решил следовать нотации, использованной в книге Вазирани.)kk
Юкка Суомела
12

Используя, как и в ответе Джеймса Кинга, обозначение для наилучшего приближения полиномиального времени покрытия вершин в равномерных гиперграфах степени не более , мы также имеемa(Δ,k)kΔ

(1)a(Δ,k)lnΔ+O(1)

из алгоритма жадного приближения для покрытия множеств: покрытие вершин в гиперграфах степени не более аналогично задаче покрытия множеств с наборами размеров не более , для которой жадный алгоритм имеет коэффициент приближения не более , где - гармоническая функция.Д Н Д Н п = 1 + 1 / 2 + ... 1 / п пер п + O ( 1 )ΔΔHΔHn=1+1/2+1/nlnn+O(1)

В этой статье я показываю, что

(2)supk{a(Δ,k)}lnΔO(lnlnΔ)

если только , изменив параметры при уменьшении по Фейге.P=NP

Лука Тревизан
источник
7

На тот случай, если вы еще не нашли его; Самым последним результатом твердости для покрытия вершин ограниченной степени, которое я нашел в недавних поисках, является Chlebik & Chlebikova , например, около 1,01 твердости в кубических графах.

daveagp
источник
6

Это не совсем отвечает на ваш вопрос, но, возможно, это может помочь - есть статья [Dinur et al. 2004], которая охватывает f> 2 (но, кажется, не фиксирует k).

Лев Рейзин
источник