Klam Wert - Klam value

In der parametrisierten Komplexität von Algorithmen ist der Klam-Wert eines parametrisierten Algorithmus eine Zahl, die die Parameterwerte begrenzt, für die der Algorithmus vernünftigerweise als praktisch angesehen werden kann. Ein Algorithmus mit einem höheren Klam-Wert kann für einen größeren Bereich von Parameterwerten verwendet werden als ein anderer Algorithmus mit einem niedrigeren Klam-Wert. Der klam-Wert wurde zuerst von Downey und Fellows  ( 1999 ) definiert und wurde seitdem von anderen Forschern in parametrisierter Komplexität verwendet, um verschiedene Algorithmen miteinander zu vergleichen und um Ziele für zukünftige algorithmische Verbesserungen festzulegen.

Definition

Ein Algorithmus wird als nachvollziehbar mit festen Parametern bezeichnet, wenn die Anzahl der von ihm ausgeführten Elementaroperationen an die Form gebunden ist , wobei ein Maß für die Eingabegröße (z. B. die Anzahl der Scheitelpunkte in einem Diagramm ) ein Parameter ist, der den beschreibt Die Komplexität der Eingabe (z. B. die Baumbreite des Diagramms) ist eine Konstante, die nicht von oder abhängt , und eine berechenbare Funktion . ${\ displaystyle O (n ^ {c}) + f (k)}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle c}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle f}$

Gegeben ist eine Zeit gebunden diese Form ist der Klam Wert des Algorithmus (oder genauer der Zeit gebunden) definiert , um den größten Wert sein , so daß für die maximale Anzahl von Schritten von jeder Berechnung gebunden nicht „some angemessene absoluten überschreiten ". Genauer gesagt verwenden sowohl Downey & Fellows (1999) als auch Niedermeier (1998) die Zahl 10 ²⁰ als diese Grenze, und dies wurde von späteren Forschern verfolgt. Um zu verhindern , künstlich die klam Wert eines Algorithmus zu verbessern , indem mehr von seiner Komplexität in der Umsetzung eines Teils der Zeit gebunden, Downey & Fellows (1999) begrenzen auch höchstens drei, gültig für viele bekannte Fest Parameter lenkbar Algorithmen zu sein. ${\ displaystyle k}$${\ displaystyle f (k)}$${\ displaystyle O (n ^ {c})}$${\ displaystyle c}$

Beispiele

Niedermeier (1998) zitiert das Beispiel der Scheitelpunktabdeckung mit ihrem natürlichen Parameter (der Anzahl der Scheitelpunkte in der Abdeckung). Zu dieser Zeit hatte die bekannteste parametrisierte Zeitgrenze . Das Lösen ergibt einen Klam-Wert von ungefähr 129. Der Teil der Zeitgrenze kann jedoch daraus vereinfacht werden, indem eine Formgrenze mit einem größeren konstanten Faktor in der O-Notation und einer größeren Basis des verborgenen Exponenten erhalten wird in seinem ungefähren Dezimalwert. Für eine einfache Exponentialgrenze wie diese kann man direkt lösen, woraus Niedermeier einen Klam-Wert von ungefähr 165 ableitet. Nachfolgende Forschungen haben parametrisierte Vertex-Cover-Algorithmen mit einem Klam-Wert von ungefähr 190 entwickelt. Das heißt, man kann daraus schließen Die Analyse, dass Vertex-Cover-Instanzen mit einer Cover-Größe von mehr als 190 außerhalb der Reichweite dieses Algorithmus liegen, aber Instanzen, deren Cover-Größe ausreichend weit unter dieser Grenze liegt, sind wahrscheinlich lösbar. ${\ displaystyle f (k) = O (k ^ {2} 1,3248 ^ {k})}$${\ displaystyle k ^ {2} 1.3248 ^ {k} = 10 ^ {20}}$${\ displaystyle k ^ {2}}$${\ displaystyle O (1.3248 ^ {k})}$${\ displaystyle f (k) = c ^ {k}}$${\ displaystyle k = 20 / \ log _ {10} c}$${\ displaystyle f (k) = O (1.2738 ^ {k})}$

Ein weiteres Beispiel für ein Problem, bei dem der klam-Wert explizit als Ziel für zukünftige Forschungen verwendet wurde, ist das maximale Blatt-Spanning-Tree-Problem , bei dem das Ziel darin besteht, einen Spanning-Tree eines Graphen mit so vielen Blattknoten wie möglich zu finden (parametrisiert) durch die Anzahl der Blätter). Fellows et al. (2000) entwickeln einen Algorithmus für dieses Problem, den sie unter Verwendung des Klam-Werts mit früheren Arbeiten zu demselben Problem vergleichen: Frühere Algorithmen hatten Klam-Werte von 1 und 5 und ihre haben einen Klam-Wert von 16. Sie schlagen dies jedoch auch vor Es sollte möglich sein, verbesserte Algorithmen für dieses Problem mit einem Klam-Wert von mindestens 50 bereitzustellen. Obwohl dies offen bleibt, haben mehrere spätere Veröffentlichungen den Klam-Wert dieses Problems schrittweise auf 37 verbessert.

Verweise