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

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

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

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

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

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

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

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

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

Фёгингер представил общую схему преобразования определенного класса динамических программ в ФПТАС.

Вход

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

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

Чрезвычайно простая динамическая программа

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

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

Алгоритм ДП такой:

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

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

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

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

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

1. Близость сохраняется с помощью функций перехода : для любого r любой функции перехода f в F любого входного вектора x и для любых двух векторов состояния s1 _, выполняется s2 _{>1, для} следующее: s1 _{, для} если ( 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 ,...,С ^БД ) и x =(1,...,1). Если степень полученного многочлена по z не превосходит d _j , то условие 1 выполнено.
2. Близость сохраняется функцией значения : существует целое число G ≥ 0 (которое является функцией функции значения g и вектора степени d ), такое, что для любого r > 1 и для любых двух векторов состояния s ₁ , s ₂ , имеет место следующее: если s ₁ ( d,r )-близок к s ₂ , то: g ( s ₁ ) ≤ r ^Г · g ( s ₂ ) (в задачах минимизации); г ( s ₁ ) ≥ р ^(-Г) · g ( s ₂ ) (в задачах максимизации).
   • Достаточным условием для этого является то, что функция g является полиномиальной функцией (от b переменных) с неотрицательными коэффициентами.
3. Технические условия :
   • Все функции перехода f в F и функция значения g могут быть вычислены за политайм.
   • Число | Ф | функций перехода является полиномиальным по 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. Определять:

• $\epsilon$ := требуемый коэффициент аппроксимации.
• $r:=1+{\frac {\epsilon }{2Gn}}$, где G – константа из условия 2. Заметим, что ${\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}$.
• $L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil$, где P ₁ — полином из условия 3 (верхняя граница ln каждого значения, которое может появиться в векторе состояния). Обратите внимание, что $L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil$, поэтому он является полиномиальным по размеру входных данных и по $1/\epsilon$. Также, $r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}$, поэтому по определению P ₁ каждое целое число, которое может появиться в векторе состояния, находится в диапазоне [0, r ^л ].
• Разделить диапазон [0, r ^л ] на L +1 r -интервалы: $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 )-близки.
• $R:=(L+1+P_{2}(n,\log {X}))^{b}$.
  • что количество r -блоков не превышает R. Обратите внимание , Поскольку b — фиксированная константа, этот R является полиномиальным по размеру входных данных и по $1/\epsilon$.

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

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

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

Заметим, что для каждого состояния s _u в U _k его подмножество T _k содержит хотя бы одно состояние st _, которое (d,r)-близко к s _u . Кроме того, каждый U _k является подмножеством Sk _в исходной (необрезанной) DP. Основная лемма для доказательства правильности FPTAS:

каждого шага k в 0,..., n для каждого состояния s _s в Sk _Для существует состояние в _st T k _, которое есть ( d , r ^к )-близко к 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 ^к-1 )-близко к s _{s −} . Поскольку близость сохраняется за счет переходов (условие 1 выше), f ( s _{t −} , x ) равно ( d , r ^к-1 )-близко к f ( s _{s -} , x )= s _s . Это f ( s _{t -} , x ) находится в U _k . После обрезки существует состояние st _t в T _k , которое ( d , r )-близко к f(s _t- ,x) . Это s _t ( d , r ^к )-близко к s _s .

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

Примеры

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

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

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

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

5. Взвешенная скорость-опоздание относительно общего срока сдачи на любом фиксированном количестве машин: m|| $\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 .
• Выход мин/макс {г(с) | s в Sn _} .

Проблема называется доброжелательной, если она удовлетворяет следующим условиям (которые расширяют условия 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 ).
   • если s1 _над доминирует над , _s2 то f ( s1 ₍ , x ) доминирует f ) s2 _, x .
2. Близость сохраняется функцией ценности: существует целое число G ≥ 0 (функция функции ценности g и вектора степени d ), такое, что для любого r >1 и для любых двух векторов состояния s ₁ , s ₂ , имеет место следующее:
   • если s ₁ ( d,r )-близок к s ₂ , а s ₁ квазидоминирует s ₂ , то: g ( s ₁ ) ≤ r ^Г · g ( s ₂ ) (в задачах минимизации); г ( s ₁ ) ≥ р ^(-Г) · g ( s ₂ ) (в задачах максимизации).
   • если s1 _s2 доминирует над , _g то ( s1 ) _≤ g ( s2 ) _; (в задачах минимизации) 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 .
• Выход мин/макс {г(с) | s в T _n }.

Примеры

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

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

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

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

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

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

5. Всего опозданий на одну машину: 1|| $\sum V_{j}$.

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

Непримеры

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

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

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

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

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

Некоторые другие проблемы, связанные с FPTAS

• Задача о рюкзаке , а также некоторые его варианты:
  • Проблема с рюкзаком 0-1.
  • Задача о неограниченном рюкзаке.
  • Многомерная задача о рюкзаке с дельта-модулярными ограничениями.
  • Многоцелевая задача о рюкзаке 0-1.
  • Параметрическая задача о рюкзаке.
  • Симметричная квадратичная задача о рюкзаке.
• Count-subset-sum (#SubsetSum ) нахождение количества различных подмножеств с суммой не более C. —
• Ограниченный кратчайший путь : поиск пути с минимальной стоимостью между двумя узлами графа с учетом ограничения задержки.
• Кратчайшие пути и нелинейные цели.
• Подсчет краевых покрытий .
• Задача поиска подмножества векторов с фиксированной размерностью.

См. также

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

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

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