Konsequenzen der Untergrenzen für Netze bei der Approximation

10

Viele hier kennen wahrscheinlich Alons jüngste superlineare Untergrenzen für Netze in einer natürlichen geometrischen Umgebung [PDF] . Ich würde gerne wissen, was, wenn überhaupt, eine solche Untergrenze für die Annäherung der damit verbundenen Set-Cover- / Hitting-Set-Probleme bedeutet. ϵ

Um etwas genauer zu sein, betrachten Sie eine Familie von Bereichsräumen, zum Beispiel die Familie:

{(X,R) : ist eine endliche planare Punktmenge, enthält alle Schnittpunkte von mit LinienXRX}

Wenn für eine Funktion , die linear oder superlinear ist , die Familie einen Bereichsraum enthält, der keine Netze der Größe zulässt , was bedeutet dies, wenn überhaupt, für das Minimum Hitting? Problem auf diese Familie von Bereichsräumen beschränken?fϵf(1/ϵ)

James King
quelle
2
Es gibt ein neues Ergebnis mit noch stärkeren Untergrenzen: arxiv.org/abs/1012.1240
Suresh Venkat

Antworten:

7

Wenn ein Bereichsraum ein Netz der Größe , beträgt die Integralitätslücke des gebrochenen Schlagsatzes (oder der Satzabdeckung) . Sehen Sie sich die Arbeit von Philip Long an ( hier [Die Arbeit von Even et al. Ist später als diese Arbeit und entdecken Sie einige seiner Sachen wieder]). Siehe auch die Folien 13-16 hier .ϵf(1/ϵ)f(1/ϵ)/(1/ϵ)

Kurz gesagt, wenn nichtlineare Netze vorhanden sind, bedeutet dies, dass es sehr schwierig sein wird, das relevante Problem der Treffermenge / Satzabdeckung innerhalb eines besseren als eines konstanten Faktors zu approximieren.ϵ

Sariel Har-Peled
quelle
Welcher Abschnitt des ersten Papiers ist für dieses spezielle Problem relevant? Oder äquivalent dazu sagen Sie im zweiten Link: "In geometrischen Einstellungen gibt es ein Netz der Größe wenn die Integritätslücke ." Ich habe Probleme, das zu verstehen. ϵO(K/ϵ)K
Taninamdar
1
Satz 1 in der Zeitung ....
Sariel Har-Peled