Bounded-Cardinality-Bounded-Frequency-Set-Cover: Härte der Approximation

26

Berücksichtigen Sie das Problem der minimalen Mengenabdeckung mit den folgenden Einschränkungen: Jede Menge enthält höchstens Elemente, und jedes Element des Universums kommt in höchstens Mengen vor.fkf

  • Beispiel: Der Fall und f = 2 entspricht dem Minimum Vertex Cover Problem in Graphen mit maximalem Grad 4.f = 2k=4f=2

Sei a(k,f)>1 der größte Wert, so dass es NP-schwer ist , eine a(k,f) -Näherung des Minimum-Set-Cover-Problems mit den Parametern k und f .

Frage: Haben wir eine Referenz, die die stärksten bekannten Untergrenzen von a(k,f) ? Insbesondere interessieren mich konkrete Werte für den Fall, dass sowohl k als auch f klein sind, aber f>2 .


Eingeschränkte Versionen des Set-Cover-Problems eignen sich häufig für Reduzierungen. In der Regel besteht eine gewisse Freiheit bei der Auswahl der Werte für k und f , und weitere Informationen zu a(k,f) helfen bei der Auswahl der richtigen Werte, die die besten Härteergebnisse liefern. Referenzen hier , hier und hier bieten einen Ausgangspunkt, aber die Informationen sind etwas veraltet und fragmentarisch. Ich habe mich gefragt, ob es eine vollständigere und aktuellere Quelle gibt.

Jukka Suomela
quelle
Vielen Dank für die bisherigen Antworten! Beginnen wir eine Prämie und sehen wir, ob wir mehr Beteiligung bekommen können. Der Vollständigkeit halber werde ich das Kopfgeld gerne vergeben, wenn jemand einen Hinweis auf eine nicht triviale Untergrenze von a(3,3) .
Jukka Suomela
... und das Kopfgeld ging zu der Antwort, die etwas ergab, das einer Untergrenze von am nächsten kam , aber aus Gründen der Fairness entschied ich mich, die gründlichste Antwort zu akzeptieren. Dank an alle; es scheint, dass der Fall von tatsächlich offen ist. a ( 3 , 3 )a(3,3)a(3,3)
Jukka Suomela

Antworten:

15

Unter Verwendung der allgemeineren Parameternotation anstelle von entspricht dies dem Vertex-Cover-Problem in -uniformen Hypergraphen mit maximalem Grad . Aus Gründen der Übereinstimmung mit der Literatur verwende ich wenn Sie , und wenn Sie .( k , f ) k Δ k f Δ k(Δ,k)(k,f)kΔkfΔk

Bei einer Konstante werden die Ergebnisse ignoriert, wenn includeΔε>0Δ

  • supΔ{a(Δ,k)}k aus der allgemeinen Deckung.
  • supΔ{a(Δ,k)}k1ε (Dinur et al., 2004) , wie von Lev.
  • Wenn die Vermutung der einzigartigen Spiele wahr ist, dann ist , was eng ist (Khot & Regev, 2008) .supΔ{a(Δ,k)}kε

ignorieren ,k

  • supk{a(Δ,k)}Δ (trivial).
  • supk{a(4,k)}2ε (Holmerin, 2002)

Das einzige Ergebnis, von dem ich weiß, dass es die beiden Parameter kombiniert, ist

  • kkΔa(Δ,k)k(1o(1))(k(k1)lnlnΔln(Δ)) für Behoben: oder wächst langsam mit (Halperin, 2002)kkΔ

Es gibt einen Zusammenhang zwischen diesem Problem und dem (schwachen) Independent-Set-Problem, aber ich bin mir nicht ganz sicher, wie sie in Bezug auf die Approximierbarkeit zusammenhängen. Ich würde empfehlen, dies zu untersuchen, vielleicht hier zu beginnen: [PDF] .

James King
quelle
Vielen Dank für die Hinweise und Entschuldigungen für die Verwendung der etwas verwirrenden Parameter. (Ich habe versucht, mit der Verwendung des Parameters in "minimum set cover" übereinzustimmen, und ich habe beschlossen, der in Vaziranis Buch verwendeten Notation zu folgen.)kkk
Jukka Suomela
12

Verwendung wie in James King Antwort, die Schreibweise für die bestmögliche Polynomzeit Annäherung der Knotenüberdeckung in -Einheitliche Hyper vom Grad höchstens haben wir auchk Δa(Δ,k)kΔ

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

aus dem Greedy-Approximationsalgorithmus für Mengenabdeckung : Die Scheitelabdeckung in Hypergraphen mit einem Grad von höchstens ist das gleiche wie das Problem mit Mengenabdeckung mit höchstens , für das der Greedy-Algorithmus ein Approximationsverhältnis von höchstens hat. Dabei ist die harmonische Funktion.Δ H Δ H n = 1 + 1 / 2 + ... 1 / n ln n + O ( 1 )ΔΔHΔHn=1+1/2+1/nlnn+O(1)

In diesem Artikel zeige ich das

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

es sei denn, , durch Ändern der Parameter in einer Reduktion von Feige.P=NP

Luca Trevisan
quelle
7

Nur für den Fall, dass Sie es noch nicht gefunden haben; Das jüngste Ergebnis der Härte für die Vertex-Abdeckung mit beschränktem Grad, das ich kürzlich bei der Suche gefunden habe, ist Chlebik & Chlebikova , z. B. 1,01-Härte in kubischen Diagrammen.

daveagp
quelle
6

Dies beantwortet Ihre Frage nicht ganz, aber vielleicht kann es helfen - es gibt ein Papier [Dinur et al. 2004], die f> 2 abdeckt (aber k nicht zu fixieren scheint).

Lev Reyzin
quelle