Неуклюжее значение

В параметризованной сложности алгоритмов . значение klam параметризованного алгоритма представляет собой число, ограничивающее значения параметров, для которых можно разумно ожидать, что алгоритм будет практичным Алгоритм с более высоким значением klam можно использовать для более широкого диапазона значений параметров, чем другой алгоритм с более низким значением klam. Значение klam было впервые определено Дауни и Феллоузом ( 1999 ). и с тех пор использовался другими исследователями параметризованной сложности как для сравнения различных алгоритмов друг с другом, так и для постановки целей для будущих улучшений алгоритмов.

Определение

Алгоритм называется управляемым с фиксированными параметрами, если количество выполняемых им элементарных операций имеет границу вида $O(n^{c})+f(k)$, где $n$ — это некоторая мера входного размера (например, количество вершин в графе ), $k$ параметр, описывающий сложность входных данных (например, ширину дерева графа), $c$ является константой, не зависящей от $n$ или $k$, и $f$ является вычислимой функцией .

Учитывая временную границу этой формы, значение klam алгоритма (или, точнее, временной границы) определяется как наибольшее значение $k$ такой, что $f(k)$ не превышает «некоторой разумной абсолютной границы максимальногоколичество шагов любого вычисления». Точнее, и Дауни и Феллоуз (1999) , и Нидермайер (1998) используют число 10. ²⁰ как это связано, и за этим последовали более поздние исследователи. Чтобы предотвратить искусственное улучшение klam-ценности алгоритма путем увеличения его сложности в $O(n^{c})$ часть времени ограничена, Downey & Fellows (1999) также ограничивают $c$ должно быть не более трех, что справедливо для многих известных управляемых алгоритмов с фиксированными параметрами.

Примеры

Нидермайер (1998) приводит пример вершинного покрытия с его естественным параметром (количеством вершин в покрытии). В то время наиболее известная параметризованная оценка времени имела $f(k)=O(k^{2}1.3248^{k})$. Решение $k^{2}1.3248^{k}=10^{20}$ дает значение klam примерно 129. Однакотот $k^{2}$ часть временной границы можно упростить из нее, придав границе вид $O(1.3248^{k})$ как с большим постоянным коэффициентом, скрытым в O-нотации, так и с большим основанием показателя степени, скрытым в его приблизительном десятичном значении.Для простой экспоненциальной оценки $f(k)=c^{k}$такой как этот, можно решить напрямую $k=20/\log _{10}c$ из которого Нидермейер выводит значение klam примерно 165. Последующие исследования разработали параметризованные алгоритмы покрытия вершин с $f(k)=O(1.2738^{k})$ давая значение klam примерно 190. То есть из этого анализа можно сделать вывод, что экземпляры вершинного покрытия с размером покрытия больше 190 недоступны этому алгоритму, но экземпляры, размер покрытия которых значительно ниже этого предела, вероятно, будут решаемый.

Другим примером проблемы, в которой значение klam было явно использовано в качестве цели будущих исследований, является задача о максимальном листовом связующем дереве , в которой цель состоит в том, чтобы найти связующее дерево графа с как можно большим количеством листовых узлов (параметризованное по количеству листьев). Товарищи и др. (2000) разработали алгоритм для этой проблемы, который они сравнивают, используя значение klam, с предыдущими работами по той же проблеме: предыдущие алгоритмы имели значения klam 1 и 5, а их алгоритм имеет значение klam 16. Однако они также предполагают, что должно быть возможно предоставить улучшенные алгоритмы для этой проблемы со значением klam не менее 50. Хотя это остается открытым, в нескольких более поздних статьях значение klam этой проблемы постепенно улучшилось до 37.