Wartość Klama

W sparametryzowanej złożoności algorytmów wartość klam sparametryzowanego algorytmu jest liczbą, która ogranicza wartości parametrów, dla których można rozsądnie oczekiwać, że algorytm będzie praktyczny . Algorytm z wyższą wartością klam może być użyty do szerszego zakresu wartości parametrów niż inny algorytm z niższą wartością klam. Wartość klam została po raz pierwszy zdefiniowana przez Downeya i Fellowsa ( 1999 ) i od tego czasu był używany przez innych badaczy w sparametryzowanej złożoności zarówno jako sposób porównywania różnych algorytmów ze sobą, jak i do wyznaczania celów dla przyszłych ulepszeń algorytmicznych.

Definicja

Mówi się, że algorytm jest wykonalny ze stałymi parametrami, jeśli liczba wykonywanych przez niego operacji elementarnych ma granicę postaci ${\ Displaystyle O (n ^ {c}) + f (k) }$ , gdzie jest $rozmiaru$$jest$ (taką jak liczba wierzchołków na wykresie ), parametrem opisującym złożoność danych wejściowych (takich jak szerokość drzewa wykres), $,$$jest stałą$$}$ która nie zależy od ani $jest$ a funkcją obliczalną .

$f (k) }$ postaci, wartość klam algorytmu (lub dokładniej ograniczenia czasowego) jest zdefiniowana jako największa wartość taka, że $displaystyle$ nie przekracza „pewnej rozsądnej bezwzględnej granicy maksymalnej liczby kroków dowolnego obliczenia”. Dokładniej, zarówno Downey i Fellows (1999), jak i Niedermeier (1998) używają liczby 10 ²⁰ jako ta granica, i to było śledzone przez późniejszych badaczy. $części$ poprawianiu wartości klam algorytmu poprzez umieszczanie większej jego złożoności w czasowo, Downey & Fellows (1999) ograniczają ${\ displaystyle c}$ najwyżej trzy, ważne dla wielu znanych algorytmów o stałych parametrach, które można zastosować.

Przykłady

Niedermeier (1998) podaje przykład pokrycia wierzchołków z jego naturalnym parametrem (liczbą wierzchołków w pokryciu). W tamtym czasie najbardziej znana sparametryzowana granica czasu miała ${\ Displaystyle f (k) = O (k ^ {2} 1,3248 ^ {k})}$ . Rozwiązanie ${\ Displaystyle k ^ {2} 1,3248 ^ {k} = 10 ^ {20}}$ daje klam wartość około 129. Jednak ${\ Displaystyle k ^ {2}}$ część granicy czasu można z niej uprościć, dając granicę postaci z obiema większą stałą ${\ Displaystyle O (1,3248 ^ {k})}$ współczynnik ukryty w notacji O i większa podstawa wykładnika ukryta w jego przybliżonej wartości dziesiętnej. Dla prostej granicy wykładniczej, takiej jak ta, można rozwiązać bezpośrednio ${\ Displaystyle f (k) = c ^ {k$${\ Displaystyle k = 20/\ log _ {10} c},$ z którego Niedermeier wywodzi wartość klam wynoszącą około 165. W późniejszych badaniach opracowano sparametryzowane algorytmy pokrycia wierzchołków z ${\ Displaystyle f(k)=O(1,2738^{k})}$ dając klam o wartości około 190. Oznacza to, że z tej analizy można wywnioskować, że przypadki pokrycia wierzchołków o rozmiarze pokrycia większym niż 190 są poza zasięgiem tego algorytmu, ale przypadki, których rozmiar pokrycia jest wystarczająco dużo poniżej tego limitu, prawdopodobnie będą rozwiązywalne.

Innym przykładem problemu, w którym wartość klam została jawnie wykorzystana jako cel przyszłych badań, jest problem maksymalnego drzewa rozpinającego liście , w którym celem jest znalezienie drzewa rozpinającego grafu z jak największą liczbą węzłów liścia (sparametryzowane według liczby liści). Fellows i in. (2000) opracuj algorytm dla tego problemu, który porównują za pomocą wartości klam z wcześniejszymi pracami nad tym samym problemem: poprzednie algorytmy miały wartości klam 1 i 5, a ich mają wartość klam równą 16. Sugerują jednak również, że powinno to być możliwe aby zapewnić ulepszone algorytmy dla tego problemu z wartością klam wynoszącą co najmniej 50. Chociaż pozostaje to otwarte, kilka późniejszych artykułów stopniowo poprawiło wartość klam tego problemu do 37.