Klam värde

I den parametriserade komplexiteten hos algoritmer är klam -värdet för en parametriserad algoritm ett tal som begränsar parametervärdena för vilka algoritmen rimligen kan förväntas vara praktisk. En algoritm med ett högre klam-värde kan användas för ett bredare område av parametervärden än en annan algoritm med ett lägre klam-värde. klam-värdet definierades först av Downey och Fellows ( 1999 ), och har sedan dess använts av andra forskare i parametriserad komplexitet både som ett sätt att jämföra olika algoritmer med varandra och för att sätta upp mål för framtida algoritmiska förbättringar.

Definition

En algoritm sägs vara hanteringsbar med fasta parametrar om antalet elementära operationer den utför har en gräns av formen $O(n^{c})+f(k)$ , där $n$ är ett mått på indatastorleken (som antalet hörn i en graf ), $k$ är en parameter som beskriver komplexiteten hos inmatningen (som trädbredden på graf), $c$ är en konstant som inte beror på $n$ eller $k$ , och $f$ är en beräkningsbar funktion .

$) {\displaystyle f(k) }$ , definieras klam-värdet för algoritmen (eller mer korrekt av tidsgränsen) som det största värdet av $k$ så att inte överstiger "någon rimlig absolut gräns för det maximala antalet steg i någon beräkning". Mer exakt använder både Downey & Fellows (1999) och Niedermeier (1998) siffran 10 ²⁰ som denna gräns, och detta har följts av senare forskare. För att förhindra artificiell förbättring av klam-värdet för en algoritm genom att lägga mer av dess komplexitet i ${\displaystyle O(n^{c})}-$ delen av den tidsbundna, begränsar Downey & Fellows (1999) också $c$ ska vara högst tre, giltigt för många kända algoritmer som kan hanteras med fasta parametrar.

Exempel

Niedermeier (1998) nämner exemplet med vertex cover , med dess naturliga parameter (antal vertex i locket). Vid den tiden hade den mest kända parametriserade tidsgränsen $f(k)=O(k^{2}1,3248^{k})$ . Att lösa $k^{2}1,3248^{k}=10^{20}$ ger ett klam-värde på ungefär 129. $k^{2}$ en del av tidsgränsen kan förenklas ur det, vilket ger en gräns av formen $O(1,3248^{k})$ med både en större konstant faktor gömd i O-notationen och en större basen för exponenten gömd i dess ungefärliga decimalvärde. För en enkel exponentiell gräns $f(k)=c^{k}$ som den här, kan man lösa direkt $k=20/ \log _{10}c$ från vilket Niedermeier härleder ett klam-värde på ungefär 165. Efterföljande forskning har utvecklat parametriserade vertextäckningsalgoritmer med $f(k)=O(1,2738^ {k})$ ger ett klam-värde på ungefär 190. Det vill säga, man kan dra slutsatsen från denna analys att vertextäckningsinstanser med täckstorlek större än 190 är utom räckhåll för denna algoritm, men instanser vars täckstorlek är tillräckligt långt under denna gränsen är sannolikt lösbar.

Ett annat exempel på ett problem där klam-värdet uttryckligen har använts som ett mål för framtida forskning är problemet med maximal lövspännande träd, där målet är att hitta ett spännande träd i en graf med så många lövnoder som möjligt (parametriserad med antalet löv). Fellows et al. (2000) utvecklar en algoritm för detta problem som de jämför med klam-värdet med tidigare arbete med samma problem: tidigare algoritmer hade klam-värden på 1 och 5, och deras har ett klam-värde på 16. Men de föreslår också att det borde vara möjligt att tillhandahålla förbättrade algoritmer för detta problem med ett klam-värde på minst 50. Även om detta förblir öppet, har flera senare artiklar stegvis förbättrat klam-värdet för detta problem till 37.