Полностью полиномиальная схема аппроксимации

Полностью полиномиальная схема аппроксимации (FPTAS) — это алгоритм для поиска приближенных решений функциональных задач , особенно задач оптимизации . FPTAS принимает в качестве входных данных экземпляр задачи и параметр ε > 0. В качестве выходных данных он возвращает значение, которое по крайней мере в раз больше правильного значения, а в большинстве раз больше правильного значения. ${\displaystyle 1-\varepsilon }$ ${\displaystyle 1+\varepsilon }$

В контексте задач оптимизации правильное значение понимается как значение оптимального решения, и часто подразумевается, что FPTAS должен выдавать допустимое решение (а не просто значение решения). Возврат значения и нахождение решения с этим значением эквивалентны, если предположить, что задача обладает самосводимостью .

Важно отметить, что время выполнения FPTAS полиномиально по размеру задачи и по 1/ε. Это отличается от общей схемы аппроксимации полиномиального времени (PTAS). Время выполнения общей PTAS полиномиально по размеру задачи для каждого конкретного ε, но может быть экспоненциальным по 1/ε. ^[1]

Термин FPTAS может также использоваться для обозначения класса задач, имеющих FPTAS. FPTAS является подмножеством PTAS, и если P = NP , то это строгое подмножество. ^[2]

Связь с другими классами сложности

Все проблемы в FPTAS решаются с фиксированными параметрами относительно стандартной параметризации. ^[3]

Любая сильно NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS, если P=NP. ^[4] Однако обратное утверждение неверно: например, если P не равно NP, рюкзак с двумя ограничениями не является сильно NP-трудной задачей, но не имеет FPTAS, даже если оптимальная целевая функция полиномиально ограничена. ^[5]

Преобразование динамической программы в FPTAS

Вёгингер ^[6] представил общую схему преобразования определенного класса динамических программ в FPTAS.

Вход

Схема решает задачи оптимизации, в которых входные данные определяются следующим образом:

• Входные данные состоят из n векторов, x ₁ ,..., x _n .
• Каждый входной вектор состоит из некоторых неотрицательных целых чисел, где может зависеть от входных данных. ${\displaystyle a}$ ${\displaystyle a}$
• Все компоненты входных векторов кодируются в двоичном виде. Таким образом, размер задачи составляет O( n +log( X )), где X — сумма всех компонентов во всех векторах.

Очень простая динамическая программа

Предполагается, что задача имеет алгоритм динамического программирования (DP), использующий состояния . Каждое состояние представляет собой вектор, состоящий из некоторых неотрицательных целых чисел, где не зависит от входа. DP работает за n шагов. На каждом шаге i он обрабатывает вход x _i и создает набор состояний S _i . Каждое состояние кодирует частичное решение задачи, используя входы x ₁ ,..., x _i . Компоненты DP следующие: ${\displaystyle b}$ ${\displaystyle b}$

• Множество S ₀ начальных состояний .
• Набор функций перехода F. Каждая функция f в F отображает пару (состояние, вход) в новое состояние.
• Целевая функция g, сопоставляющая состояние с его значением.

Алгоритм DP:

• Пусть S ₀  := множество начальных состояний.
• Для k = 1 до n выполните:
  • Пусть S _k  := { f ( s , x _k ) | f в F , s в S _{k −1} }
• Выход мин/макс {g(s) | s в S _n }.

Время выполнения DP линейно зависит от количества возможных состояний. В общем случае это число может быть экспоненциальным по размеру входной задачи: оно может быть в O( n V ^b ), где V — наибольшее целое число, которое может появиться в состоянии. Если V находится в O( X ), то время выполнения находится в O( n X ^b ), что является всего лишь псевдополиномиальным временем , поскольку оно экспоненциально по размеру задачи, который находится в O(log X ).

Способ сделать его полиномиальным — это обрезать пространство состояний : вместо того, чтобы сохранять все возможные состояния на каждом шаге, сохранить только подмножество состояний; удалить состояния, которые «достаточно близки» к другим состояниям. При определенных условиях это обрезание можно выполнить таким образом, чтобы не слишком сильно изменить объективное значение.

Чтобы формализовать это, предположим, что рассматриваемая задача имеет неотрицательный целочисленный вектор d = ( d ₁ ,..., d _b ), называемый вектором степени задачи. Для каждого действительного числа r >1 мы говорим, что два вектора состояния s ₁ , s ₂ являются (d,r)-близкими , если для каждой координаты j из 1,..., b : (в частности, если d _j =0 для некоторого j , то ). ${\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}$ ${\displaystyle s_{1,j}=s_{2,j}}$

Проблема называется чрезвычайно благожелательной, если она удовлетворяет следующим трём условиям:

1. Близость сохраняется с помощью функций перехода : для любого r > 1, для любой функции перехода f в F , для любого входного вектора x и для любых двух векторов состояния s ₁ , s ₂ выполняется следующее: если s ₁ является ( d,r )-близким к s ₂ , то f ( s ₁ , x ) является ( d,r )-близким к f ( s ₂ ,x ).
   • Достаточное условие для этого можно проверить следующим образом. Для каждой функции f ( s , x ) из F и для каждой координаты j из 1,..., b обозначим через f _j (s,x) j -ю координату f . Эту f _j можно рассматривать как целочисленную функцию от b + a переменных. Предположим, что каждая такая f _j является многочленом с неотрицательными коэффициентами. Преобразуем ее в многочлен от одной переменной z , подставив s =(z ^d1 ,...,z ^db ) и x =(1,...,1). Если степень полученного многочлена по z не превышает d _j , то условие 1 выполнено.
2. Близость сохраняется функцией ценности : существует целое число G ≥ 0 (которое является функцией функции ценности g и вектора степени d ), такое, что для любого r > 1 и для любых двух векторов состояния s ₁ , s ₂ выполняется следующее: если s ₁ ( d,r )-близок к s ₂ , то: g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (в задачах минимизации); g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (в задачах максимизации).
   • Достаточным условием для этого является то, что функция g является полиномиальной функцией (от b переменных) с неотрицательными коэффициентами.
3. Технические условия :
   • Все функции перехода f в F и функция значения g могут быть вычислены в поливремени.
   • Число | F | функций перехода является полиномом по n и log( X ).
   • Множество S ₀ начальных состояний можно вычислить за время, полиномиальное по n и log( X ).
   • Пусть V _j будет множеством всех значений, которые могут появиться в координате j в состоянии. Тогда ln каждого значения в V _j не превышает полинома P ₁ (n,log(X)).
   • Если d _j =0, то мощность V _j не превышает полинома P ₂ ( n ,log( X )).

Для каждой чрезвычайно благожелательной проблемы динамическая программа может быть преобразована в FPTAS. Определите:

• ${\displaystyle \epsilon }$ := требуемый коэффициент аппроксимации.
• ${\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}$, где G — константа из условия 2. Обратите внимание, что . ${\displaystyle {\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}$
• ${\displaystyle L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil }$, где P ₁ — многочлен из условия 3 (верхняя граница ln каждого значения, которое может появиться в векторе состояния). Обратите внимание, что , поэтому он является многочленом по размеру входа и по . Кроме того, , поэтому по определению P ₁ каждое целое число, которое может появиться в векторе состояния, находится в диапазоне [0, r ^L ]. ${\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil }$ ${\displaystyle 1/\epsilon }$ ${\displaystyle r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}}$
• Разобьем диапазон [0, r ^L ] на L +1 r -интервалов: . ${\displaystyle I_{0}=[0];I_{1}=[1,r);I_{2}=[r,r^{2});\ldots ;I_{L}=[r^{L-1},r^{L}]}$
• Разобьем пространство состояний на r-ячейки : каждая координата k со степенью d _k ≥ 1 разобьем на L +1 интервалов выше; каждая координата с d _k = 0 разобьем на P ₂ ( n ,log( X )) одноэлементных интервалов — интервал для каждого возможного значения координаты k (где P ₂ — многочлен из условия 3 выше).
  • Обратите внимание, что каждое возможное состояние содержится ровно в одном r -ящике; если два состояния находятся в одном и том же r -ящике, то они ( d , r )-близки.
• ${\displaystyle R:=(L+1+P_{2}(n,\log {X}))^{b}}$.
  • Обратите внимание, что количество r -боксов не превышает R. Поскольку b — фиксированная константа, R является полиномом по размеру входных данных и по . ${\displaystyle 1/\epsilon }$

FPTAS работает аналогично DP, но на каждом шаге он обрезает набор состояний до меньшего набора T _k , который содержит ровно одно состояние в каждом r -box. Алгоритм FPTAS таков:

• Пусть T ₀  := S ₀ = множество начальных состояний.
• Для k = 1 до n выполните:
  • Пусть U _k  := { f ( s , x _k ) | f в F , s в T _{k −1} }
  • Пусть T _k  := обрезанная копия U _k : для каждого r -ящика, содержащего одно или несколько состояний U _k , сохраним ровно одно состояние в T _k .
• Выход мин/макс {g(s) | s в T _n }.

Время выполнения FPTAS полиномиально относительно общего числа возможных состояний в каждом T _i , что не больше общего числа r -блоков, что не больше R , что полиномиально относительно n , log( X ) и . ${\displaystyle 1/\epsilon }$

Обратите внимание, что для каждого состояния s _u в U _k его подмножество T _{k содержит} по крайней мере одно состояние s _t , которое (d,r)-близко к s _u . Кроме того, каждое U _k является подмножеством Sk в исходном (необрезанном) DP. Основная лемма для доказательства корректности FPTAS: ^{[6] : Лем.3.3}

_Для каждого шага k в 0,..., n , для каждого состояния s _s в Sk существует состояние s _t в T _{k ,} которое ( d , r ^k )-близко к s _s .

Доказательство проводится индукцией по k . Для k = 0 имеем T _k = S _k ; каждое состояние ( d , 1 )-близко к себе. Предположим, что лемма верна для k -1. Для каждого состояния s _s в S _k пусть s _s- будет одним из его предшественников в S _k-1 , так что f ( s _{s −} , x )= s _s . По предположению индукции существует состояние s _t- в T _k-1 , которое ( d , r ^k-1 )-близко к s _{s −} . Поскольку близость сохраняется переходами (Условие 1 выше), f ( s _{t −} , x ) является ( d , r ^k-1 )-близко к f ( s _{s −} , x )= s _s . Это f ( s _{t −} , x ) находится в U _k . После обрезки в T _k есть состояние s _{t ,} которое ( d , r )-близко к f(s _t- ,x) . Это s _t является ( d , r ^k )-близким к s _s .

Рассмотрим теперь состояние s ^* в S _n , которое соответствует оптимальному решению (то есть g ( s* )=OPT). По лемме выше существует состояние t * в T _n , которое ( d , r ⁿ )-близко к s ^* . Поскольку близость сохраняется функцией ценности, g (t*) ≥ r ^(-Gn) · g ( s* ) для задачи максимизации. По определению r , . Итак . Аналогичное рассуждение работает для задачи минимизации. ${\displaystyle r^{-Gn}\geq (1-\epsilon )}$ ${\displaystyle g(t^{*})\geq (1-\epsilon )\cdot OPT}$

Примеры

Вот несколько примеров чрезвычайно доброжелательных задач, которые имеют FPTAS согласно приведенной выше теореме. ^[6]

1. Многоканальное разбиение чисел (эквивалентно, планирование идентичных машин ) с целью минимизации наибольшей суммы является чрезвычайно благожелательным. Здесь у нас есть a = 1 (входные данные являются целыми числами), а b = количество ячеек (которое считается фиксированным). Каждое состояние является вектором из b целых чисел, представляющих суммы b ячеек. Имеется b функций: каждая функция j представляет вставку следующего ввода в ячейку j . Функция g ( s ) выбирает наибольший элемент s . S ₀ = {(0,...,0)}. Условия для чрезвычайной благожелательности выполняются при векторе степени d = (1,...,1) и G = 1. Результат распространяется на планирование однородных машин и планирование не связанных машин , когда количество машин фиксировано (это необходимо, поскольку R - количество r -ящиков - экспоненциально по b ). Обозначается Pm|| или Qm|| или Rm|| . ${\displaystyle \max C_{j}}$ ${\displaystyle \max C_{j}}$ ${\displaystyle \max C_{j}}$

• Примечание : рассмотрим особый случай b = 2, где цель состоит в минимизации квадрата разности между двумя суммами частей. Можно использовать тот же DP, но на этот раз с функцией значения g ( s ) = ( s ₁ - s ₂ ) ² . Теперь условие 2 нарушается: состояния ( s ₁ , s ₁ ) и ( s ₁ , s ₂ ) могут быть ( d,r )-близкими, но g ( s ₁ , s ₁ ) = 0, в то время как g ( s ₁ , s ₂ ) > 0. поэтому приведенную выше теорему нельзя применить. Действительно, задача не имеет FPTAS, если P = NP, поскольку FPTAS можно было бы использовать для решения в поливремени, является ли оптимальное значение 0.

2. Сумма кубов времени выполнения работы на любом фиксированном числе идентичных или однородных машин (последнее обозначается Qm|| ) является ex-благоприятной с a = 1, b = 3, d = (1, 1, 3). Она может быть расширена до любой фиксированной степени времени выполнения. ${\displaystyle \sum C_{j}^{3}}$

3. Сумма взвешенного времени завершения на любом фиксированном числе идентичных или однородных машин — последняя обозначается Qm|| . ${\displaystyle \sum w_{j}C_{j}}$

4. Сумма времени завершения на любом фиксированном количестве идентичных или однородных машин с зависящим от времени временем обработки: Qm|time-dep| . Это справедливо даже для взвешенной суммы времени завершения. ${\displaystyle \sum C_{j}}$

5. Взвешенное раннее-запаздывание относительно общей даты выполнения на любом фиксированном количестве машин: m|| . ${\displaystyle \sum w_{j}|C_{j}|}$

Простая динамическая программа

Простые динамические программы добавляют к приведенной выше формуле следующие компоненты:

• Набор H функций фильтрации , той же мощности, что и F. Каждая функция h _i в H отображает пару (состояние,вход) в булево значение. Значение должно быть "истинным" тогда и только тогда, когда активация перехода f _i на этой паре приведет к допустимому состоянию.
• Отношение доминирования , которое представляет собой частичный порядок по состояниям (безразличия отсутствуют, не все пары сравнимы), и отношение квазидоминирования , которое представляет собой полный предпорядок по состояниям (безразличия допускаются, все пары сравнимы).

Исходный DP изменен следующим образом:

• Пусть S ₀  := множество начальных состояний.
• Для k = 1 до n выполните:
  • Пусть S _k  := { f _j ( s , x _k ) | f _j in F , s in S _{k −1} , h _j ( s , x _k )=True }, где h _j — функция фильтра, соответствующая функции перехода f _j .
• Выход мин/макс {g(s) | s в S _n }.

Проблема называется благожелательной, если она удовлетворяет следующим условиям (которые расширяют условия 1, 2, 3 выше):

1. Близость сохраняется с помощью функций перехода : для любого r > 1, для любой функции перехода f в F , для любого входного вектора x и для любых двух векторов состояния s ₁ , s ₂ выполняется следующее:
   • если s ₁ ( d,r )-близок к s ₂ , и s ₁ квазидоминирует над s ₂ , то либо (a) f ( s ₁ , x ) ( d,r )-близок к f ( s ₂ ,x ), и f ( s ₁ , x ) квазидоминирует над f ( s ₂ ,x ) , либо (b) f ( s ₁ , x ) доминирует над f ( s ₂ ,x ).
   • если s ₁ доминирует над s ₂ , то f ( s ₁ , x ) доминирует над f ( s ₂ ,x ).
2. Близость сохраняется функцией значения: существует целое число G ≥ 0 (функция функции значения g и вектора степени d ), такое, что для любого r >1 и для любых двух векторов состояния s ₁ , s ₂ выполняется следующее:
   • если s ₁ ( d,r )-близок к s ₂ , и s ₁ квазидоминирует над s ₂ , то: g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (в задачах минимизации); g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (в задачах максимизации).
   • если s ₁ доминирует над s ₂ , то g ( s ₁ ) ≤ g ( s ₂ ) (в задачах минимизации); g ( s ₁ ) ≥ g ( s ₂ ) (в задачах максимизации).
3. Технические условия (в дополнение к вышеперечисленным):
   • Отношение квазидоминирования может быть определено за полиномиальное время.
4. Условия на функции фильтра : для любого r > 1, для любой функции фильтра h в H , для любого входного вектора x и для любых двух векторов состояния s ₁ , s ₂ выполняется следующее:
   • если s ₁ ( d,r )-близок к s ₂ , и s ₁ квазидоминирует над s ₂ , то h ( s ₁ , x ) ≥ h ( s ₂ , x ) .
   • если s ₁ доминирует над s ₂ , то h ( s ₁ , x ) ≥ h ( s ₂ , x ).

Для каждой благожелательной проблемы динамическую программу можно преобразовать в FPTAS аналогично приведенной выше, с двумя изменениями (выделены жирным шрифтом):

• Пусть T ₀  := S ₀ = множество начальных состояний.
• Для k = 1 до n выполните:
  • Пусть U _k  := { f _j ( s , x _k ) | f _j in F , s in T _{k −1} , h _j ( s , x _k )=True }, где h _j — функция фильтра, соответствующая функции перехода f _j .
  • Пусть T _k  := обрезанная копия U _k : для каждого r -ящика, содержащего одно или несколько состояний U _k , выберем один элемент , который квазидоминирует над всеми остальными элементами в U _k , и вставим его в T _k .
• Выход мин/макс {g(s) | s в T _n }.

Примеры

Вот несколько примеров доброжелательных задач, которые имеют FPTAS согласно приведенной выше теореме. ^[6]

1. Задача о рюкзаке 0-1 является благожелательной. Здесь у нас есть a = 2: каждый вход является 2-вектором (вес, значение). Есть DP с b = 2: каждое состояние кодирует (текущий вес, текущее значение). Есть две функции перехода: f ₁ соответствует добавлению следующего элемента входа, а f ₂ соответствует его отсутствию. Соответствующие функции фильтра: h ₁ проверяет, что вес со следующим элементом входа не превышает вместимости рюкзака; h ₂ всегда возвращает True. Функция значения g ( s ) возвращает s ₂ . Начальный набор состояний равен {(0,0)}. Вектор степени равен (1,1). Отношение доминирования тривиально. Отношение квазидоминирования сравнивает только координату веса: s квазидоминирует над t тогда и только тогда, когда s ₁ ≤ t ₁ . Следствием этого является то, что если состояние t имеет больший вес, чем состояние s , то функциям перехода разрешено не сохранять близость между t и s (например, возможно, что s имеет преемника, а t не имеет соответствующего преемника). Похожий алгоритм был представлен ранее Ибаррой и Кимом. ^[7] Время выполнения этого FPTAS может быть улучшено до операций с целыми числами. ^[8] Экспонента была позже улучшена до 2,5. ^[9] ${\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}$

• Примечание : рассмотрим задачу о рюкзаке с 2 весами , где каждый элемент имеет два веса и значение, и цель состоит в том, чтобы максимизировать значение таким образом, чтобы сумма квадратов общих весов была не больше вместимости рюкзака: . Мы могли бы решить ее, используя похожую DP, где каждое состояние равно (текущий вес 1, текущий вес 2, значение). Отношение квазидоминирования следует изменить так: s квазидоминирует t тогда и только тогда, когда ( s ₁ ² + s ₂ ² ) ≤ ( t ₁ ² + t ₂ ² ). Но это нарушает Условие 1 выше: квазидоминирование не сохраняется функциями перехода [например, состояние (2,2,..) квазидоминирует (1,3,..); но после добавления входа (2,0,..) к обоим состояниям результат (4,2,..) не квазидоминирует (3,3,..)]. Поэтому теорему использовать нельзя. Действительно, эта задача не имеет FPTAS, если P=NP. То же самое верно для двумерной задачи о рюкзаке. То же самое верно для задачи о сумме нескольких подмножеств : отношение квазидоминирования должно быть: s квазидоминирует над t тогда и только тогда, когда max( s _1, s ₂ ) ≤ max( t _1, t ₂ ), но оно не сохраняется при переходах, по тому же примеру, что и выше. ${\displaystyle \left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W}$

2. Минимизация взвешенного числа запаздывающих заданий или максимизация взвешенного числа преждевременных заданий на одной машине; обозначается 1|| . ${\displaystyle \sum w_{j}U_{j}}$

3. Пакетное планирование для минимизации взвешенного числа запаздывающих заданий: 1|партия| . ${\displaystyle \sum w_{j}U_{j}}$

4. Продолжительность ухудшающихся работ на одной машине: 1|ухудшение| . ${\displaystyle \max C_{j}}$

5. Общее количество просроченной работы на одной машине: 1|| . ${\displaystyle \sum V_{j}}$

6. Общая взвешенная задержка работы на одной машине: 1|| . ${\displaystyle \sum w_{j}V_{j}}$

Не примеры

Несмотря на общность приведенного выше результата, существуют случаи, в которых его невозможно использовать.

1. В задаче о полном запаздывании 1|| формулировка динамического программирования Лоулера ^[10] требует обновления всех состояний в старом пространстве состояний несколько раз B раз, где B имеет порядок X (максимальный размер входных данных). То же самое справедливо для DP для экономичного определения размера партии. ^[11] В этих случаях число функций перехода в F равно B , что экспоненциально в log( X ), поэтому второе техническое условие нарушается. Метод усечения состояний бесполезен, но для разработки FPTAS использовался другой метод — округление входных данных. ^{[12] [13]} ${\displaystyle \sum T_{j}}$

2. В задаче минимизации дисперсии 1|| целевая функция равна , что нарушает Условие 2, поэтому теорема не может быть использована. Но для разработки FPTAS использовались различные методы. ^{[14] [15]} ${\displaystyle CTV}$ ${\displaystyle g(s)=s_{5}-(s_{4}-s_{3})^{2}/n}$

FPTAS для аппроксимации действительных чисел

Другой тип задач, в которых FPTAS может быть полезен, — это поиск рациональных чисел, которые аппроксимируют некоторые действительные числа. Например, рассмотрим бесконечный ряд . Сумма является иррациональным числом . Чтобы аппроксимировать ее рациональным числом, мы можем вычислить сумму первых k элементов для некоторого конечного k . Можно показать, что ошибка в аппроксимации составляет около . Следовательно, чтобы получить ошибку ε, нам нужно около элементов, так что это FPTAS. Обратите внимание, что эта конкретная сумма может быть представлена ​​другой суммой, в которой требуется только O(log(ε)) элементов, поэтому сумма фактически может быть аппроксимирована за полиномиальное время в длине кодирования ε. ^{[16] : 35, Sec.1} ${\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i^{3}}}}$ ${\displaystyle {\frac {1}{2k^{2}}}}$ ${\displaystyle {\sqrt {\frac {1}{2\epsilon }}}}$

Некоторые другие проблемы, имеющие FPTAS

• Задача о рюкзаке , ^{[17] [18],} а также некоторые ее варианты:
  • Задача о рюкзаке 0-1. ^[19]
  • Неограниченная задача о рюкзаке. ^[20]
  • Многомерная задача о рюкзаке с дельта-модулярными ограничениями. ^[21]
  • Многокритериальная задача о рюкзаке 0-1. ^[22]
  • Параметрическая задача о рюкзаке. ^[23]
  • Симметричная квадратичная задача о рюкзаке. ^[24]
• Count-subset-sum (# SubsetSum ) — нахождение количества различных подмножеств с суммой не более C . ^[25]
• Ограниченный кратчайший путь : нахождение пути с минимальной стоимостью между двумя узлами в графе с учетом ограничения задержки. ^[26]
• Кратчайшие пути и нелинейные цели. ^[27]
• Подсчет краев-крышек . ^[28]
• Задача поиска подмножества векторов, где размерность фиксирована. ^[29]

Смотрите также

• «Доброжелательные динамические программы», которые допускают FPTAS, также допускают эволюционный алгоритм. ^[30]

Ссылки

1. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela и M. Protasi. Сложность и аппроксимация: комбинаторные задачи оптимизации и их аппроксимативные свойства , Springer-Verlag, 1999.
2. Янсен, Томас (1998), «Введение в теорию сложности и алгоритмы аппроксимации», в Mayr, Эрнст В.; Премель, Ханс Юрген; Штегер, Ангелика (ред.), Лекции по проверке доказательств и алгоритмам аппроксимации , Lecture Notes in Computer Science, т. 1367, Springer, стр. 5–28, doi :10.1007/BFb0053011, ISBN 9783540642015. См. обсуждение после Определения 1.30 на стр. 20.
3. Cai, Liming; Chen, Jianer (июнь 1997). «О трактуемости и аппроксимируемости задач оптимизации NP с фиксированными параметрами». Журнал компьютерных и системных наук . 54 (3): 465–474. doi : 10.1006/jcss.1997.1490 .
4. Вазирани, Виджай В. (2003). Алгоритмы аппроксимации . Берлин: Шпрингер. Следствие 8.6. ISBN 3-540-65367-8.
5. Х. Келлерер; У. Пферши; Д. Пизингер (2004). Задачи о ранце . Springer. Теорема 9.4.1.
6. Woeginger, Gerhard J. (2000-02-01). «Когда динамическая программная формулировка гарантирует существование полностью полиномиальной схемы аппроксимации времени (FPTAS)?». INFORMS Journal on Computing . 12 (1): 57–74. doi :10.1287/ijoc.12.1.57.11901. ISSN  1091-9856.
7. Ибарра, Оскар Х.; Ким, Чул Э. (1975-10-01). «Быстрые алгоритмы аппроксимации для задач о ранце и сумме подмножеств». Журнал ACM . 22 (4): 463–468. doi : 10.1145/321906.321909 . ISSN  0004-5411. S2CID  14619586.
8. Лоулер, Юджин Л. (1 ноября 1979 г.). «Быстрые аппроксимационные алгоритмы для задач о ранце». Математика исследования операций . 4 (4): 339–356. doi :10.1287/moor.4.4.339. ISSN  0364-765X. S2CID  7655435.
9. Ри, Донгук (2015). Более быстрые полностью полиномиальные схемы аппроксимации для задач о ранце (диссертация). Массачусетский технологический институт. hdl :1721.1/98564.
10. Лоулер, Юджин Л. (1977-01-01), Хаммер, ПЛ; Джонсон, ЕЛ; Корте, БХ; Немхаузер, GL (ред.), "Псевдополиномиальный" алгоритм упорядочивания заданий для минимизации общего опоздания**Исследование поддержано грантом Национального научного фонда GJ-43227X", Анналы дискретной математики , Исследования по целочисленному программированию, т. 1, Elsevier, стр. 331–342, doi :10.1016/S0167-5060(08)70742-8 , получено 17 декабря 2021 г.
11. Флориан, М.; Ленстра, Дж. К.; Ринной Кан, АХГ (1980-07-01). «Детерминированное планирование производства: алгоритмы и сложность». Management Science . 26 (7): 669–679. doi :10.1287/mnsc.26.7.669. ISSN  0025-1909.
12. Лоулер, Э. Л. (1982-12-01). «Полностью полиномиальная схема аппроксимации для проблемы тотального опозданий». Operations Research Letters . 1 (6): 207–208. doi :10.1016/0167-6377(82)90022-0. ISSN  0167-6377.
13. Ван Хоесел, CPM; Вагельманс, APM (2001). «Полностью полиномиальные аппроксимационные схемы для задач экономичного определения размера партии с одним элементом». Математика исследования операций . 26 (2): 339–357. doi :10.1287/moor.26.2.339.10552.
14. Cai, X. (1995-09-21). «Минимизация согласованно взвешенной дисперсии в системах с одной машиной». Европейский журнал операционных исследований . 85 (3): 576–592. doi :10.1016/0377-2217(93)E0367-7. ISSN  0377-2217.
15. Woeginger, Gerhard J. (1999-05-01). «Аппроксимационная схема для минимизации приемлемо взвешенной дисперсии на одной машине». INFORMS Journal on Computing . 11 (2): 211–216. doi :10.1287/ijoc.11.2.211. ISSN  1091-9856.
16. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419
17. Вазирани, Виджай (2001). Алгоритмы аппроксимации . Берлин: Springer. С. 69–70. ISBN 3540653678. OCLC  47097680.
18. Келлерер, Ганс; Пферши, Ульрих (2004-03-01). «Улучшенное динамическое программирование в связи с FPTAS для задачи о ранце». Журнал комбинаторной оптимизации . 8 (1): 5–11. doi :10.1023/B:JOCO.0000021934.29833.6b. ISSN  1573-2886. S2CID  36474745.
19. Джин, Се (2019). Улучшенный FPTAS для ранца 0-1 . Международные труды Лейбница по информатике (LIPIcs). Том. 132. Замок Дагштуль – Центр информатики Лейбница. стр. 76:1–76:14. arXiv : 1904.09562 . doi : 10.4230/LIPIcs.ICALP.2019.76 . ISBN 9783959771092. S2CID  128317990.
20. Янсен, Клаус; Крафт, Стефан Э.Дж. (2018-02-01). «Быстрее FPTAS для задачи о неограниченном рюкзаке». Европейский журнал комбинаторики . Комбинаторные алгоритмы, посвящается памяти Мирки Миллер. 68 : 148–174. arXiv : 1504.04650 . doi :10.1016/j.ejc.2017.07.016. ISSN  0195-6698. S2CID  9557898.
21. Грибанов, ДВ (2021-05-10). "FPTAS для $$\var Delta $$-Modular Multidimensional Knapsack Problem". Математическая теория оптимизации и исследование операций . Конспект лекций по информатике. Том 12755. С. 79–95. arXiv : 2103.07257 . doi :10.1007/978-3-030-77876-7_6. ISBN 978-3-030-77875-0. S2CID  232222954.
22. Базган, Кристина; Хьюго, Хадриан; Вандерпутен, Дэниел (2009-10-01). «Реализация эффективной fptas для многоцелевой задачи о рюкзаке 0–1». Европейский журнал операционных исследований . 198 (1): 47–56. doi :10.1016/j.ejor.2008.07.047. ISSN  0377-2217.
23. Хольцхаузер, Михаэль; Крумке, Свен О. (2017-10-01). «FPTAS для параметрической задачи о ранце». Information Processing Letters . 126 : 43–47. arXiv : 1701.07822 . doi :10.1016/j.ipl.2017.06.006. ISSN  0020-0190. S2CID  1013794.
24. Сюй, Чжоу (2012-04-16). «Сильно полиномиальный FPTAS для симметричной квадратичной задачи о рюкзаке». European Journal of Operational Research . 218 (2): 377–381. doi :10.1016/j.ejor.2011.10.049. hdl : 10397/24376 . ISSN  0377-2217.
25. Гопалан, Парикшит; Кливанс, Адам; Мека, Рагху; Штефанкович, Даниэль; Вемпала, Сантош; Вигода, Эрик (2011-10-01). "FPTAS для #Knapsack и связанных с ним задач подсчета". IEEE 52-й ежегодный симпозиум по основам компьютерной науки 2011 г. стр. 817–826. doi :10.1109/FOCS.2011.32. ISBN 978-0-7695-4571-4. S2CID  5691574.
26. Эргун, Фунда ; Синха, Ракеш; Чжан, Лиза (15.09.2002). «Улучшенный FPTAS для ограниченного кратчайшего пути». Information Processing Letters . 83 (5): 287–291. doi :10.1016/S0020-0190(02)00205-3. ISSN  0020-0190.
27. Цаггурис, Джордж; Заролиагис, Христос (2009-06-01). «Многоцелевая оптимизация: улучшенная FPTAS для кратчайших путей и нелинейных целей с приложениями». Теория вычислительных систем . 45 (1): 162–186. doi :10.1007/s00224-007-9096-4. ISSN  1433-0490. S2CID  13010023.
28. Линь, Чэнъюй; Лю, Цзинчэн; Лу, Пиньян (2013-12-18), "Простой FPTAS для подсчета рёберных покрытий", Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2014 года , Труды, Общество промышленной и прикладной математики, стр. 341–348, arXiv : 1309.6115 , doi : 10.1137/1.9781611973402.25, ISBN 978-1-61197-338-9, S2CID  14598468 , получено 2021-12-13
29. Кельманов, А.В.; Романченко, С.М. (01.07.2014). «FPTAS для задачи поиска подмножества векторов». Журнал прикладной и промышленной математики . 8 (3): 329–336. дои : 10.1134/S1990478914030041. ISSN  1990-4797. S2CID  96437935.
30. Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07). "Эволюционные алгоритмы и динамическое программирование". Theoretical Computer Science . 412 (43): 6020–6035. arXiv : 1301.4096 . doi : 10.1016/j.tcs.2011.07.024 . ISSN  0304-3975.

Внешние ссылки

• Зоопарк сложности: FPTAS