Jump to content

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

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

В контексте задач оптимизации под правильным значением понимается значение оптимального решения, и часто подразумевается, что 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] представил общую схему преобразования определенного класса динамических программ в ФПТАС.

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

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

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

[ редактировать ]

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

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

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

  • Пусть S 0 := множество начальных состояний.
  • Для 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 1 ,..., d b ), называемый вектором степени проблемы. действительного числа r >1 мы говорим, что два вектора состояния s1 Для , s2 каждого , (d,r)-близки если для каждой координаты j в 1,..., b : (в частности, если d j =0 для некоторого j , то ).

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

  1. Близость сохраняется с помощью функций перехода : для любого r любой функции перехода f в F любого входного вектора x и для любых двух векторов состояния s1 , выполняется s2 >1, для следующее: s1 , для если ( d,r )-близко к s 2 , то f ( s 1 , x ) ( d,r )-близко к f ( s 2 ,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 1 , s 2 , имеет место следующее: если s 1 ( d,r )-близок к s 2 , то: g ( s 1 ) ≤ r Г · g ( s 2 ) (в задачах минимизации); г ( s 1 ) ≥ р (-Г) · g ( s 2 ) (в задачах максимизации).
    • Достаточным условием для этого является то, что функция g является полиномиальной функцией (от b переменных) с неотрицательными коэффициентами.
  3. Технические условия :
    • Все функции перехода f в F и функция значения g могут быть вычислены за политайм.
    • Число | Ф | функций перехода является полиномиальным по n и log( X ).
    • Набор S 0 начальных состояний может быть вычислен за полиномиальное от n и log( X ) время.
    • Пусть V j будет набором всех значений, которые могут появиться в координате j в состоянии. Тогда ln каждого значения в V j не более чем полином P 1 (n,log(X)).
    • Если d j =0, мощность V j не превышает полинома P 2 ( n ,log( X )).

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

  • := требуемый коэффициент аппроксимации.
  • , где G – константа из условия 2. Заметим, что .
  • , где P 1 — полином из условия 3 (верхняя граница ln каждого значения, которое может появиться в векторе состояния). Обратите внимание, что , поэтому он является полиномиальным по размеру входных данных и по . Также, , поэтому по определению P 1 каждое целое число, которое может появиться в векторе состояния, находится в диапазоне [0, r л ].
  • Разделить диапазон [0, r л ] на L +1 r -интервалы: .
  • Разделите пространство состояний на r-блоки : каждая координата k степени d k ≥ 1 разбивается на интервалы L +1, указанные выше; каждая координата с d k = 0 разбивается на P 2 ( n ,log( X )) одноэлементные интервалы - интервал для каждого возможного значения координаты k (где P 2 - полином из условия 3 выше).
    • Обратите внимание, что каждое возможное состояние содержится ровно в одном r -блоке; если два состояния находятся в одном r -блоке, то они ( d , r )-близки.
  • .
    • что количество r -блоков не превышает R. Обратите внимание , Поскольку b — фиксированная константа, этот R является полиномиальным по размеру входных данных и по .

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

  • Пусть T 0 := S 0 = множество начальных состояний.
  • Для 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 ), и .

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

каждого шага 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 , . Так . Аналогичный аргумент работает и для задачи минимизации.

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

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

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

2. Сумма кубов времени завершения работы на любом фиксированном количестве одинаковых или однородных машин – последнее обозначается Qm|| - экс-доброжелателен с a =1, b =3, d=(1,1,3). Его можно расширить до любой фиксированной степени времени завершения.

3. Сумма взвешенного времени завершения на любом фиксированном количестве идентичных или однородных машин – последнее обозначается Qm|| .

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

5. Взвешенная скорость-опоздание относительно общего срока сдачи на любом фиксированном количестве машин: m|| .

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

[ редактировать ]

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

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

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

  • Пусть S 0 := множество начальных состояний.
  • Для 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 1 , s 2 выполняется следующее:
    • если s 1 ( d,r )-близок к s 2 , а s 1 квазидоминирует s 2 , то либо (a) f ( s 1 , x ) ( d,r )-близок к f ( s 2 , x ) и f ( s 1 , x ) квазидоминирует f ( s 2 ,x ) или (b) f ( s 1 , x ) доминирует f ( s 2 ,x ).
    • если s1 над доминирует над , s2 то f ( s1 ( , x ) доминирует f ) s2 , x .
  2. Близость сохраняется функцией ценности: существует целое число G ≥ 0 (функция функции ценности g и вектора степени d ), такое, что для любого r >1 и для любых двух векторов состояния s 1 , s 2 , имеет место следующее:
    • если s 1 ( d,r )-близок к s 2 , а s 1 квазидоминирует s 2 , то: g ( s 1 ) ≤ r Г · g ( s 2 ) (в задачах минимизации); г ( s 1 ) ≥ р (-Г) · g ( s 2 ) (в задачах максимизации).
    • если s1 s2 доминирует над , g то ( s1 ) g ( s2 ) ; (в задачах минимизации) g ( s 1 ) ≥ g ( s 2 ) (в задачах максимизации).
  3. Технические условия (помимо вышеперечисленных):
    • Отношение квазидоминирования может быть решено за полиномиальное время.
  4. Условия для функций фильтра : Для любого r >1, для любой функции фильтра h в H , для любого входного вектора x и для любых двух векторов состояния s 1 , s 2 выполняется следующее:
    • если s 1 ( d,r )-близок к s 2 , и s 1 квазидоминирует s 2 то h ( s 1 , x ) ≥ h ( s 2 , x ) .
    • если s 1 доминирует над s 2 , то h ( s 1 , x ) ≥ h ( s 2 , x ).

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

  • Пусть T 0 := S 0 = множество начальных состояний.
  • Для 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 по приведенной выше теореме. [6]

1. Проблема с рюкзаком 0:1 благожелательна. Здесь у нас есть = 2: каждый вход представляет собой 2-вектор (вес, значение). Есть ДП с b =2: каждое состояние кодирует (текущий вес, текущее значение). Существует две функции перехода: f 1 соответствует добавлению следующего входного элемента, а f 2 соответствует его не добавлению. Соответствующие функции фильтра: h 1 проверяет, что вес следующего входного элемента не превышает вместимости рюкзака; h 2 всегда возвращает True. Функция значения ( s ) возвращает s2 g . Начальный набор состояний — {(0,0)}. Вектор степени равен (1,1). Отношение доминирования тривиально. Отношение квазидоминирования сравнивает только весовую координату: s квазидоминирует t тогда и только тогда, когда s 1 t 1 . Следствием этого является то, что если состояние t имеет более высокий вес, чем состояние s , то функциям перехода разрешено не сохранять близость между t и s (возможно, например, что s имеет преемника, а t не имеет иметь соответствующего преемника). Похожий алгоритм ранее был представлен Ибаррой и Кимом. [7] Время работы этого FPTAS может быть улучшено до операции с целыми числами. [8] Позже показатель был улучшен до 2,5. [9]

  • Примечание : рассмотрим задачу о 2-х весовом рюкзаке , где каждый предмет имеет два веса и значение, и цель состоит в том, чтобы максимизировать значение так, чтобы сумма квадратов общих весов не превышала вместимость рюкзака: . Мы могли бы решить эту проблему, используя аналогичный DP, где каждое состояние имеет значение (текущий вес 1, текущий вес 2, значение). Отношение квазидоминирования должно быть изменено следующим образом: s квазидоминирует t тогда и только тогда, когда ( s 1 2 + с 2 2 ) ≤ ( т 1 2 + т 2 2 ). Но это нарушает условие 1 выше: квазидоминирование не сохраняется функциями перехода (например, состояние (2,2,..) квазидоминирует (1,3,..); но после добавления входных данных (2,0,..) к обоим состояниям результат (4,2,..) не квазидоминирует (3,3,..)]. Поэтому теорему использовать нельзя. Действительно, эта задача не имеет FPTAS, если P = NP. То же самое справедливо и для двумерной задачи о рюкзаке. То же самое верно и для о сумме множественных подмножеств : отношение квазидоминирования должно быть: квазидоминирует t тогда и только тогда, когда max( s1 , s2 s ) ≤ max( t1 , t2 задачи ), но оно не сохраняется при переходах , по тому же примеру, что и выше.

2. Минимизация взвешенного количества запоздалых заданий или максимизация взвешенного количества ранних заданий на одной машине; обозначается 1|| .

3. Пакетное планирование для минимизации взвешенного количества опоздавших заданий: 1|batch| .

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

5. Всего опозданий на одну машину: 1|| .

6. Общее количество взвешенных просроченных работ на одной машине: 1|| .

Непримеры

[ редактировать ]

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

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

2. В задаче минимизации дисперсии 1|| , целевая функция , что нарушает условие 2, поэтому теорему использовать нельзя. Но для разработки FPTAS использовались разные методы. [14] [15]

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

[ редактировать ]

Другой тип задач, в которых может оказаться полезным FPTAS, — это поиск рациональных чисел, аппроксимирующих некоторые действительные числа. Например, рассмотрим бесконечный ряд . Сумма является иррациональным числом . Чтобы аппроксимировать его рациональным числом, мы можем вычислить сумму первых k элементов для некоторого конечного k . Можно показать, что ошибка аппроксимации составляет около . Следовательно, чтобы получить погрешность ε, нам нужно около элементы, так что это FPTAS. Обратите внимание, что эта конкретная сумма может быть представлена ​​другой суммой, в которой необходимы только элементы O (log (ε)), поэтому сумма фактически может быть аппроксимирована за полиномиальное время с длиной кодирования ε. [16] : 35, разд.1

Некоторые другие проблемы, связанные с 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. ^ Г. Аузиелло, П. Крещенци, Г. Гамбози, В. Канн, А. Маркетти-Спаккамела и М. Протаси. Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer-Verlag, 1999.
  2. ^ Янсен, Томас (1998), «Введение в теорию сложности и алгоритмы аппроксимации», Майр, Эрнст В.; Премель, Ханс Юрген; Стегер, Анжелика (ред.), Лекции по алгоритмам проверки доказательств и аппроксимации , Конспекты лекций по информатике, том. 1367, Springer, стр. 5–28, номер документа : 10.1007/BFb0053011 , ISBN.  9783540642015 . См. обсуждение после определения 1.30 на стр. 20 .
  3. ^ Кай, Лиминг; Чен, Цзянер (июнь 1997 г.). «О разрешимости и аппроксимируемости задач NP-оптимизации при фиксированных параметрах» . Журнал компьютерных и системных наук . 54 (3): 465–474. дои : 10.1006/jcss.1997.1490 .
  4. ^ Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. Corollary 8.6. ISBN  3-540-65367-8 .
  5. ^ Х. Келлерер; У. Пферши; Д. Пизингер (2004). Проблемы с рюкзаком . Спрингер. Теорема 9.4.1.
  6. ^ Jump up to: а б с д Вегингер, Герхард Дж. (1 февраля 2000 г.). «Когда формулировка динамического программирования гарантирует существование полностью полиномиальной схемы аппроксимации времени (FPTAS)?» . ИНФОМС Журнал по вычислительной технике . 12 (1): 57–74. дои : 10.1287/ijoc.12.1.57.11901 . ISSN   1091-9856 .
  7. ^ Ибарра, Оскар Х.; Ким, Чул Э. (1 октября 1975 г.). «Алгоритмы быстрого приближения для задач о рюкзаке и сумме подмножеств» . Журнал АКМ . 22 (4): 463–468. дои : 10.1145/321906.321909 . ISSN   0004-5411 . S2CID   14619586 .
  8. ^ Лоулер, Юджин Л. (1 ноября 1979 г.). «Алгоритмы быстрого приближения для задач о рюкзаке» . Математика исследования операций . 4 (4): 339–356. дои : 10.1287/moor.4.4.339 . ISSN   0364-765X . S2CID   7655435 .
  9. ^ Ри, Донгук (2015). Более быстрые полностью полиномиальные схемы аппроксимации задач о рюкзаке (диссертация). Массачусетский технологический институт. hdl : 1721.1/98564 .
  10. ^ Лоулер, Юджин Л. (1 января 1977 г.), Хаммер, Польша; Джонсон, Эл.; Корте, БХ; Немхаузер, Г.Л. (ред.), «Псевдополиномиальный» алгоритм для упорядочения заданий для минимизации общего опоздания ** Исследование, поддержанное грантом Национального научного фонда GJ-43227X» , Анналы дискретной математики , Исследования по целочисленному программированию, том. 1, Elsevier, стр. 331–342, номер документа : 10.1016/S0167-5060(08)70742-8 , получено 17 декабря 2021 г.
  11. ^ Флориан, М.; Ленстра, Дж. К.; Риннуй Кан, AHG (1 июля 1980 г.). «Детерминированное планирование производства: алгоритмы и сложности» . Наука управления . 26 (7): 669–679. дои : 10.1287/mnsc.26.7.669 . ISSN   0025-1909 .
  12. ^ Лоулер, Эл. (1 декабря 1982 г.). «Полностью полиномиальная схема аппроксимации проблемы тотального опоздания» . Письма об исследованиях операций . 1 (6): 207–208. дои : 10.1016/0167-6377(82)90022-0 . ISSN   0167-6377 .
  13. ^ ван Хозель, CPM; Вагельманс, APM (2001). «Полностью полиномиальные схемы аппроксимации для задач определения размера экономической партии с использованием одного элемента» . Математика исследования операций . 26 (2): 339–357. дои : 10.1287/moor.26.2.339.10552 .
  14. ^ Цай, X. (21 сентября 1995 г.). «Минимизация приятно взвешенной дисперсии в одномашинных системах» . Европейский журнал операционных исследований . 85 (3): 576–592. дои : 10.1016/0377-2217(93)E0367-7 . ISSN   0377-2217 .
  15. ^ Вегингер, Герхард Дж. (1 мая 1999 г.). «Схема аппроксимации для минимизации согласованно взвешенной дисперсии на одной машине» . ИНФОМС Журнал по вычислительной технике . 11 (2): 211–216. дои : 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). Алгоритмы аппроксимации . Берлин: Шпрингер. стр. 69–70 . ISBN  3540653678 . OCLC   47097680 .
  18. ^ Келлерер, Ганс; Пферши, Ульрих (1 марта 2004 г.). «Улучшенное динамическое программирование в связи с FPTAS для задачи о рюкзаке» . Журнал комбинаторной оптимизации . 8 (1): 5–11. дои : 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. ^ Янсен, Клаус; Крафт, Стефан Э.Дж. (01 февраля 2018 г.). «Более быстрый FPTAS для задачи о неограниченном рюкзаке» . Европейский журнал комбинаторики . Комбинаторные алгоритмы, памяти Мирки Миллер посвящается. 68 : 148–174. arXiv : 1504.04650 . дои : 10.1016/j.ejc.2017.07.016 . ISSN   0195-6698 . S2CID   9557898 .
  21. ^ Грибанов, Д.В. (10 мая 2021 г.). «FPTAS для $$\var Delta $$-модульной многомерной задачи о рюкзаке». Математическая теория оптимизации и исследование операций . Конспекты лекций по информатике. Том. 12755. стр. 79–95. arXiv : 2103.07257 . дои : 10.1007/978-3-030-77876-7_6 . ISBN  978-3-030-77875-0 . S2CID   232222954 .
  22. ^ Базган, Кристина; Хьюго, Адриан; Вандерпоотен, Дэниел (01 октября 2009 г.). «Реализация эффективного fptas для многокритериальной задачи о рюкзаке 0–1» . Европейский журнал операционных исследований . 198 (1): 47–56. дои : 10.1016/j.ejor.2008.07.047 . ISSN   0377-2217 .
  23. ^ Хольцхаузер, Майкл; Крумке, Свен О. (01 октября 2017 г.). «FPTAS для параметрической задачи о рюкзаке» . Письма об обработке информации . 126 : 43–47. arXiv : 1701.07822 . дои : 10.1016/j.ipl.2017.06.006 . ISSN   0020-0190 . S2CID   1013794 .
  24. ^ Сюй, Чжоу (16 апреля 2012 г.). «Сильно полиномиальный FPTAS для симметричной квадратичной задачи о рюкзаке» . Европейский журнал операционных исследований . 218 (2): 377–381. дои : 10.1016/j.ejor.2011.10.049 . hdl : 10397/24376 . ISSN   0377-2217 .
  25. ^ Гопалан, Парикшит; Кливанс, Адам; Мека, Рагху; Штефанкович, Даниэль; Вемпала, Сантош; Вигода, Эрик (01 октября 2011 г.). «FPTAS для #Knapsack и связанных с ним задач со счетом» . 2011 52-й ежегодный симпозиум IEEE по основам информатики . стр. 817–826. дои : 10.1109/FOCS.2011.32 . ISBN  978-0-7695-4571-4 . S2CID   5691574 .
  26. ^ Эргун, Фунда; Синха, Ракеш; Чжан, Лиза (15 сентября 2002 г.). «Улучшенный FPTAS для ограниченного кратчайшего пути» . Письма об обработке информации . 83 (5): 287–291. дои : 10.1016/S0020-0190(02)00205-3 . ISSN   0020-0190 .
  27. ^ Цагурис, Джордж; Зарольягис, Христос (1 июня 2009 г.). «Многокритериальная оптимизация: улучшенная FPTAS для кратчайших путей и нелинейных целей с приложениями» . Теория вычислительных систем . 45 (1): 162–186. дои : 10.1007/s00224-007-9096-4 . ISSN   1433-0490 . S2CID   13010023 .
  28. ^ Линь, Чэнъюй; Лю, Цзинчэн; Лу, Пиньян (18 декабря 2013 г.), «Простой FPTAS для подсчета реберных покрытий» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2014 г. , Труды Общества промышленной и прикладной математики, стр. 341– 348, arXiv : 1309.6115 , doi : 10.1137/1.9781611973402.25 , ISBN  978-1-61197-338-9 , S2CID   14598468 , получено 13 декабря 2021 г.
  29. ^ Кельманов А.В.; Романченко, С.М. (01.07.2014). «FPTAS для задачи поиска подмножества векторов» . Журнал прикладной и промышленной математики . 8 (3): 329–336. дои : 10.1134/S1990478914030041 . ISSN   1990-4797 . S2CID   96437935 .
  30. ^ Дорр, Бенджамин; Еремеев Антон; Нойманн, Франк; Тейль, Мадлен; Тиссен, Кристиан (7 октября 2011 г.). «Эволюционные алгоритмы и динамическое программирование» . Теоретическая информатика . 412 (43): 6020–6035. arXiv : 1301.4096 . дои : 10.1016/j.tcs.2011.07.024 . ISSN   0304-3975 .
[ редактировать ]
  • Зоопарк сложности: FPTAS
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 52761a750c963248604553a33f2a6a75__1722203880
URL1:https://arc.ask3.ru/arc/aa/52/75/52761a750c963248604553a33f2a6a75.html
Заголовок, (Title) документа по адресу, URL1:
Fully polynomial-time approximation scheme - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)