В параметризованном сложности из алгоритмов , то значение Klam параметризованного алгоритма является числом , которое ограничивает значение параметров , для которых алгоритм может разумно ожидать , чтобы быть практичными. [1] Алгоритм с более высоким значением klam может использоваться для более широкого диапазона значений параметров, чем другой алгоритм с более низким значением klam. Значение klam было впервые определено Дауни и Феллоуз ( 1999 ), [2] [3] и с тех пор используется другими исследователями в параметризованной сложности как для сравнения различных алгоритмов друг с другом, так и для постановки целей на будущее. алгоритмические улучшения.
Определение
Алгоритм называется управляемым с фиксированными параметрами, если количество выполняемых им элементарных операций имеет границу вида , где - некоторая мера размера ввода (например, количество вершин в графе ),- параметр, описывающий сложность ввода (например, ширину дерева графика), константа, не зависящая от или же , а также является вычислимой функцией .
Учитывая временную границу этой формы, значение клама алгоритма (или, точнее, временной границы) определяется как наибольшее значение такой, что не превышает «некоторой разумной абсолютной границы максимального числа шагов любого вычисления». [1] Точнее, Downey & Fellows (1999) и Niedermeier (1998) использовали число 10 20 в качестве этой границы, и это было сделано более поздними исследователями. Чтобы предотвратить искусственное улучшение клам-значения алгоритма, добавляя больше его сложности вчасть временных рамок, Дауни и сотрудники (1999) также ограничивают быть не более трех, действительным для многих известных управляемых алгоритмов с фиксированными параметрами.
Примеры
Niedermeier (1998) приводит пример вершинного покрытия с его естественным параметром (числом вершин в покрытии). В то время наиболее известная параметризованная временная граница была. Решение дает значение клама примерно 129. Однако часть временного ограничения может быть упрощена вне его, давая границу формы с большим постоянным множителем, скрытым в O-нотации, и большим основанием экспоненты, скрытым в его приблизительном десятичном значении. Для простой экспоненциальной оценкикак этот, можно решить напрямую из которого Нидермейер выводит значение клама примерно 165. В ходе последующих исследований были разработаны параметризованные алгоритмы покрытия вершин с [4] дает значение клама примерно 190. То есть из этого анализа можно сделать вывод, что экземпляры вершинного покрытия с размером покрытия больше 190 находятся вне досягаемости этого алгоритма, но экземпляры, размер покрытия которых значительно ниже этого предела, вероятно, будет разрешимым.
Другим примером проблемы, в которой значение klam явно использовалось в качестве цели для будущих исследований, является проблема максимального листового остовного дерева , цель которой состоит в том, чтобы найти остовное дерево графа с максимально возможным количеством листовых узлов (параметризованные по количеству листьев). Fellows et al. (2000) разрабатывают алгоритм для этой проблемы, который они сравнивают, используя значение klam, с предыдущими работами по той же проблеме: предыдущие алгоритмы имели значения klam 1 и 5, а их - значение klam 16. [5] Однако они также предполагают, что должна быть возможность предоставить улучшенные алгоритмы для этой проблемы со значением klam не менее 50. Хотя это остается открытым, в нескольких более поздних работах постепенно улучшалось значение klam этой проблемы до 37. [6]
Рекомендации
- ^ a b Niedermeier, Rolf (1998), "Некоторые перспективы эффективных алгоритмов с фиксированными параметрами", в Rovan, Branislav (ed.), SOFSEM'98: Theory and Practice of Informatics , Lecture Notes in Computer Science, 1521 , Springer, pp. 168–185.
- ^ Дауни, Р.Г .; Стипендиаты, MR (1999), параметризованная сложность , монографии по компьютерным наукам, Springer, стр. 13–14, DOI : 10.1007 / 978-1-4612-0515-9 , ISBN 0-387-94883-X, Руководство по ремонту 1656112.
- ^ Niedermeier (1998) использует значение клама и был опубликован раньше, чем Downey & Fellows (1999) , но отдает должное Дауни и его коллегам за эту концепцию.
- ^ Чен, Цзианэр; Kanj, Iyad A .; Xia, Ge (2006), "Улучшение параметризованных верхние границ для вершинного покрова", MFCS 2006: Математические основы информатики , Lecture Notes в области компьютерных наук, 4162 , Springer, С. 238-249,. DOI : 10.1007 / 11821069_21 , MR 2298181.
- ^ Товарищи, Майкл Р .; Маккартин, Кэтрин; Розамонд, Фрэнсис А .; Стеге, Ульрике (2000), «Координированные ядра и каталитическое восстановление: улучшенный алгоритм FPT для максимального листового покрывающего дерева и других проблем», FST-TCS 2000: Основы программных технологий и теоретической информатики , Лекционные заметки в вычислительной технике . Sci . , 1974 ., Springer, Berlin, С. 240-251, DOI : 10.1007 / 3-540-44450-5_19 , MR 1850108.
- ^ Бинкеле-Райбл, Даниэль; Фернау, Хеннинг (2014), «Параметризованный анализ меры и преодоления для поиска остовного дерева с k- листом в неориентированном графе», Дискретная математика и теоретическая информатика , 16 (1): 179–200, MR 3188035.