Алгоритм параметризованной аппроксимации

Алгоритм параметризованной аппроксимации — это тип алгоритма , целью которого является поиск приближенных решений NP-сложных задач оптимизации за полиномиальное время в зависимости от размера входных данных и функции определенного параметра. Эти алгоритмы призваны сочетать в себе лучшие аспекты традиционных алгоритмов аппроксимации и управляемости с фиксированными параметрами.

В традиционных алгоритмах аппроксимации цель состоит в том, чтобы найти решения, которые отстоят не более чем на определенный коэффициент $α$ от оптимального решения, известного как $α$ -аппроксимация, за полиномиальное время. С другой стороны, параметризованные алгоритмы предназначены для поиска точных решений задач, но с тем ограничением, что время работы алгоритма является полиномиальным от размера входных данных и функцией определенного параметра $k$ . Параметр описывает некоторые свойства входа и в типичных приложениях невелик. Говорят, что задача решается с фиксированными параметрами (FPT), если существует алгоритм, который может найти оптимальное решение в $f(k)n^{O(1)}$ время, где $f(k)$ — функция, независимая от входного размера $n$ .

Алгоритм параметризованной аппроксимации направлен на поиск баланса между этими двумя подходами путем нахождения приближенных решений за время FPT: алгоритм вычисляет $α$ -аппроксимацию за время $f(k)n^{O(1)}$ время, где $f(k)$ — функция, независимая от входного размера $n$ . Этот подход направлен на преодоление ограничений обоих традиционных подходов за счет более строгих гарантий качества решения по сравнению с традиционными приближениями, сохраняя при этом эффективное время выполнения, как в алгоритмах FPT. Обзор области исследований параметризованных алгоритмов аппроксимации можно найти в обзоре Маркса. ^[1] и более недавнее исследование Feldmann et al. ^[2]

Получаемые коэффициенты аппроксимации

Полный потенциал алгоритмов параметризованной аппроксимации используется, когда показано, что данная задача оптимизации допускает $алгоритм α$ -аппроксимации, работающий в $f(k)n^{O(1)}$ время, в то время как задача, напротив, не имеет полиномиального $алгоритма α$ -аппроксимации (при некотором предположении сложности , например, ${\mathsf {P}}\neq {\mathsf {NP}}$ ), ни алгоритм FPT для данного параметра $k$ (т. е. он как минимум W[1]-труден ).

Например, некоторые задачи, которые являются APX-трудными и W[1]-трудными, допускают параметризованную схему аппроксимации (PAS) , т. е. для любого $\varepsilon >0$ а $(1+\varepsilon )$ -аппроксимация может быть вычислена в $f(k,\varepsilon )n^{g(\varepsilon )}$ время для некоторых функций $f$ и $g$ . Затем это обходит нижние границы с точки зрения аппроксимации за полиномиальное время и управляемости с фиксированными параметрами. PAS по духу похож на схему аппроксимации с полиномиальным временем (PTAS), но дополнительно использует заданный параметр $k$ . Поскольку степень полинома во время работы PAS зависит от функции $g(\varepsilon )$ , значение $\varepsilon$ предполагается произвольным, но постоянным, чтобы PAS работал во времени FPT. Если это предположение неудовлетворительно, $\varepsilon$ также рассматривается как параметр для получения эффективной параметризованной схемы аппроксимации (EPAS) , которая для любого $\varepsilon >0$ вычисляет $(1+\varepsilon )$ -аппроксимация в $f(k,\varepsilon )n^{O(1)}$ время для некоторой функции $f$ . По духу это похоже на эффективную схему аппроксимации с полиномиальным временем (EPTAS).

к -вырезать

Задача k -cut не имеет полиномиального времени. $(2-\varepsilon )$ -алгоритм аппроксимации для любого $\varepsilon >0$ , предполагая ${\mathsf {P}}\neq {\mathsf {NP}}$ и гипотеза расширения малого множества . ^[3] Он также W[1]-жестко параметризуется числом $k$ требуемых компонентов. ^[4] Однако существует EPAS, которая вычисляет $(1+\varepsilon )$ -аппроксимация в $(k/\varepsilon )^{O(k)}n^{O(1)}$ время. ^[5]

Дерево Штайнера

представляет Задача «Дерево Штейнера» собой FPT, параметризованную количеством терминалов. ^[6] Однако для «двойственного» параметра, состоящего из числа $k$ нетерминалов, содержащихся в оптимальном решении, задача является W[2]-трудной (из-за фольклорной редукции к задаче о доминирующем множестве ). Дерево Штайнера также известно как APX-трудное . ^[7] Однако существует EPAS, вычисляющая $(1+\varepsilon )$ -аппроксимация в $2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}$ время. ^[8] Более общая задача Леса Штайнера является NP-трудной на графах с шириной дерева 3. Однако на графах с шириной дерева $t$ EPAS может вычислить $(1+\varepsilon )$ -аппроксимация в $2^{O({\frac {t^{2}}{\varepsilon }}\log {\frac {t}{\varepsilon }})}n^{O(1)}$ время. ^[9]

Сильно связный подграф Штейнера

Известно, что задача о сильно связном подграфе Штейнера W[1]-трудно параметризуется числом $k$ терминалов: ^[10] а также не допускает $O(\log ^{2-\varepsilon }n)$ -аппроксимация за полиномиальное время (при стандартных предположениях о сложности ). ^[11] Однако 2-приближение можно вычислить в $3^{k}n^{O(1)}$ время. ^[12] Более того, это наилучший вариант, поскольку нет $(2-\varepsilon )$ -аппроксимация может быть вычислена в $f(k)n^{O(1)}$ время для любой функции $f$ в Gap- ETH . ^[13]

k -медиана и k -средние

Для хорошо изученных задач метрической кластеризации k -медианы и k -средних, параметризованных числом $k$ центров, известно, что нет $(1+2/e-\varepsilon )$ -аппроксимация для k-медианы и нет $(1+8/e-\varepsilon )$ -аппроксимация для k-средних может быть вычислена в $f(k)n^{O(1)}$ время для любой функции $f$ в Gap- ETH . ^[14] Существуют соответствующие алгоритмы параметризованной аппроксимации, ^[14] но неизвестно, можно ли вычислить совпадающие аппроксимации за полиномиальное время.

Кластеризация часто рассматривается в условиях малоразмерных данных, и поэтому практически значимая параметризация осуществляется по размерности базовой метрики . В евклидовом пространстве задачи k-Median и k-Means допускают EPAS, параметризованный размерностью $d$ , ^[15]^[16] а также EPAS, параметризованный $k$ . ^[17]^[18] Первый был обобщен до EPAS для параметризации по удвоенному измерению . ^[19] Для слабо связанного параметра размера шоссе только аппроксимационная схема с использованием XP . на сегодняшний день известна ^[20]

к -центр

Для метрической задачи k -центра 2-аппроксимация может быть вычислена за полиномиальное время. Однако при параметризации либо числом $k$ центров, ^[21] удвоенное измерение (фактически измерение манхэттенской метрики ), ^[22] или размер шоссе , ^[21] нет параметризованного $(2-\varepsilon )$ Алгоритм -аппроксимации существует при стандартных предположениях о сложности . Более того, проблема k-центров является W[1]-трудной даже на плоских графах при одновременной параметризации ее числом $k$ центров, размерностью удвоения , размерностью шоссе и шириной пути . ^[23] Однако при объединении $k$ с удвоенным размером существует EPAS, ^[23] то же самое верно и при объединении $k$ с размером шоссе . ^[24] Для более общей версии с пропускной способностью вершин существует EPAS для параметризации по k и размерности удвоения, но не при использовании k и размерности шоссе в качестве параметра. ^[25] Что касается ширины пути, k-Center допускает EPAS даже для более общего параметра ширины дерева , а также для ширины клика . ^[26]

Самый плотный подграф

Вариантом оптимизации задачи k -клики является задача плотного k -подграфа (которая представляет собой 2-арную задачу удовлетворения ограничений ), где задача состоит в том, чтобы найти подграф на $k$ вершинах с максимальным количеством ребер. Нетрудно получить $(k-1)$ -аппроксимация путем простого выбора соответствия размера $k/2$ в данном входном графе, поскольку максимальное количество ребер на $k$ вершинах всегда не превосходит ${k \choose 2}=k(k-1)/2$ . Это также асимптотически оптимально, поскольку при Gap- ETH нет $k^{1-o(1)}$ -аппроксимация может быть вычислена во времени FPT, параметризованном $k$ . ^[27]

Доминирующий набор

Для задачи о доминирующем множестве W[1]-трудно вычислить любое $g(k)$ -аппроксимация в $f(k)n^{O(1)}$ время для любых функций $g$ и $f$ . ^[28]

Приблизительная кернеризация

Кернелизация — это метод, используемый в рамках управляемости с фиксированными параметрами для предварительной обработки экземпляра NP-сложной задачи с целью удаления «легких частей» и выявления NP-сложного ядра экземпляра. Алгоритм кернеризации принимает экземпляр $I$ и параметр $k$ и возвращает новый экземпляр. $I'$ с параметром $k'$ такой, что размер $I'$ и $k'$ ограничен как функция входного параметра $k$ и алгоритм работает за полиномиальное время. Алгоритм $α$ -приближенной кернеризации представляет собой разновидность этого метода, который используется в алгоритмах параметризованной аппроксимации. Он возвращает ядро $I'$ такая, что любое $β$ -приближение в $I'$ может быть преобразовано в $αβ$ -аппроксимацию входного экземпляра $I$ за полиномиальное время. Это понятие было введено Локштановым и др. ^[29] но в литературе есть и другие связанные понятия, такие как ядра Тьюринга. ^[30] и $кернеризация α$ -точности. ^[31]

Что касается регулярных (неприближенных) ядер, то задача допускает алгоритм α-приближенного кернеризации тогда и только тогда, когда она имеет параметризованный алгоритм α-аппроксимации. Доказательство этого факта очень похоже на доказательство для обычных ядер . ^[29] Однако гарантированное приближенное ядро может иметь экспоненциальный размер (или хуже) во входном параметре. Следовательно, становится интересно найти задачи, которые допускают приближенные ядра полиномиального размера. Кроме того, схема приблизительного кернеризации полиномиального размера (PSAKS) представляет собой $α$ -приближенный алгоритм кернеризации, который вычисляет ядро полиномиального размера и для которого $α$ можно установить равным $1+\varepsilon$ для любого $\varepsilon >0$ .

Например, хотя задача Connected Vertex Cover представляет собой FPT, параметризованную размером решения, она не допускает (обычного) ядра полиномиального размера (если только ${\textsf {NP}}\subseteq {\textsf {coNP/poly}}$ ), но ПСАКС существует. ^[29] Аналогично, задача «Дерево Штейнера» представляет собой FPT, параметризованную количеством терминалов, и не допускает ядра полиномиального размера (если только ${\textsf {NP}}\subseteq {\textsf {coNP/poly}}$ ), но ПСАКС существует. ^[29] При параметризации дерева Штейнера количеством нетерминалов в оптимальном решении проблема становится W[2]-сложной (и, следовательно, вообще не допускает точного ядра, если только FPT = W[2]), но все же допускает PSAKS. ^[8]

Беседы о параметризованных приближениях

Ссылки

^ Маркс, Дэниел (2008). «Параметризованная сложность и алгоритмы аппроксимации» . Компьютерный журнал . 51 (1): 60–78. дои : 10.1093/comjnl/bxm048 .
^ Фельдманн, Андреас Эмиль; Картик К.С.; Ли, Ыйун; Мануранси, Пасин (2020). «Обзор аппроксимации параметризованной сложности: жесткость и алгоритмы» . Алгоритмы . 13 (6): 146. arXiv : 2006.04411 . дои : 10.3390/a13060146 . ISSN 1999-4893 . В эту статью включен текст из этого источника, доступного по лицензии CC BY 4.0 .
^ Мануранси, Пасин (2018). «Неаппроксимируемость задач максимальной биклики, минимального k-разреза и плотного по крайней мере k-подграфа из гипотезы расширения малого множества» . Алгоритмы . 11 (1): 10. arXiv : 1705.03581 . дои : 10.3390/a11010010 . ISSN 1999-4893 .
^ Г. Дауни, Родни; Эстивилл-Кастро, Владимир; Ребята, Майкл; Прието, Елена ; Розамунд, Фрэнсис А. (1 апреля 2003 г.). «Разрезать сложно: параметризованная сложность k-разреза и связанные с ним проблемы» . Электронные заметки по теоретической информатике . CATS'03, Вычисления: Австралазийский теоретический симпозиум. 78 : 209–222. дои : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 .
^ Локштанов Даниил; Саураб, Сакет; Сурианараянан, Вайшали (25 апреля 2022 г.). «Схема параметризованной аппроксимации для минимального $k$-Cut» . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . дои : 10.1137/20M1383197 . ISSN 0097-5397 .
^ Дрейфус, SE; Вагнер, Р.А. (1971). «Задача Штейнера в графах» . Сети . 1 (3): 195–207. дои : 10.1002/net.3230010302 .
^ Хлебик, Мирослав; Хлебикова, Янка (31 октября 2008 г.). «Проблема дерева Штейнера на графах: результаты о неаппроксимируемости» . Теоретическая информатика . Алгоритмические аспекты глобальных вычислений. 406 (3): 207–214. дои : 10.1016/j.tcs.2008.06.046 . ISSN 0304-3975 .
^ Перейти обратно: ^а ^б Дворжак, Павел; Фельдманн, Андреас Э.; Кноп, Душан; Масаржик, Томас; Туфар, Томас; Веселый, Павел (1 января 2021 г.). «Параметризованные схемы аппроксимации деревьев Штейнера с малым числом вершин Штейнера» . SIAM Journal по дискретной математике . 35 (1): 546–574. arXiv : 1710.00668 . дои : 10.1137/18M1209489 . ISSN 0895-4801 . S2CID 3581913 .
^ Фельдманн, Андреас Эмиль; Лампис, Майкл (2024). «Параметризованные алгоритмы для леса Штайнера в графах ограниченной ширины». В Брингманне, Карл; Гроэ, Мартин; Кормушки, Габриэле; Свенссон, Ола (ред.). 51-й международный коллоквиум по автоматам, языкам и программированию, ICALP 2024, 8–12 июля 2024 г., Таллинн, Эстония . ЛИПИ. Том 297. Замок Дагштуль - Центр информатики Лейбница. стр. 61:1–61:20. arXiv : 2402.09835 . doi : 10.4230/LIPICS.ICALP.2024.61 .
^ Го, Цзюн; Нидермайер, Рольф; Сухи, Ондржей (1 января 2011 г.). «Параметризованная сложность дуговзвешенных направленных задач Штейнера» . SIAM Journal по дискретной математике . 25 (2): 583–599. дои : 10.1137/100794560 . ISSN 0895-4801 .
^ Гальперин, Эран; Краутгамер, Роберт (9 июня 2003 г.). «Полилогарифмическая неприближаемость» . Материалы тридцать пятого ежегодного симпозиума ACM по теории вычислений . СТОК '03. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 585–594. дои : 10.1145/780542.780628 . ISBN 978-1-58113-674-6 . S2CID 8554166 .
^ Читнис, Раджеш; Хаджиагайи, Мохаммад Таги; Корцарз, Гай (2013). «Алгоритмы фиксированных параметров и аппроксимации: новый взгляд». В Гутин, Григорий; Зейдер, Стефан (ред.). Параметризованный и точный расчет . Конспекты лекций по информатике. Том. 8246. Чам: Springer International Publishing. стр. 110–122. arXiv : 1308.3520 . дои : 10.1007/978-3-319-03898-8_11 . ISBN 978-3-319-03898-8 . S2CID 6796132 .
^ Читнис, Раджеш; Фельдманн, Андреас Эмиль; Мануранси, Пасин (19 апреля 2021 г.). «Алгоритмы параметризованной аппроксимации для задач двунаправленной сети Штейнера» . Транзакции ACM на алгоритмах . 17 (2): 12:1–12:68. arXiv : 1707.06499 . дои : 10.1145/3447584 . ISSN 1549-6325 . S2CID 235372580 .
^ Перейти обратно: ^а ^б Коэн-Аддад, Винсент; Гупта, Анупам; Кумар, Амит; Ли, Ыйун; Ли, Джейсон (2019). Байер, Кристель; Хацигианнакис, Иоаннис; Флоккини, Паола; Леонарди, Стефано (ред.). «Точные аппроксимации FPT для k-медианы и k-средних» . 46-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 2019) . Международные труды Лейбница по информатике (LIPIcs). 132 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi : 10.4230/LIPIcs.ICALP.2019.42 . ISBN 978-3-95977-109-2 . S2CID 139103417 .
^ Коллиопулос, Ставрос Г.; Рао, Сатиш (1999). «Схема аппроксимации почти линейного времени для евклидовой проблемы k-медианы». В Нешетриле, Ярослав (ред.). Алгоритмы - ЕСА'99 . Конспекты лекций по информатике. Том. 1643. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 378–389. дои : 10.1007/3-540-48481-7_33 . ISBN 978-3-540-66251-8 .
^ Коэн-Аддад, Винсент (2018). «Схема быстрой аппроксимации маломерных k-средних». Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2018 года . Слушания. Общество промышленной и прикладной математики. стр. 430–440. arXiv : 1708.07381 . дои : 10.1137/1.9781611975031.29 . ISBN 978-1-61197-503-1 . S2CID 30474859 .
^ Фельдман, Дэн; Монемизаде, Мортеза; Солер, Кристиан (6 июня 2007 г.). «PTAS для кластеризации k-средних на основе слабых базовых наборов» . Материалы двадцать третьего ежегодного симпозиума по вычислительной геометрии - SCG '07 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 11–18. дои : 10.1145/1247069.1247072 . ISBN 978-1-59593-705-6 . S2CID 5694112 .
^ Фельдман, Дэн; Лангберг, Майкл (6 июня 2011 г.). «Единая платформа для аппроксимации и кластеризации данных» . Материалы сорок третьего ежегодного симпозиума ACM по теории вычислений . СТОК '11. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 569–578. дои : 10.1145/1993636.1993712 . ISBN 978-1-4503-0691-1 . S2CID 2677556 .
^ Коэн-Аддад, Винсент; Фельдманн, Андреас Эмиль; Саулпик, Дэвид (31 октября 2021 г.). «Почти линейные схемы аппроксимации времени для кластеризации в удвоенных метриках» . Журнал АКМ . 68 (6): 44:1–44:34. arXiv : 1812.08664 . дои : 10.1145/3477541 . ISSN 0004-5411 . S2CID 240476191 .
^ Фельдманн, Андреас Эмиль; Саулпик, Дэвид (1 декабря 2021 г.). «Схемы аппроксимации полиномиального времени для кластеризации в графах шоссе малой размерности» . Журнал компьютерных и системных наук . 122 : 72–93. дои : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 .
^ Перейти обратно: ^а ^б Фельдманн, Андреас Эмиль (1 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах малых размеров шоссе» . Алгоритмика . 81 (3): 1031–1052. arXiv : 1605.02530 . дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .
^ Федер, Томас; Грин, Дэниел (1 января 1988 г.). «Оптимальные алгоритмы приближенной кластеризации» . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. дои : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 . S2CID 658151 .
^ Перейти обратно: ^а ^б Фельдманн, Андреас Эмиль; Маркс, Даниэль (1 июля 2020 г.). «Параметризованная жесткость задачи k-центра в транспортных сетях» . Алгоритмика . 82 (7): 1989–2005. arXiv : 1802.08563 . дои : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .
^ Беккер, Амария; Кляйн, Филип Н.; Саулпик, Дэвид (2018). Азар, Йоси; Баст, Ханна; Герман, Гжегож (ред.). «Схемы аппроксимации полиномиального времени для маршрутизации k-центра, k-медианы и емкостного транспортного средства в ограниченном измерении шоссе» . 26-й ежегодный европейский симпозиум по алгоритмам (ESA 2018) . Международные труды Лейбница по информатике (LIPIcs). 112 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi : 10.4230/LIPIcs.ESA.2018.8 . ISBN 978-3-95977-081-1 .
^ Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $k$ -центр: различие удвоения и измерения шоссе». В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 13453. Чам: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .
^ Кацикарелис, Иоаннис; Лампис, Майкл; Пашос, Вангелис Т. (15 июля 2019 г.). «Структурные параметры, точные границы и аппроксимация (k, r)-центра» . Дискретная прикладная математика . Комбинаторная оптимизация: между практикой и теорией. 264 : 90–117. arXiv : 1704.08868 . дои : 10.1016/j.dam.2018.11.002 . ISSN 0166-218X .
^ Динур, Ирит; Мануранси, Пасин (2018). Карлин, Анна Р. (ред.). «ETH-твердость аппроксимации 2-CSP и направленной сети Штейнера» . 9-я конференция «Инновации в теоретической информатике» (ITCS 2018) . Международные труды Лейбница по информатике (LIPIcs). 94 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. дои : 10.4230/LIPIcs.ITCS.2018.36 . ISBN 978-3-95977-060-6 . S2CID 4681120 .
^ С., Картик С.; Лаеханукит, Бундит; Мануранси, Пасин (20 июня 2018 г.). «О параметризованной сложности аппроксимации доминирующего множества» . Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2018. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1283–1296. arXiv : 1711.11029 . дои : 10.1145/3188745.3188896 . ISBN 978-1-4503-5559-9 . S2CID 3170316 .
^ Перейти обратно: ^а ^б ^с ^д Локштанов Даниил; Панолан, Фахад; Рамануджан, М.С.; Саураб, Сакет (19 июня 2017 г.). «Кернеризация с потерями» . Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . STOC 2017. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 224–237. дои : 10.1145/3055399.3055456 . ISBN 978-1-4503-4528-6 . S2CID 14599219 .
^ Гермелин, Дэнни; Крач, Стефан; Солтыс, Каролина; Вальстрем, Магнус; У, Си (1 марта 2015 г.). «Теория полноты полиномиальной (Тьюринговой) кернелизации» . Алгоритмика . 71 (3): 702–730. дои : 10.1007/s00453-014-9910-8 . ISSN 1432-0541 . S2CID 253973283 .
^ Товарищи, Майкл Р.; Кулик, Ариэль; Розамонд, Фрэнсис; Шахнай, Хадас (1 мая 2018 г.). «Параметризованная аппроксимация посредством преобразований, сохраняющих точность» . Журнал компьютерных и системных наук . 93 : 30–40. дои : 10.1016/j.jcss.2017.11.001 . ISSN 0022-0000 .

[1] Маркс, Дэниел (2008). «Параметризованная сложность и алгоритмы аппроксимации» . Компьютерный журнал . 51 (1): 60–78. дои : 10.1093/comjnl/bxm048 .

[2] Фельдманн, Андреас Эмиль; Картик К.С.; Ли, Ыйун; Мануранси, Пасин (2020). «Обзор аппроксимации параметризованной сложности: жесткость и алгоритмы» . Алгоритмы . 13 (6): 146. arXiv : 2006.04411 . дои : 10.3390/a13060146 . ISSN 1999-4893 . В эту статью включен текст из этого источника, доступного по лицензии CC BY 4.0 .

[3] Мануранси, Пасин (2018). «Неаппроксимируемость задач максимальной биклики, минимального k-разреза и плотного по крайней мере k-подграфа из гипотезы расширения малого множества» . Алгоритмы . 11 (1): 10. arXiv : 1705.03581 . дои : 10.3390/a11010010 . ISSN 1999-4893 .

[4] Г. Дауни, Родни; Эстивилл-Кастро, Владимир; Ребята, Майкл; Прието, Елена ; Розамунд, Фрэнсис А. (1 апреля 2003 г.). «Разрезать сложно: параметризованная сложность k-разреза и связанные с ним проблемы» . Электронные заметки по теоретической информатике . CATS'03, Вычисления: Австралазийский теоретический симпозиум. 78 : 209–222. дои : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 .

[5] Локштанов Даниил; Саураб, Сакет; Сурианараянан, Вайшали (25 апреля 2022 г.). «Схема параметризованной аппроксимации для минимального $k$-Cut» . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . дои : 10.1137/20M1383197 . ISSN 0097-5397 .

[6] Дрейфус, SE; Вагнер, Р.А. (1971). «Задача Штейнера в графах» . Сети . 1 (3): 195–207. дои : 10.1002/net.3230010302 .

[7] Хлебик, Мирослав; Хлебикова, Янка (31 октября 2008 г.). «Проблема дерева Штейнера на графах: результаты о неаппроксимируемости» . Теоретическая информатика . Алгоритмические аспекты глобальных вычислений. 406 (3): 207–214. дои : 10.1016/j.tcs.2008.06.046 . ISSN 0304-3975 .

[:5-8] Перейти обратно: ^а ^б Дворжак, Павел; Фельдманн, Андреас Э.; Кноп, Душан; Масаржик, Томас; Туфар, Томас; Веселый, Павел (1 января 2021 г.). «Параметризованные схемы аппроксимации деревьев Штейнера с малым числом вершин Штейнера» . SIAM Journal по дискретной математике . 35 (1): 546–574. arXiv : 1710.00668 . дои : 10.1137/18M1209489 . ISSN 0895-4801 . S2CID 3581913 .

[9] Фельдманн, Андреас Эмиль; Лампис, Майкл (2024). «Параметризованные алгоритмы для леса Штайнера в графах ограниченной ширины». В Брингманне, Карл; Гроэ, Мартин; Кормушки, Габриэле; Свенссон, Ола (ред.). 51-й международный коллоквиум по автоматам, языкам и программированию, ICALP 2024, 8–12 июля 2024 г., Таллинн, Эстония . ЛИПИ. Том 297. Замок Дагштуль - Центр информатики Лейбница. стр. 61:1–61:20. arXiv : 2402.09835 . doi : 10.4230/LIPICS.ICALP.2024.61 .

[10] Го, Цзюн; Нидермайер, Рольф; Сухи, Ондржей (1 января 2011 г.). «Параметризованная сложность дуговзвешенных направленных задач Штейнера» . SIAM Journal по дискретной математике . 25 (2): 583–599. дои : 10.1137/100794560 . ISSN 0895-4801 .

[11] Гальперин, Эран; Краутгамер, Роберт (9 июня 2003 г.). «Полилогарифмическая неприближаемость» . Материалы тридцать пятого ежегодного симпозиума ACM по теории вычислений . СТОК '03. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 585–594. дои : 10.1145/780542.780628 . ISBN 978-1-58113-674-6 . S2CID 8554166 .

[12] Читнис, Раджеш; Хаджиагайи, Мохаммад Таги; Корцарз, Гай (2013). «Алгоритмы фиксированных параметров и аппроксимации: новый взгляд». В Гутин, Григорий; Зейдер, Стефан (ред.). Параметризованный и точный расчет . Конспекты лекций по информатике. Том. 8246. Чам: Springer International Publishing. стр. 110–122. arXiv : 1308.3520 . дои : 10.1007/978-3-319-03898-8_11 . ISBN 978-3-319-03898-8 . S2CID 6796132 .

[13] Читнис, Раджеш; Фельдманн, Андреас Эмиль; Мануранси, Пасин (19 апреля 2021 г.). «Алгоритмы параметризованной аппроксимации для задач двунаправленной сети Штейнера» . Транзакции ACM на алгоритмах . 17 (2): 12:1–12:68. arXiv : 1707.06499 . дои : 10.1145/3447584 . ISSN 1549-6325 . S2CID 235372580 .

[:1-14] Перейти обратно: ^а ^б Коэн-Аддад, Винсент; Гупта, Анупам; Кумар, Амит; Ли, Ыйун; Ли, Джейсон (2019). Байер, Кристель; Хацигианнакис, Иоаннис; Флоккини, Паола; Леонарди, Стефано (ред.). «Точные аппроксимации FPT для k-медианы и k-средних» . 46-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 2019) . Международные труды Лейбница по информатике (LIPIcs). 132 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi : 10.4230/LIPIcs.ICALP.2019.42 . ISBN 978-3-95977-109-2 . S2CID 139103417 .

[15] Коллиопулос, Ставрос Г.; Рао, Сатиш (1999). «Схема аппроксимации почти линейного времени для евклидовой проблемы k-медианы». В Нешетриле, Ярослав (ред.). Алгоритмы - ЕСА'99 . Конспекты лекций по информатике. Том. 1643. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 378–389. дои : 10.1007/3-540-48481-7_33 . ISBN 978-3-540-66251-8 .

[16] Коэн-Аддад, Винсент (2018). «Схема быстрой аппроксимации маломерных k-средних». Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2018 года . Слушания. Общество промышленной и прикладной математики. стр. 430–440. arXiv : 1708.07381 . дои : 10.1137/1.9781611975031.29 . ISBN 978-1-61197-503-1 . S2CID 30474859 .

[17] Фельдман, Дэн; Монемизаде, Мортеза; Солер, Кристиан (6 июня 2007 г.). «PTAS для кластеризации k-средних на основе слабых базовых наборов» . Материалы двадцать третьего ежегодного симпозиума по вычислительной геометрии - SCG '07 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 11–18. дои : 10.1145/1247069.1247072 . ISBN 978-1-59593-705-6 . S2CID 5694112 .

[18] Фельдман, Дэн; Лангберг, Майкл (6 июня 2011 г.). «Единая платформа для аппроксимации и кластеризации данных» . Материалы сорок третьего ежегодного симпозиума ACM по теории вычислений . СТОК '11. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 569–578. дои : 10.1145/1993636.1993712 . ISBN 978-1-4503-0691-1 . S2CID 2677556 .

[19] Коэн-Аддад, Винсент; Фельдманн, Андреас Эмиль; Саулпик, Дэвид (31 октября 2021 г.). «Почти линейные схемы аппроксимации времени для кластеризации в удвоенных метриках» . Журнал АКМ . 68 (6): 44:1–44:34. arXiv : 1812.08664 . дои : 10.1145/3477541 . ISSN 0004-5411 . S2CID 240476191 .

[20] Фельдманн, Андреас Эмиль; Саулпик, Дэвид (1 декабря 2021 г.). «Схемы аппроксимации полиномиального времени для кластеризации в графах шоссе малой размерности» . Журнал компьютерных и системных наук . 122 : 72–93. дои : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 .

[:2-21] Перейти обратно: ^а ^б Фельдманн, Андреас Эмиль (1 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах малых размеров шоссе» . Алгоритмика . 81 (3): 1031–1052. arXiv : 1605.02530 . дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .

[22] Федер, Томас; Грин, Дэниел (1 января 1988 г.). «Оптимальные алгоритмы приближенной кластеризации» . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. дои : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 . S2CID 658151 .

[:3-23] Перейти обратно: ^а ^б Фельдманн, Андреас Эмиль; Маркс, Даниэль (1 июля 2020 г.). «Параметризованная жесткость задачи k-центра в транспортных сетях» . Алгоритмика . 82 (7): 1989–2005. arXiv : 1802.08563 . дои : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .

[24] Беккер, Амария; Кляйн, Филип Н.; Саулпик, Дэвид (2018). Азар, Йоси; Баст, Ханна; Герман, Гжегож (ред.). «Схемы аппроксимации полиномиального времени для маршрутизации k-центра, k-медианы и емкостного транспортного средства в ограниченном измерении шоссе» . 26-й ежегодный европейский симпозиум по алгоритмам (ESA 2018) . Международные труды Лейбница по информатике (LIPIcs). 112 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi : 10.4230/LIPIcs.ESA.2018.8 . ISBN 978-3-95977-081-1 .

[25] Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $k$ -центр: различие удвоения и измерения шоссе». В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 13453. Чам: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

[:4-26] Кацикарелис, Иоаннис; Лампис, Майкл; Пашос, Вангелис Т. (15 июля 2019 г.). «Структурные параметры, точные границы и аппроксимация (k, r)-центра» . Дискретная прикладная математика . Комбинаторная оптимизация: между практикой и теорией. 264 : 90–117. arXiv : 1704.08868 . дои : 10.1016/j.dam.2018.11.002 . ISSN 0166-218X .

[27] Динур, Ирит; Мануранси, Пасин (2018). Карлин, Анна Р. (ред.). «ETH-твердость аппроксимации 2-CSP и направленной сети Штейнера» . 9-я конференция «Инновации в теоретической информатике» (ITCS 2018) . Международные труды Лейбница по информатике (LIPIcs). 94 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. дои : 10.4230/LIPIcs.ITCS.2018.36 . ISBN 978-3-95977-060-6 . S2CID 4681120 .

[28] С., Картик С.; Лаеханукит, Бундит; Мануранси, Пасин (20 июня 2018 г.). «О параметризованной сложности аппроксимации доминирующего множества» . Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2018. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1283–1296. arXiv : 1711.11029 . дои : 10.1145/3188745.3188896 . ISBN 978-1-4503-5559-9 . S2CID 3170316 .

[:0-29] Перейти обратно: ^а ^б ^с ^д Локштанов Даниил; Панолан, Фахад; Рамануджан, М.С.; Саураб, Сакет (19 июня 2017 г.). «Кернеризация с потерями» . Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . STOC 2017. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 224–237. дои : 10.1145/3055399.3055456 . ISBN 978-1-4503-4528-6 . S2CID 14599219 .

[30] Гермелин, Дэнни; Крач, Стефан; Солтыс, Каролина; Вальстрем, Магнус; У, Си (1 марта 2015 г.). «Теория полноты полиномиальной (Тьюринговой) кернелизации» . Алгоритмика . 71 (3): 702–730. дои : 10.1007/s00453-014-9910-8 . ISSN 1432-0541 . S2CID 253973283 .

[31] Товарищи, Майкл Р.; Кулик, Ариэль; Розамонд, Фрэнсис; Шахнай, Хадас (1 мая 2018 г.). «Параметризованная аппроксимация посредством преобразований, сохраняющих точность» . Журнал компьютерных и системных наук . 93 : 30–40. дои : 10.1016/j.jcss.2017.11.001 . ISSN 0022-0000 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]