Приближенные схемы по одноименному роману Петры Схурман и Герхарда Вёгингера режиссер-постановщик Александр Кононов

Проблема Кроша

Не мог бы ты составить мне план мероприятий, так чтобы я отправился в космос как можно скорее ? Я могу, я все могу! И я думаю, что месяц - это оптимальный срок для такого проекта! Отлично! Завтра же приступаю! Я зайду за планом завтра утром! Но, я не успею найти план до утра! Пин все может, но … это потребует двадцать три с половиной года !!!

Завтра… 2 месяца Но …я хотел … 1 месяц Тогда…через 23,5 года Послезавтра 1.5 месяца Через 3 дня … 1 и 1/3 месяца Что если я зайду ровно через X дней 1+1/X

Приближенный алгоритм Полиномиальный алгоритм A называется ρ-приближенным алгоритмом для задачи минимизации Π, если для каждой ее индивидуальной задачи I Ω Π, Полиномиальный алгоритм A называется ρ-приближенным алгоритмом для задачи минимизации Π, если для каждой ее индивидуальной задачи I Ω Π, A(I) ρOPT(I). A(I) ρOPT(I).

Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа при фиксированном ε. Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа при фиксированном ε.

Вполне полиномиальная приближенная схема (FPTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется вполне полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа и 1/ε. Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется вполне полиномиальной приближенной схемой, если алгоритм A ε (1+ε)-приближенный алгоритм и время его работы ограничено полиномом от размера входа и 1/ε.

Комментарий Трудоемкость Трудоемкость PTAS: | I | 2/ε, | I | 2/ε 10, (| I | 2/ε ) 1/ε. PTAS: | I | 2/ε, | I | 2/ε 10, (| I | 2/ε ) 1/ε. FPTAS: | I | 2 /ε, | I |/ε 2, | I | 7 /ε 3. FPTAS: | I | 2 /ε, | I |/ε 2, | I | 7 /ε 3. С точки зрения точности алгоритма в худшем случае FPTAS – наилучший результат, на который можно надеяться для NP-трудных задач. С точки зрения точности алгоритма в худшем случае FPTAS – наилучший результат, на который можно надеяться для NP-трудных задач.

Отношение между классами NP P APX PTAS FPTAS Псевдополиномиальные алгоритмы

История Graham 1966: 2-прибл. для P||C max. Graham 1966: 2-прибл. для P||C max. Graham 1969: PTAS для Pm||C max. Graham 1969: PTAS для Pm||C max. Gary, Graham, Ullman 1972: концепция приближенных алгоритмов Gary, Graham, Ullman 1972: концепция приближенных алгоритмов Gorowitz, Sahni, Ibarra, Kim ( ): первые PTAS и FPTAS для задач о рюкзаке и задач теории расписаний. Gorowitz, Sahni, Ibarra, Kim ( ): первые PTAS и FPTAS для задач о рюкзаке и задач теории расписаний.

История продолжается Garey, Johnson 1978: термины PTAS, FPTAS. Garey, Johnson 1978: термины PTAS, FPTAS. Fernandez de la Vega, Lueker 1981: AFPTAS для задачи об упаковке в контейнеры. Fernandez de la Vega, Lueker 1981: AFPTAS для задачи об упаковке в контейнеры. Hochbaum, Shmoys 1988: PTAS для P||C max. Hochbaum, Shmoys 1988: PTAS для P||C max. Baker 1994: PTAS для задач на планарных графах (макс. независимое мн-во, миним. вершинное покрытие, миним. домин мн-во). Baker 1994: PTAS для задач на планарных графах (макс. независимое мн-во, миним. вершинное покрытие, миним. домин мн-во). Arora 1996: PTAS для задачи коммивояжера на плоскости. Arora 1996: PTAS для задачи коммивояжера на плоскости.

Отрицательные результаты Sahni, Gonzalez 1976: задача коммивояжера не существует ρ-прибл. алг., где ρ – любая конст. Sahni, Gonzalez 1976: задача коммивояжера не существует ρ-прибл. алг., где ρ – любая конст. Lenstra, Rinnoy Kan 1978: P|prec, p j =1|C max не существует (4/3–ε)-прибл. алг. Lenstra, Rinnoy Kan 1978: P|prec, p j =1|C max не существует (4/3–ε)-прибл. алг. Willamson, Hall, Hoogeven, Hurkens, Lenstra, Sevastianov, Shmoys 1997: F||C max, O||C max не существует (5/4–ε)-прибл. алг. Willamson, Hall, Hoogeven, Hurkens, Lenstra, Sevastianov, Shmoys 1997: F||C max, O||C max не существует (5/4–ε)-прибл. алг.

Отрицательные результаты Papadimitriou, Yanakakis 1991: новые идеи и инструменты для получения отрицательных результатов. Определение класса APX. Papadimitriou, Yanakakis 1991: новые идеи и инструменты для получения отрицательных результатов. Определение класса APX. Arora, Lund, Motwani, Sudan, Szegedy 1992: труднейшая задача в APX не имеет PTAS, если P NP. Arora, Lund, Motwani, Sudan, Szegedy 1992: труднейшая задача в APX не имеет PTAS, если P NP.

Цеховые задачи Willamson, Hall, Hoogeven, Hurkens, Lenstra, Sevastianov, Shmoys 1997: F||C max, O||C max не существует (5/4–ε)-прибл. алг. Willamson, Hall, Hoogeven, Hurkens, Lenstra, Sevastianov, Shmoys 1997: F||C max, O||C max не существует (5/4–ε)-прибл. алг. Hall 1998: PTAS для Fm||C max. Hall 1998: PTAS для Fm||C max. Sevastianov, Woeginger 1998: PTAS для Om||C max. Sevastianov, Woeginger 1998: PTAS для Om||C max. Sviridenko, Jansen, Solis-Oba 1999: PTAS для Jm||C max. Sviridenko, Jansen, Solis-Oba 1999: PTAS для Jm||C max.

Как построить PTAS Упрощение примера I. Упрощение примера I. Разбиение пространства решений. Разбиение пространства решений. Структурирование работы алгоритма A. Структурирование работы алгоритма A. Пример I Алгоритм AРешение A(I)

Упрощение примера I. Первая идея превратить трудный пример в более простой в котором легче найти оптимальное решение. Затем мы используем оптимальное решение простого примера для получения приближенного решения для трудного примера. Первая идея превратить трудный пример в более простой в котором легче найти оптимальное решение. Затем мы используем оптимальное решение простого примера для получения приближенного решения для трудного примера. Упростить Решить OPT # Вернуться OPT App I I #

Способы упрощения Округление Округление Слияние Слияние Отбрасывание Отбрасывание Усреднение Усреднение

P2||C max J={1,..., n} – работы. J={1,..., n} – работы. {M 1, M 2 } – одинаковые машины. {M 1, M 2 } – одинаковые машины. j : p j > 0 (i=1,…, n). j : p j > 0 (i=1,…, n). Каждая работа должна быть выполнена на одной из двух машин. Каждая работа должна быть выполнена на одной из двух машин. Минимизировать длину расписания (C max ). Минимизировать длину расписания (C max ). Прерывания запрещены. Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно. Каждая машина обслуживает не более одной работы одновременно.

Нижняя оценка

Как упростить пример? (I I # ) Big = { j J | p j εL} Big = { j J | p j εL} Новый пример I # содержит все большие работы из I. Новый пример I # содержит все большие работы из I. Small = { j J | p j < εL} Small = { j J | p j < εL} Пусть X= Σ j Small p j. Пусть X= Σ j Small p j. Новый пример I # содержит X/εL работ длины εL. Новый пример I # содержит X/εL работ длины εL. Маленькие работы, как бы склеиваются вместе и разрезаются на маленькие одинаковые кусочки. Маленькие работы, как бы склеиваются вместе и разрезаются на маленькие одинаковые кусочки.

Оценка на оптимум OPT(I # ) (1+ ε)OPT(I ). OPT(I # ) (1+ ε)OPT(I ).

Доказательство X i – размер всех маленьких работ, выполняемых на машине M i в оптимальном расписании для I. X i – размер всех маленьких работ, выполняемых на машине M i в оптимальном расписании для I. Оставим все большие работы на тех машинах, где они были в оптимальном расписании. Оставим все большие работы на тех машинах, где они были в оптимальном расписании. Заменим все маленькие работы на машине M i на X i /εL работ длины εL. Заменим все маленькие работы на машине M i на X i /εL работ длины εL. X 1 /εL + X 2 /εL X 1 /εL + X 2 /εL = X/εL X 1 /εL + X 2 /εL X 1 /εL + X 2 /εL = X/εL X i /εL εL – X i (X i /εL + 1) εL – X i εL X i /εL εL – X i (X i /εL + 1) εL – X i εL OPT(I # ) OPT + εL (1+ ε)OPT(I) OPT(I # ) OPT + εL (1+ ε)OPT(I)

Как решить упрощенный пример? Как много работ в I # ? Как много работ в I # ? p j εL для всех работ в I #. p j εL для всех работ в I #. Общая длина всех работ в I # p sum 2L. Общая длина всех работ в I # p sum 2L. Число работ в I # 2L/εL= 2/ε. Число работ в I # 2L/εL= 2/ε. Число работ в I # не зависит от n ! Число работ в I # не зависит от n ! Найдем все возможные расписания. Найдем все возможные расписания. Число различных расписаний 2 2/ε ! Число различных расписаний 2 2/ε !

Как вернуться к исходной задаче? Пусть σ # – оптимальное расписание для I #. Пусть σ # – оптимальное расписание для I #. L i # – нагрузка машины M i в σ #. L i # – нагрузка машины M i в σ #. B i # – общая длина больших работ на M i в σ #. B i # – общая длина больших работ на M i в σ #. X i # – размер всех маленьких работ на M i в σ #. X i # – размер всех маленьких работ на M i в σ #. L i # = B i # + X i #. L i # = B i # + X i #.

Алгоритм ( σ # (I # ) σ(I) ) Большие работы выполняются на той же машине, что и в σ #. Большие работы выполняются на той же машине, что и в σ #. Выделим интервал длины X 1 # + 2εL на машине M 1 и X 2 # на машине M 2. Выделим интервал длины X 1 # + 2εL на машине M 1 и X 2 # на машине M 2. Будем последовательно упаковывать маленькие работы в выделенный интервал на M 1, пока не встретим работу, которая туда не поместится. Будем последовательно упаковывать маленькие работы в выделенный интервал на M 1, пока не встретим работу, которая туда не поместится. Оставшиеся маленькие работы упакуем в выделенный интервал на M 2. Оставшиеся маленькие работы упакуем в выделенный интервал на M 2.

Оценка качества

Разбиение пространства решений Вторая идея разбить пространство решений на несколько меньших областей, в которых проще найти хорошее приближенное решение. Решив задачу отдельно для каждой маленькой области и взяв среди них лучшее есть шанс получить хорошее приближенное решение. Вторая идея разбить пространство решений на несколько меньших областей, в которых проще найти хорошее приближенное решение. Решив задачу отдельно для каждой маленькой области и взяв среди них лучшее есть шанс получить хорошее приближенное решение. * * * * * * * * * * *

Общая схема 1. Разбиение на области. 2. Выбор «хорошего» представителя в каждой области. 3. Выбор из множества хороших представителей наилучшего.

P2||C max J={1,..., n} – работы. J={1,..., n} – работы. {M 1, M 2 } – одинаковые машины. {M 1, M 2 } – одинаковые машины. j : p j > 0 (i=1,…, n). j : p j > 0 (i=1,…, n). Каждая работа должна быть выполнена на одной из двух машин. Каждая работа должна быть выполнена на одной из двух машин. Минимизировать длину расписания (C max ). Минимизировать длину расписания (C max ). Прерывания запрещены. Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно. Каждая машина обслуживает не более одной работы одновременно.

Как разбить на области Big = { j J| p j εL} Big = { j J| p j εL} Small = { j J| p j < εL} Small = { j J| p j < εL} Φ – множество допустимых расписаний Φ – множество допустимых расписаний Расписание σ Φ – назначение работ на машины. Расписание σ Φ – назначение работ на машины. Определим области Φ (1), Φ (2),…согласно назначению больших работ: σ 1 и σ 2 лежат в одной области тогда и только тогда, когда каждая большая работа выполняется в σ 1 на той же машине, что и в σ 2. Определим области Φ (1), Φ (2),…согласно назначению больших работ: σ 1 и σ 2 лежат в одной области тогда и только тогда, когда каждая большая работа выполняется в σ 1 на той же машине, что и в σ 2.

Сколько получилось областей? Число больших работ 2L/εL= 2/ε. Число больших работ 2L/εL= 2/ε. Число способов разместить большие работы по двум машинам 2 2/ε. Число способов разместить большие работы по двум машинам 2 2/ε. Число различных областей 2 2/ε ! Число различных областей 2 2/ε ! Число различных областей зависит от ε и не зависит от размера входа! Число различных областей зависит от ε и не зависит от размера входа!

Как выбрать «хорошего» представителя? Назначение больших работ зафиксировано в Φ (l). Назначение больших работ зафиксировано в Φ (l). OPT (l) – длина оптимального расписания в Φ (l). OPT (l) – длина оптимального расписания в Φ (l). B i (l) – общая длина больших работ на M i. B i (l) – общая длина больших работ на M i. T := max{B i (1), B i (2) } OPT (l) T := max{B i (1), B i (2) } OPT (l) Пусть B i (l) начальная загрузка машины M i. Пусть B i (l) начальная загрузка машины M i. Назначим маленькие работы одну за другой по следующему правилу: каждый раз работа назначается на машину с меньшей нагрузкой на этот момент. Назначим маленькие работы одну за другой по следующему правилу: каждый раз работа назначается на машину с меньшей нагрузкой на этот момент. Полученное расписание σ (l) длины A (l) выберем представителем от Φ (l). Полученное расписание σ (l) длины A (l) выберем представителем от Φ (l).

А хорош ли представитель? 1. Если A (l) =T, то A (l) = OPT (l). 2. Пусть A (l) >T. Рассмотрим машину с большей загрузкой в σ (l). Рассмотрим машину с большей загрузкой в σ (l). Последняя назначенная на нее работа маленькая и ее длина меньше εL. Последняя назначенная на нее работа маленькая и ее длина меньше εL. В момент назначения этой работы загрузка этой машины не превышала p sum / 2. В момент назначения этой работы загрузка этой машины не превышала p sum / 2. A (l) (p sum / 2) + εL (1 + ε)OPT (1 + ε)OPT (l) A (l) (p sum / 2) + εL (1 + ε)OPT (1 + ε)OPT (l)

Структурирование работы алгоритма Основная идея рассмотреть точный, но медленный алгоритм. Основная идея рассмотреть точный, но медленный алгоритм. Если алгоритм получает и перерабатывает огромное количество различных значений, то мы можем отбросить часть из них и ускорить работу алгоритма. Если алгоритм получает и перерабатывает огромное количество различных значений, то мы можем отбросить часть из них и ускорить работу алгоритма.

P2||C max J={1,..., n} – работы. J={1,..., n} – работы. {M 1, M 2 } – одинаковые машины. {M 1, M 2 } – одинаковые машины. j : p j > 0 (i=1,…, n). j : p j > 0 (i=1,…, n). Каждая работа должна быть выполнена на одной из двух машин. Каждая работа должна быть выполнена на одной из двух машин. Минимизировать длину расписания (C max ). Минимизировать длину расписания (C max ). Прерывания запрещены. Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно. Каждая машина обслуживает не более одной работы одновременно.

Краткая запись решения Обозначим через σ k допустимое расписание k первых работ {1,..., k}. Обозначим через σ k допустимое расписание k первых работ {1,..., k}. Закодируем расписание σ k с нагрузками машин L 1 и L 2 двумерным вектором [L 1, L 2 ]. Закодируем расписание σ k с нагрузками машин L 1 и L 2 двумерным вектором [L 1, L 2 ]. Пусть V k обозначает множество векторов, соответствующих допустимым расписаниям k первых работ {1,..., k}. Пусть V k обозначает множество векторов, соответствующих допустимым расписаниям k первых работ {1,..., k}.

Алгоритм «Динамическое программирование» Input ( J={1,..., n}, p: J Z + ) 1) Положим V 0 ={[0,0]}, i=0. 2) While i n do: для каждого вектора [x,y] V i добавить вектора [x + p i,y] и [x,y + p i ] в V i+1 ; для каждого вектора [x,y] V i добавить вектора [x + p i,y] и [x,y + p i ] в V i+1 ; i:= i +1; i:= i +1; 3) Найти [x*,y*] V n, который минимизирует величину max [x,y] V n {x,y} Output ([x*,y*])

Трудоемкость алгоритма Координаты всех векторов целые числа от 0 до p sum. Координаты всех векторов целые числа от 0 до p sum. Число различных векторов в V i ограничено (p sum ) 2. Число различных векторов в V i ограничено (p sum ) 2. Общее количество векторов, вычисляемых алгоритмом не превосходит n(p sum ) 2. Общее количество векторов, вычисляемых алгоритмом не превосходит n(p sum ) 2. Трудоемкость алгоритма O(n(p sum ) 2 ). Трудоемкость алгоритма O(n(p sum ) 2 ). Размер входа |I| ограничен O(log(p sum ))=O(ln(p sum )) или O(n log p max ). Размер входа |I| ограничен O(log(p sum ))=O(ln(p sum )) или O(n log p max ). Трудоемкость алгоритма не ограничена полиномом от размера входа! Трудоемкость алгоритма не ограничена полиномом от размера входа!

Как упростить множество векторов? Все вектора соответствуют точкам плоскости в квадрате [0, p sum ]×[0, p sum ]. Все вектора соответствуют точкам плоскости в квадрате [0, p sum ]×[0, p sum ]. Разделим этот квадрат вертикальными и горизонтальными линиями на клетки (квадратики). Разделим этот квадрат вертикальными и горизонтальными линиями на клетки (квадратики). В обоих направлениях линии имеют координаты Δ i, где Δ = 1+ (ε/2n), i = 1, 2, …, K. В обоих направлениях линии имеют координаты Δ i, где Δ = 1+ (ε/2n), i = 1, 2, …, K. K = log Δ (p sum ) = ln(p sum )/ln Δ = ((1+2n )/ε) ln(p sum ) K = log Δ (p sum ) = ln(p sum )/ln Δ = ((1+2n )/ε) ln(p sum )

Отсев векторов Пусть два вектора [x 1,y 1 ] и [x 2,y 2 ] попали в одну клетку. Пусть два вектора [x 1,y 1 ] и [x 2,y 2 ] попали в одну клетку. x 1 /Δ x 2 x 1 Δ и y 1 /Δ y 2 y 1 Δ. x 1 /Δ x 2 x 1 Δ и y 1 /Δ y 2 y 1 Δ. Из каждой клетки, имеющей непустое пересечение с V i, выберем один вектор и добавим его в «урезанное» множество векторов V i #. Из каждой клетки, имеющей непустое пересечение с V i, выберем один вектор и добавим его в «урезанное» множество векторов V i #.

Алгоритм FPTAS Input ( J={1,..., n}, p: J Z + ) 1. Положим V 0 # ={[0,0]}, i=0. 2. While i n do: для каждого вектора [x,y] V i # добавить вектора [x + p i,y] и [x,y + p i ] в V i+1 ; для каждого вектора [x,y] V i # добавить вектора [x + p i,y] и [x,y + p i ] в V i+1 ; i:= i +1; i:= i +1; Преобразовать V i в V i #. Преобразовать V i в V i #. 3. 3) Найти [x*,y*] V n #, который минимизирует величину max [x,y] V n # {x,y} Output ([x*,y*])

Трудоемкость алгоритма FPTAS Множество векторов в V i # содержит не более одного вектора из каждой клетки. Множество векторов в V i # содержит не более одного вектора из каждой клетки. Всего клеток K 2. Всего клеток K 2. Трудоемкость алгоритма FPTAS O(nK 2 ). Трудоемкость алгоритма FPTAS O(nK 2 ). nK 2 = n ((1+2n )/ε) ln(p sum ) 2 nK 2 = n ((1+2n )/ε) ln(p sum ) 2 Алгоритм FPTAS – полиномиален от размера входа и 1/ε. Алгоритм FPTAS – полиномиален от размера входа и 1/ε.

Оценка на вектора в V i и V i # Для каждого вектора [x,y] V i существует вектор [x #,y # ] V i #, такой что x # Δ i x и y # Δ i y. Для каждого вектора [x,y] V i существует вектор [x #,y # ] V i #, такой что x # Δ i x и y # Δ i y.

Доказательство (по индукции) i =1: (x 1 /Δ x 2 x 1 Δ и y 1 /Δ y 2 y 1 Δ ) i 1 i: Пусть [x,y] V i. Тогда [a,b] V i-1, и либо [x,y]= [a+p k,b], либо [x,y]= [a,b+p k ]. Тогда [a #,b # ] : a # Δ i 1 a, b # Δ i 1 b. Алгоритм FPTAS строит вектор [a # +p k,b # ] и выбирает [α,β], такой что α Δ(a # +p k ) и β Δb #. Имеем α Δ(a # +p k ) Δ i a + Δp k Δ i (a+p k ) =Δ i x и β Δ i y.

Точность алгоритма FPTAS

Заключение Рассмотрели ли мы все приемы? Рассмотрели ли мы все приемы? Конечно, нет! Конечно, нет! Approximation Algorithms for NP-hard problems, ed. D.Hochbaum, PWS Publishing Company, Approximation Algorithms for NP-hard problems, ed. D.Hochbaum, PWS Publishing Company, V. Vazirani Approximation Algorithms, Springer-Verlag, Berlin, V. Vazirani Approximation Algorithms, Springer-Verlag, Berlin, P. Schuurman, G. Woeginger, Approximation Schemes – A Tutorial, chapter of the book Lecture on Scheduling, to appear in P. Schuurman, G. Woeginger, Approximation Schemes – A Tutorial, chapter of the book Lecture on Scheduling, to appear in D. Williamson, D. Shmoys, The Design of Approximation Algorithms, Cambridge UP, D. Williamson, D. Shmoys, The Design of Approximation Algorithms, Cambridge UP, 2011.