Maksymalny zestaw rozłączny: jaki jest faktyczny współczynnik przybliżenia chciwego algorytmu?

Rozważ problem znalezienia maksymalnego zestawu rozłącznego - maksymalnego zestawu nie nakładających się kształtów geometrycznych z danej kolekcji kandydatów. Jest to problem NP-zupełny, ale w wielu przypadkach następujący chciwy algorytm daje przybliżenie o stałym współczynniku:

Dla każdego kandydującego kształtu x oblicz jego rozłączny numer przecięcia $DIN(x)$ = największa liczba rozłącznych kształtów przecinających się x .
$\arg \min_{x} DIN(x)$
Kontynuuj, aż nie pozostanie więcej kandydatów.

Na przykład rozważmy następujący rysunek ze strony Wikipedii:

wprowadź opis zdjęcia tutaj

Zielony dysk przecina 5 innych dysków, ale jego DIN to 3 (3 czerwone dyski są rozłączne). Najwyższe i najniższe czerwone dyski przecinają 2 inne dyski, ale one same przecinają się, więc ich DIN wynosi 1. Żółte dyski mają DIN równe 2. Chciwy algorytm wybiera zatem najwyższy lub najniższy czerwony dysk.

Jeśli minimalna DIN może być ograniczona przez stałą, wówczas zachłannym algorytmem jest przybliżenie wielomianowe współczynnika stałego.

Na przykład, jeśli wszystkie kształty kandydujące są dyskami jednostkowymi, Marathe i wsp. (1995) pokazują, że zawsze istnieje dysk o DIN co najwyżej 3: dysk skrajnie lewy (dysk o najmniejszej współrzędnej x) przecina co najwyżej 3 inne dyski rozłączne . Dlatego chciwy algorytm daje aproksymację 3, ponieważ uzyskuje 1 dysk dla każdego (najwyżej) 3 dysków w optymalnym rozwiązaniu.

Podobnie, jeśli wszystkie kształty kandydujące są dyskami o dowolnym rozmiarze, zachłanny algorytm daje przybliżone 5, ponieważ najmniejszy dysk przecina co najwyżej 5 innych dysków rozłącznych, tzn. Minimalna DIN wynosi maksymalnie 5.

Jak dotąd tak dobrze, ale czy te czynniki 3 i 5 są ciasne? Nie jestem pewien.

Rozważ powyższy rysunek. Wybranie najbardziej wysuniętego w lewo dysku (zielony) spowoduje znalezienie rozłącznego zestawu o rozmiarze 1, który jest rzeczywiście 3-przybliżeniem do maksymalnego rozłącznego zestawu o rozmiarze 3 (czerwony), ale zachłanny algorytm nie wybierze zielonego dysku - wybierze czerwony / górny dysk, którego DIN wynosi 1. W tym przypadku zachłanny algorytm znajdzie optymalne rozwiązanie.

Nie mogłem znaleźć przeciwnego przykładu dla ogólnego , w którym zachłanny algorytm znajduje zestaw rozłączny z dyskami jednostkowymi , podczas gdy maksymalny zestaw rozłączny ma . Właściwie nie mogłem nawet skonstruować ogólnego kontrprzykładu, w którym minimalne DIN rzeczywiście wynosi 3. Najlepsze, co mogłem wymyślić, to następujące, w których każdy dysk jednostkowy przecina co najwyżej 2 inne dyski rozłączne (tj. Minimalny DIN to 2). Ale nawet tutaj chciwy algorytm znajduje optymalne rozwiązanie zamiast przybliżenia 2: $n$ $n$ $3n$

wprowadź opis zdjęcia tutaj

Moje pytania to:

Jaka jest rzeczywista maksymalna min. DIN w kolekcjach dysków jednostkowych? Dyski o dowolnych rozmiarach?
Jaki jest faktyczny współczynnik przybliżenia chciwego algorytmu dla kolekcji dysków jednostkowych? W przypadku dysków o dowolnej wielkości? (współczynnik ten jest co najwyżej tak duży, jak maksymalna min. DIN, ale może być mniejszy).

AKTUALIZACJA: Dla każdego k-krotki kształtów , zdefiniuj = największa liczba rozłącznych kształtów przeciętych przez ich połączenie . Zdefiniuj jako minimalną wartość DIN wszystkich k-krotek rozłącznych kształtów. $x_1,...,x_k$ $DIN(x_1,...,x_k)$ $x_1\cup...\cup x_k$ $minDIN_k$

Na przykład w odpowiedzi Yury poniżej , ponieważ każde koło przecina 3 inne koła. , ponieważ możliwe jest wybranie 2 rozłącznych okręgów, jednego z zewnętrznego koła i jednego z wewnętrznego koła, które razem przecinają tylko 4 inne koła. Dla każdego , . $minDIN_1=3$ $minDIN_2=4$ $k$ $minDIN_k\leq k+2$

MYŚLĘ, że współczynnik aproksymacji pożądliwego algorytmu może być ograniczony przez , ponieważ dla każdego kształtu w optymalnym rozwiązaniu mamy co najmniej kształtów na wyjściu algorytmu. Czy to jest poprawne? $\frac{minDIN_k}{k}$ $minDIN_k$ $k$

EDYCJA: Czytam teraz doskonałą książkę Problemy badawcze w dyskretnej geometrii . Chociaż nie znalazłem dokładnie tego problemu, znalazłem problem, który wygląda na powiązany. W rozdziale „2.5 Cienkie wypełnienia z wieloma sąsiadami” podano przykłady wypełnień z kręgów, w których każde koło dotyka 5 innych kręgów. Zastanawiam się, czy takie wypełnienie może dać konfigurację kół o DIN = 5.

cg.comp-geom

— Erel Segal-Halevi
źródło

Warto zauważyć, że obliczenie DIN może być tak trudne, jak obliczenie samego maksimum niezależnego zestawu. Na przykład w przypadku grafów dyskowych (zamiast grafów jednostkowych) można dodać duży dysk przecinający wszystkie inne obiekty w układzie; obliczenie jego DIN odpowiada obliczeniu maksymalnego niezależnego zestawu w oryginalnym układzie.

— Bart Jansen

@BartJansen To prawda, ale chciwy algorytm tak naprawdę nie musi obliczać DIN dla każdego kształtu - potrzebuje tylko kształtu z minimalnym DIN. Ponieważ minimalna wartość DIN wynosi co najwyżej 5 (w przypadku dysków o dowolnej wielkości), musi ona tylko sprawdzić wszystkie podzbiory zawierające co najwyżej 6 dysków i sprawdzić, czy jeden z nich jest niezależny. Można to zrobić w czasie dla każdego kształtu.

O (n^{6})

$O(n^6)$

— Erel Segal-Halevi

W przypadku ostatniego pytania - tak, jest poprawne.

— domotorp

Jaka jest rzeczywista maksymalna minimalna wartość DIN w kolekcjach dysków jednostkowych?

To jest 3. wprowadź opis zdjęcia tutaj

— Jurij
źródło

Są tu 32 dyski jednostkowe, ułożone na 2 poziomach po 16. Każdy dysk przecina 3 dyski rozłączne - 2 na swoim poziomie i 1 na drugim poziomie. Ale chciwy algorytm nadal znajdzie optymalne rozwiązanie z 16 dyskami.

— Erel Segal-Halevi

Tak, że tylko 1/4 odpowiedzi na pytanie :-)

— Yury