УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК

САНКТ-ПЕТЕРБУРГСКИЙ АКАДЕМИЧЕСКИЙ УНИВЕРСИТЕТ –

НАУЧНО-ОБРАЗОВАТЕЛЬНЫЙ ЦЕНТР НАНОТЕХНОЛОГИЙ РАН

На правах рукописи

Диссертация допущена к защите

Зав. кафедрой

“ ” 2012 г.

ДИССЕРТАЦИЯ

НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ

МАГИСТРА

Тема: Приближённые алгоритмы решения перестановочных задач Направление: 010600.68 – Прикладные математика и физика Магистерская программа: “Математические и информационные технологии” Выполнил студент: А. Г. Головнёв (подпись) Руководитель:

к.ф.-м.н. А. С. Куликов (подпись) Рецензент:

к.ф.-м.н. С. И. Николенко (подпись) Санкт-Петербург 2012 г.

Реферат

Работа выполнена на 25 страницах в 2 главах, использован 41 источник.

Лучший известный алгоритм решения задачи о коммивояжёре имеет время работы O (2n ), используя память O (2n ) (O (·) скрывает полиномиальные множители от длины входа, т.е. poly(n, log M ), где n количество вершин исходного графа, M максимальный вес ребра). Если мы рассматриваем только алгоритмы с полиномиальной памятью, то лучшее решение требует время O (4n nlog n ). Для задачи коммивояжёра с небольшими весами рёбер удобно использовать алгоритм со временем работы O (1.657n ·M ) и памятью O (M ). Открытым вопросом является существование алгоритма со временем работы O (2n ), использующем лишь полиномиальную память. В первой главе работы мы предлагаем алгоритм, который для любого > 0 находит (1 + )-приближение общей ориентированной задачи о коммивояжёре за время O (2n 1 ), используя O (1 ) = 1 · poly(n, log M ) память. То есть, для любого фиксированного, алгоритм за O (2n ) шагов и полиномиальную память находит (1 + )-приближение.

Лучшее приближение задачи о кратчайшей надстроке имеет фактор приближения 2.5. Во второй главе работы мы приедлагаем алгоритм, улучшающий фактор приближения для частного случая задачи о кратчайшей надстроке: для случая, когда длины всех входных строк не превосходят 7.

В частности, алгоритм находит 4/3-приближение задачи о 3-надстроке.

Содержание Содержание................................ Введение................................. Глава 1. Экспоненциальная схема приближения для задачи о коммивояжёре.............................. 1.1 Определения........................... 1.2 Известные результаты..................... 1.3 Идея алгоритма......................... 1.4 Алгоритм включений-исключений............... 1.5 Алгоритм решения метрической задачи коммивояжёра... 1.6 Алгоритм решения общей задачи коммивояжёра...... Глава 2. Полиномиальный приближённый алгоритм для задачи о надстроке.............................. 2.1 Определения........................... 2.2 Известные результаты..................... 2.3 Идея алгоритма......................... 2.4 Алгоритм............................. Заключение................................ Список литературы........................... Введение В работе рассматриваются приближённые алгоритмы решения перестановочных задач. Многие NP-трудные задачи (например, задача выполнимости булевой формулы, задача о вершинном покрытии, задача о покрытии множествами) имеют множество кандидатов на решение размера 2n. Но даже для некоторых из перечисленных задач неизвестны алгоритмы со временем работы меньше 2n. Перестановочные задачи это задачи, кандидаты на решение которых имеют размер порядка n!. Интересно, что для многих перестановочных задач можно получить алгоритмы со временем работы 2n.

В данной работе мы рассматриваем следующие перестановочные задачи: задача коммивояжёра и задача о кратчайшей надстроке. Эти задачи имеют как практический, так и теоретический интерес. Задача коммивояжёра широко используется в логистике, планировании, производстве интегральных схем. Задача о кратчайшей надстроке долгое время рассматривалась применительно к области биоинформатики. Также кратчайшие надстроки используются для эффективного хранения информации о графах.

Для точного решения задачи коммивояжёра известны алгоритмы, использующие • время O (2n ) и память O (2n );

• время O (2n · M ) и память O (M );

• время O (4n nlog n ) и полиномиальную память.

Открытым вопросом является существование точного алгоритма решения задачи коммивояжёра со временем O (2n ), использующем лишь полиномиальную память. В первой главе этой работы получим промежуточный результат. Мы покажем, что для любого фиксированного, за время O (2n ) и полиномиальную память может быть найдено (1+)-приближение общей задачи о коммивояжёре. Этот результат интересен ещё и тем, что в предположении P=NP, общая задача о коммивояжёре не может быть приближена за полиномиальное время с любым полиномиально вычислимым фактором. Более того, если P=NP, даже метрическая версия задачи о коммивояжёре не может быть приближена с любой точностью за полиномиальное время.

Обе исследуемые задачи являются NP-трудными. Следовательно, маловероятно существование полиномиальных алгоритмов точного решения задач. В связи с этим изучаются полиномиальные алгоритмы приближённого решения задачи коммивояжёра и задачи о кратчайшей надстроке.

Лучшее известное приближение задачи о кратчайшей надстроке имеет фактор приближения 2.5. Во второй главе мы предложим полиномиальный по времени приближённый алгоритм решения для задачи о кратчайшей k-надстроке. Задача о кратчайшей k-надстроке принимает на вход строки длины k. Новый алгоритм улучшает известные приближения для задачи о k-надстроке для k < 8. В частности, алгоритм находит 4/3приближение задачи о 3-надстроке.

Глава 1. Экспоненциальная схема приближения для задачи о коммивояжёре Гамильтонов цикл графа это цикл, проходящий по каждой вершине графа ровно один раз. Задача коммивояжёра (ЗК) заключается в поиске гамильтонова цикла минимального веса в полном графе с целыми неотрицательными весами рёбер. Метрическая задача коммивояжёра задача коммивояжёра на графах, удовлетворяющих неравенству треугольника. Ориентированная (асимметрическая) задача коммивояжёра это задача коммивояжёра на ориентированных графах.

Обозначим через n количество вершин исходного графа, а через максимальный вес ребра. O (·) скрывает полиномиальные множиM тели от длины входа, т.е. poly(n, log M ). Вес оптимального гамильтонова цикла в графе G обозначим через OPT(G). Мы будем опускать G в данной нотации, если из контекста будет понятно, с каким графом мы работаем.

Наша цель по заданному найти гамильтонов цикл длины не больше, чем (1 + )OPT(G).

Точные алгоритмы Bellman [1], Held и Karp [2] разработали алгоритм динамического программирования для ЗК. Этот алгоритм использует память и время O (2n ) и до сих пор является самым быстрым алгоритмом решения общей задачи о коммивояжёре. Лучший известный алгоритм с полиномиальной памятью имеет время работы O (4n nlog n ) (Gurevich и Shelah [3], Bjrklund и Husfeldt [4]).

Koivisto и Parviainen [5] показали, что ЗК может быть решена за время O (22nt nlog(nt) ) и память O (2t ) для любого t = n, n/2, n/4.... Также авторы предложили алгоритм, который для любого 2 < S < 2 решает ЗК за O (T n ) шагов и O (S n ) память, так что T S < 4.

Kohn, Gottlieb и Kohn [6], Karp [7], Bax и Franklin [8] предложили алгоритм для ЗК со временем работы O (2n · M ) и памятью O (M ), где максимальный вес ребра. Bjrklund [9] разработал алгоритм Монтеo Карло со временем работы O (1.657n · M ) и экспоненциально маленькой вероятностью ошибки.

Даже для частного случая ЗК метрической задачи коммивояжёра неизвестны лучшие точные алгоритмы решения. Открытым вопросом является существование алгоритма со временем работы O (2n ) = 2n · poly(n, log M ) и полиномиальной памятью (см Open Problem 2.2.b, Woeginger [10]).

Eppstein [11] предложил алгоритм для ЗК в кубических графах со временем работы 1.260n, для графов степени 4 со временем работы 1.890n. Iwama и Nakashima [12] улучшили оценку для кубических графов до 1.251n. Gebauer [13] разработал алгоритм для графов степени 4 со временем работы 1.733n и экспоненциальной памятью.

Bjrklund, Husfeldt, Kaski и Koivisto [14] разработали алгоритм со временем работы O(2 )n для ЗК в графах ограниченной степени (здесь зависит только от степени графа).

Для неориентированной версии задачи о гамильтоновом цикле (ГЦ) оценка O (2n ) была улучшена. Bjrklund [9] предложил алгоритм, решаo ющий ГЦ за время O (1.657n ), используя лишь полиномиальную память.

Более того, предложенный алгоритм решает задачу ГЦ на двудольных графах за время O (2n/2 ).

Приближённые алгоритмы Общая задача коммивояжёра Известно, что в предположении P= NP, общая ЗК не может быть приближена с любым полиномиально вычислимым фактором (Sahni и Gonzalez [15]).

Задача называется сильно NP-трудной, если она остаётся NPтрудной, даже когда все её числовые параметры ограничены многочленом от длины входа (Garey и Johnson [16]). Если P=NP, сильно NP-трудные задачи не имеют FPTAS (Vazirani [17]). ЗК и метрическая ЗК являются сильно NP-трудными задачами (см., например, Garey и Johnson [18]).

Неориентированная метрическая задача коммивояжёра Существует 2-приближающий алгоритм для метрической ЗК (Rosenkrantz, Stearns и Lewis [19]). Лучшее известное приближение 3/2 получено Christodes [20].

Papadimitriou и Vempala [21]: если P=NP, неориентированная метрическая ЗК не может быть приближена за полиномиальное время с точностью лучше, чем 116.

Ориентированная метрическая задача коммивояжёра Frieze, Galbiati, Maoli [22] показали, что ориентированная версия метрической ЗК может быть приближена с фактором log n, Blser [23] улучшил оценa ку до 0.999 log2 n. Kaplan, Lewenstein, Shafrir и Sviridenko [24] разработали 4/3 log3 n-приближение. Feige и Singh [25] предложили 2/3 log2 nприближение. Недавно Asadpour, Goemans, Madry, Gharan и Saberi [26] улучшили фактор приближения до O(log n/ log log n).

Papadimitriou и Vempala [21] доказали, что если P=NP, то ориентированная метрическая ЗК не может быть приближена за полиномиальное время с точностью лучше, чем Другие частные случаи Полиномиальная приближённая схема (PTAS) это алгоритм, который для любого фиксированного за полиномиальное время находит решение, не превосходящее (1+)OPT, где OPT оптимальное решение задачи. Полностью полиномиальная приближённая схема (FPTAS) это полиномиальная приближённая схема, время работы которой полиномиально зависит от n и 1. Для евклидовой версии ЗК найдена полиномиальная схема приближений (Arora [27] [28], Mitchell [29]).

Gharan, Saberi и Singh [30] разработали приближённый алгоритм с фактором 3/2 для графической версии ЗК. Mmke, Svensson [31] приo вели 1.461-приближение для графической ЗК. Mucha [32] улучшил фактор приближения до 1.444.

(1,2)-ЗК неориентированная задача коммивояжёра на графах, в которых веса всех рёбер равны 1 или 2. Даже этот случай задачи является MAX-SNP-трудным (Papadimitriou, Yannakakis [33]). Berman и Karpinski [34] разработали полиномиальный алгоритм, приближающий эту задачу с фактором 8/7.

Bourgeois, Escoer и Paschos [35] предложили следующие экспоненциальные (1 + )-приближения метрической версии ЗК:

• за время O (4(1/2)n nlog n ) и полиномиальную память для любого • за время O (2(1/2)n ) и экспоненциальную память для любого Мы предлагаем алгоритм, который для любого фиксированного использует O (2n ) шагов и полиномиальную память для вычисления (1+)приближения общей ориентированной задачи коммивояжёра. Как было указано выше, лучшее известное полиномиальное приближение даже для неориентированной метрической версии ЗК 1.5 (для ориентированной O( log log n )). Если P=NP, то за полиномиальное время не может быть найдеlog n но 116 -приближение неориентированной метрической ЗК (см. раздел 1.2).

Если нам необходимо, например, 1000 -приближение, то мы должны использовать точные алгоритмы, которые требуют либо экспоненциальную память, либо время 4n nlog n. Экспоненциальные алгоритмы редко используются на практике, но в любом случае, мы способны их запустить и ждать ответа. Однако если алгоритм использует экспоненциальную память, то мы не имеем возможности даже запустить алгоритм на входах разумного размера. Предложенный алгоритм может найти 1001/1000-приближение общей ЗК за время O (2n ), используя лишь полиномиальную память.

Разработанный алгоритм использует идею, предложенную для построения полностью полиномиальной приближённой схемы для задачи о рюкзаке в работе Ibarra, Kim [36]. Авторы используют псевдополиномиальный алгоритм для задачи о рюкзаке, работающий время O(nW ), где количество предметов, W вместимость рюкзака. Полностью поn линомиальная схема приближения задачи о рюкзаке сначала делит веса всех предметов на (, n, W ), затем вызывает псевдополиномиальный алгоритм. Полученный ответ может не оказаться оптимальным, т.к. некоторые веса не просто поделены на, но и округлены. Однако простой анализ показывает, что округление не сильно сказывается на результате.

Мы используем похожую идею. Через OPT обозначим оптимальное рещение ЗК. Для того, чтобы получить полиномиальный по памяти приближённый алгоритм, мы сначала разделим веса всех рёбер на достаточно большое число, затем запустим точный алгоритм, основанный на формуле включений-исключений. Время работы полученного алгоритма будет равно 2n · OPT/ и длина полученного цикла будет не больше OPT + n.

OPT OPT

версия ЗК может быть приближена за полиномиальное время, то есть, мы можем найти, что OPT OPT · log n и взять = n log n. Тогда полученный алгоритм будет иметь время работы O (2n 1 ) и использовать O (1 ) памяти. Для неметрического случая задачи мы сначала находим 4-приближение за экспоненциальное время, а после запускаем описанный алгоритм.

Сравнивая предложенный алгоритм с алгоритмом из работы Boria et al. [35], отметим, что для любого фиксированного > 0, алгоритм Boria либо требует экспоненциальную память, либо имеет время выполнения O (cn ), где c > 2.

1.4. Алгоритм включений-исключений Алгоритм включений-исключений основан на следующей хорошо известной формуле (доказательство может быть найдено, например, в Bax [37]).

Теорема 1.1. Пусть X конечное множество, f, g функции, определённые на всех подмножествах X. Если для любого A X выполняется то для любого A X Например, для проверки существования в графе G(V, E) гамильтонова пути из вершины s в вершину t за время O (2n ) и полиномиальную память, можно определить для A V, f (A) как количество путей (не обязательно простых) длины n 1, проходящих по всем вершинам из A. Тогда f (V ) равно количеству гамильтоновых путей из s в t. Легко видеть, что количество путей (не обязательно простых) длины n 1, проходяg(A) щих только по вершинам из A. Осталось заметить, что g(A) может быть посчитано за полиномиальное время (динамическим программированием или возведением матрицы смежности, индуцированной A, в степень n 1).

Обычно работы Kohn, Gottlieb and Kohn [6], Karp [7], Bax and Franklin [8] цитируются как алгоритмы со временем работы O (2n · M ), использующие O(n · M + n2 ) память, где M максимальнй вес ребра. Для начала нам необходимо показать, что время работы алгоритма включений-исключений может быть оценено как O (2n · OPT), а память как O(n · OPT + n2 ).

Задача распознавания для ЗК может быть сформулирована следующим образом: по параметру k необходимо определить, существует ли в данном графе G гамильтонов цикл длины k. Мы покажем, что задача распознавания может быть решена за время O (2n k) = 2n k · poly(n) и память O (k) = k · poly(n).

За c(U ) обозначим количество циклов в U V длины k, содержащих ровно n рёбер. Отметим, что c(U ) может быть вычислено динамическим программированием за время O(kn4 ) и память O(kn2 ) (можно заполнить таблицу D размера n k, где D[v, j] количество путей длины j, заканчивающихся в вершине v).

Алгоритм 1 InclExcl-Decision-TSP решение задачи распознавания для ориентированной ЗК за время O (2n k) и память O (k).

Input: G = (V, E) полный взвешенный ориентированный граф, k параметр задачи распознавания.

Output: количество гамильтоновых путей длины k.

Корректность алгоритма InclExcl-Decision-TSP следует из (1.1).

O (k).

Бинарный поиск по параметру k даёт следующий алгоритм (InclExcl-TSP) решения оптимизационной версии ориентированной ЗК.

Лемма 1.1. Алгоритм InclExcl-TSP решает ориентированную ЗК за время O (2n · OPT) и память O (OPT).

Доказательство. Мы используем двоичный поиск для поиска такого мирешение ориентированной ЗК за время O (2n ·OPT) и память O (OPT).

Алгоритм 2 InclExcl-TSP Input: G = (V, E) полный взвешенный ориентированный граф.

Output: длина кратчайшего гамильтонова цикла.

установить k = 1 и удваивать k, пока InclExcl-Decision-TSP(G, k)= использовать двоичный поиск на полученном интервале для нахождения минимального такого k, что InclExcl-Decision-TSP(G, k)> нимального k, что алгоритм InclExcl-Decision-TSP возвращает положительное количество циклов. Нам необходимо O(log OPT) вызовов InclExcl-Decision-TSP с параметром k 2OPT, а O(log OP T ) полиномиально от длины входа. Следовательно, время работы составляет Замечание 1.1. Алгоритм InclExcl-TSP был предложен в работе Karp [7]. Мы лишь подчеркнули, что время работы и использованная память могут быть оценены как O (2n · OPT) и O (OPT), соответственно.

Замечание 1.2. Алгоритм InclExcl-TSP может быть модифицирован для нахождения самого цикла, а не просто установления факта его существования.

1.5. Алгоритм решения метрической задачи Обозначим через Approx-Asym-TSP (log n)-приближающий алгоритм ориентированной метрической задачи коммивояжёра (алгоритмы перечислены в разделе 1.2). Мы предлагаем следующую приближённую схему для ориентированной метрической ЗК.

Лемма 1.2. Алгоритм Approx-Metric-TSP находит цикл длины (1 + )OPT в графе G.

Доказательство. Пусть OPT и OPT длины оптимальных гамильтоновых циклов в графе G до деления весов рёбер на и после, соответственно.

Алгоритм 3 Approx-Metric-TSP память O (1 ).

Parameter: > 0 фактор приближения.

Input: G = (V, E) полный взвешенный ориентированный граф.

Output: гамильтонов цикл веса (1 + )OPT(G).

= Approx-Asym-TSP(G) разделим веса всех рёбер на : w(e) = w(e)/, где return InclExcl-TSP(G) Длина полученного алгоритмом пути RES · OPT. Обозначим через I = (e1,..., en ) рёбра оптимального цикла в исходном графе G. Тогда OPT Из OPT · log n получаем n OPT и RES (1 + ) · OPT.

Лемма 1.3. Время работы алгоритма Approx-Metric-TSP равно Доказательство. Время работы шага 1 полиномиально (см. раздел 1.2).

По Лемме 1.1, время работы шага 7 составляет O (2n · OPT ), а память O (OPT ). Оценка OPT даёт Следовательно, время работы алгоритма Approx-Metric-TSP O (2n 1 ), В предыдущем разделе мы рассматривали только метрическую версию задачи коммивояжёра, т.к. для генерации оценки мы использовали полиномиальный приближённый алгоритм. Сейчас мы избавимся от вызова полиномиального алгоритма и расширим результат на общую задачу коммивояжёра. Единственное отличие алгоритмов состоит в поиске 4приближения общей ЗК за экспоненциальное время (шаги 2-5).

Алгоритм 4 Approx-TSP Parameter: > 0 фактор приближения.

Input: G = (V, E) полный взвешенный ориентированный граф.

Output: гамильтонов цикл длины (1 + )OPT(G).

Пусть граф G получен из G делением всех весов рёбер на : w (e) = w(e)/, где until InclExcl-Decision-TSP(G, 2n) > Разделим все веса рёбер на : w(e) = w(e)/, где return InclExcl-TSP(G) Лемма 1.4. Алгоритм Approx-TSP находит гамильтонов цикл длины (1 + )OPT в графе G.

Доказательство. Нам необходимо показать только то, что шаги 2-5 находят 4-приближение OPT. После мы используем такую же технику, как и в алгоритме Approx-Metric-TSP.

Если G содержит цикл длины 2n, то G содержит цикл длины 2n = 2. Если в G отсутствуют циклы длины 2n, то все циклы в G имеют длину. Действительно, если бы G содержал цикл длины, то G содержал бы цикл длины / + n = 2n.

Следовательно, 2 является 4-приближением OPT.

Лемма 1.5. Время работы алгоритма Approx-TSP O (2n 1 ), память O (1 ).

Доказательство. Время работы шага 5 составляет O (2n ·2n) = O (2n ), память O (2n) = O (1). Количество вызовов InclExcl-Decision-TSP O(log(OPTn)) = poly(n, log M ). По Лемме 1.3, время работы алгоритма Approx-TSP оценивается как O (2n 1 ), память O (1 ).

Глава 2. Полиномиальный приближённый алгоритм для задачи о надстроке Пусть нам задан набор из n строк S = {s1,..., sn } +. Задача о кратчайшей надстроке заключается в поиске строки s наименьшей длины, содержащей каждую si как подстроку. Задача о кратчайшей rнадстроке принимает на вход n строк длины r. Компрессией называется разность сумм длин всех строк |s1 | +... + |sn | и длины кратчайшей надстроки (s1,..., sn ).

Будем называть перекрытием overlap(s, t) строк s и t наибольший суффикс s, который является префиксом t. Например, overlap(ABACBA, BABCA) = BA. Через префикс prex(s, t) обозначим строку, полученную из s вычёркиванием overlap(s, t).

Каждой входной строке поставим в соответствие вершину графа.

Граф перекрытий строится следующим образом: для любых двух вершин s и t, вес дуги (s, t) равен overlap(s, t). Граф префиксов имеет веса, равные prex(s, t) Задача о кратчайшей надстроке является типичной перестановочной задачей: если мы знаем порядок следования исходных строк в оптимальной надстроке, то мы можем восстановить оптимальную надстроку.

Gallant, Maier, Astorer [38] доказали, что задача о кратчайшей 2надстроке может быть решена за полиномиальное время, а задача о кратчайшей 3-надстроке является NP-трудной.

Лучшее известное полиномиальное приближение задачи о надстроке имеет фактор приближения 2.5 (Sweedyk [39]; Kaplan, Lewenstein, Shafrir, Sviridenko [24]). Задача о компрессии может быть приближена с фактором 2/3 (Kaplan, Lewenstein, Shafrir, Sviridenko [24]). Karpinski и Schmied [40] доказали, что в предположении P=NP задача о кратчайшей надстроке не может быть приближена с фактором, меньшим 1.0029, задача о компрессии с фактором 1.0048. Из -приближения задачи о надстроке над бинарным алфавитом следует -приближение задачи о надстроке над любым алфавитом (Vassilevska, [41]).

Можно рассматривать задачу о кратчайшей надстроке, как задачу о кратчайшем гамильтоновом пути в графе префиксов. Также задача о надстроке может быть рассмотрена как задача о максимальном гамильтоновом пути в графе перекрытий. Лучший известный алгоритм решения задачи о надстроке использует алгоритм включений-исключений для задачи о коммивояжёре (Kohn, Gottlieb и Kohn [6]; Karp [7]; Bax и Franklin [8]). Следовательно, задача о кратчайшей надстроке может быть решена за время 2n с использованием лишь полиномиальной памяти.

Открытыми вопросами остаются вопрос о существовании точного алгоритма со временем работы < 2n и о существовании полиномиальногго алгоритма с фактором приближения < 2.5.

В этой главе мы предложим полиномиальный приближённый алгоритм для задачи о кратчайшей k-надстроке. Алгоритм имеет фактор приближения < 2.5 для k < 8.

Отметим, что n + 2 |OPT(S)| 3n (равенства достигаются в случае, когда перекрытия всех строк будут равны 2 и когда оптимальная строка не содержит строк с перекрытиями). Отметим, что в этих двух случаях (OPT(S) = n + 2 или OPT(S) = 3n) решение может быть найдено за полиномиальное время. Действительно, если OPT(S) = n + 2, то S множетво всех подстрок длины 3 какой-то строки длины n + 2. Такая надстрока может быть найдена проходом по эйлерову циклу графа де Брюйна на S, DG(S). С другой стороны, если OPT(S) = 3n, то исходные строки не пересекаются, следовательно, любая их конкатенация даёт оптимальную надстроку.

Заметим, что случай OPT(S) = n + 2 соответствует максимально возможной компрессии, в то время как случай OPT(S) = 3n соответствует минимальной (т.е., нулевой) компрессии.

Алгоритм работает следующим образом. Сначала построим граф перекрытий OG(S) и найдём 2/3-приближение максимального гамильтонова пути в нём. Такой путь даёт хорошее приближение OPT(S) в случае, когда OPT(S) достаточно велико.

Теперь построим граф де Брюйна DG(S). Заметим, что этот граф может рассматриваться как граф де Брюйна набора строк длины 2 над алфавитом 2. А именно, строка ABC представлялась, как ребро из AB в BC. Но это ребро ещё может быть рассмотрено как строка (AB)(BC) длины 2 над новым алфавитом. Теперь мы находим оптимальное решение для построенного набора 2-строк (напомним, что задача о 2-надстроке может быть решена за полиномиальное время) и перейдём от решения к решению исходной задачи. Это даёт хорошее приближение в случае, когда OPT(S) мало. Мы будем использовать этот приём, когда исходные строки сильно перекрываются. Тогда соответствующие 2-строки также пересекаются сильно и могут быть найдены полиномиальным алгоритмом для задачи о 2-надстроке.

Алгоритм 5 Приближённый алгоритм для задачи о r-надстроке {сначала находим длинный гамильтонов путь в графе перекрытий} пусть Sn это 2/3-приближение максимального гамильтонова пути в графе OG(S) {теперь находим короткий путь задачи о деревенском почтовом в графе де Брюйна} пусть S = {s1,..., sn } 2 множество 2-строк над алфавитом 1 = r1 ; si 2-строка, состоящая из префикса si длины r 1 и суффикса si длины r 3: найдём 1 Sn оптимальное решение задачи о 2-надстроке для S 4: return лучшее из решений и Теорема 2.1. Алгоритм 5 находит (r)-приближение задачи о rнадстроке, где Доказательство. Пусть H оптимальный гамильтонов путь в графе OG(S). Тогда 2/3-приближение максимального гамильтонова пути имеет вес 2w(H)/3.

Следовательно, перестановка даёт надстроку длины rn 2w(H)/3.

Соответствующий фактор приближения:

Пусть u обозначает количество рёбер веса (r 2) в H. Тогда количество рёбер в H веса ровно (r 1) равно (n u). Получаем w(H) (r 1)(n u) + (r 2)u и, следовательно, Тогда длина оптимальной надстроки для S имеет длину n + u. Следовательно, 1 даёт надстроку длины не больше, чем rn (r 1)(n u) для S. Из (2.2), это не больше Соответствующий фактор приближения:

Теперь теорема следует из (2.1), (2.3) и 0 w(H)/n (r 1).

Следствие 2.1. Алгоритм 5 находит 4/3-приближение 3-надстроки, 8/5приближение для 4-надстроки, 13/7-приближение для 5-надстроки.

Доказательство. Это следует из несложных вычислений. Рис. 2.1 демонстрирует графики рассматриваемых функций.

Заключение В данной работе предложены следующие алгоритмы:

• (1+)-приближение общей ЗК за время O (2n 1 ) и память O (1 );

• полиномиальное по времени 4/3-приближение для задачи о 3надстроке;

• алгоритм, имеющий фактор приближения < 2.5 для задачи о kнадстроке для k < 8.

Дальнейшие направления исследования включают в себя следующие задачи:

• разработать точный алгоритм для ЗК со временем работы O (2n ), использующий лишь полиномиальную память;

• разработать полиномиальный приближённый алгоритм для задачи о надстроке с фактором приближения < 2.5;

• разработать алгоритм решения задачи о надстроке со временем работы < 2n.

Список литературы [1] Richard Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. J. ACM, 9:61–63, January 1962.

[2] Michael Held and Richard M. Karp. The Traveling-Salesman Problem and Minimum Spanning Trees.

Mathematical Programming, 1:6–25, 1971.

[3] Yuri Gurevich and Saharon Shelah. Expected computation time for Hamiltonian path problem. SIAM J. Comput., 16:486–502, June 1987.

[4] Andreas Bjrklund and Thore Husfeldt. Exact Algorithms for Exact Satisability and Number of Perfect Matchings. Algorithmica, 52:226–249, 2008.

[5] Mikko Koivisto and Pekka Parviainen. A space-time tradeo for permutation problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 484–492, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics.

[6] Kohn, Samuel and Gottlieb, Allan and Kohn, Meryle. A generating function approach to the traveling salesman problem. In Proceedings of the 1977 annual conference, ACM ’77, pages 294–300, New York, NY, USA, 1977.

[7] Richard M. Karp. Dynamic Programming Meets the Principle of Inclusion and Exclusion. Operations Research Letters, 1(2):49 – 51, 1982.

[8] Eric Bax and Joel Franklin. A Finite-Dierence Sieve to Count Paths and Cycles by Length. Inf.

Process. Lett., 60:171–176, November 1996.

[9] Andreas Bjrklund. Determinant Sums for Undirected Hamiltonicity. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS’10, pages 173–182, Washington, DC, USA, 2010. IEEE Computer Society.

[10] Gerhard J. Woeginger. Open Problems Around Exact Algorithms. Discrete Appl. Math., 156:397–405, February 2008.

[11] David Eppstein. The traveling salesman problem for cubic graphs. In Frank Dehne, Jorg-Rudiger Sack, and Michiel Smid, editors, Algorithms and Data Structures, volume 2748 of Lecture Notes in Computer Science, pages 307–318. Springer Berlin / Heidelberg, 2003.

[12] Kazuo Iwama and Takuya Nakashima. An improved exact algorithm for cubic graph tsp. In Guohui Lin, editor, Computing and Combinatorics, volume 4598 of Lecture Notes in Computer Science, pages 108–117. Springer Berlin / Heidelberg, 2007.

[13] Heidi Gebauer. Finding and enumerating hamilton cycles in 4-regular graphs. Theoretical Computer Science, 412(35):4579–4591, August 2011.

[14] Andreas Bjrklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The Travelling Salesman Problem in Bounded Degree Graphs. In Luca Aceto, Ivan Damgard, Leslie Goldberg, Magnus Halldorsson, Anna Ingolfsdottir, and Igor Walukiewicz, editors, Automata, Languages and Programming, volume 5125 of Lecture Notes in Computer Science, pages 198–209. Springer Berlin / Heidelberg, 2008.

[15] Sartaj Sahni and Teolo Gonzalez. P-Complete Approximation Problems. J. ACM, 23:555–565, July [16] M. R. Garey and D. S. Johnson. “Strong” NP-Completeness Results: Motivation, Examples, and Implications. J. ACM, 25:499–508, July 1978.

[17] Vijay V. Vazirani. Approximation Algorithms. Springer, 2003.

[18] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

[19] Daniel J. Rosenkrantz, Richard Edwin Stearns, and Philip M. Lewis. An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput., 6(3):563–581, 1977.

[20] N Christodes. Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem. Technical Report 338, Graduate School of Industrial Administration, CMU, 1976.

[21] Christos Papadimitriou and Santosh Vempala. On The Approximability Of The Traveling Salesman Problem. Combinatorica, 26:101–120, 2006.

[22] A. M. Frieze, G. Galbiati, and F. Maoli. On the Worst-Case Performance of Some Algorithms for the Asymmetric Traveling Salesman Problem. Networks, 12(1):23–39, 1982.

[23] Markus Blser. A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’03, pages 638–645, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics.

[24] Haim Kaplan, Moshe Lewenstein, Nira Shafrir, and Maxim Sviridenko. Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. J. ACM, 52:602–626, July 2005.

[25] Uriel Feige and Mohit Singh. Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. In Moses Charikar, Klaus Jansen, Omer Reingold, and Jose Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 4627 of Lecture Notes in Computer Science, pages 104–118. Springer Berlin / Heidelberg, 2007.

[26] Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi.

An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, pages 379–389, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics.

[27] Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. In In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS’96), pages 2–11, 1996.

[28] Sanjeev Arora. Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. In In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS’97), pages 554–563, 1997.

[29] Joseph S. B. Mitchell. Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems. SIAM J. Comput., 28:1298–1309, March 1999.

[30] Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A Randomized Rounding Approach to the Traveling Salesman Problem. In FOCS, pages 550–559, 2011.

[31] Tobias Mmke and Ola Svensson. Approximating Graphic TSP by Matchings. In FOCS, pages 560–569, [32] Marcin Mucha. Improved Analysis for Graphic TSP Approximation via Matchings. CoRR, abs/1108.1130, 2011.

[33] Christos H. Papadimitriou and Mihalis Yannakakis. The Traveling Salesman Problem with Distances One and Two. Math. Oper. Res., 18:1–11, February 1993.

[34] Piotr Berman and Marek Karpinski. 8/7-approximation Algorithm for (1,2)-TSP. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, SODA ’06, pages 641–648, New York, NY, USA, 2006. ACM.

[35] N. Boria, N. Bourgeois, B. Escoer, and V. Th. Paschos. Exponential approximation schemata for some network design problems. Cahier du LAMSADE 303, LAMSADE, Universite Paris-Dauphine, 2011.

[36] Oscar H. Ibarra and Chul E. Kim. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. J. ACM, 22:463–468, October 1975.

[37] Eric T. Bax. Recurrence-Based Reductions for Inclusion and Exclusion Algorithms Applied to #P Problems. 1996.

[38] John Gallant, David Maier, and James A. Storer. On nding minimal length superstrings. Journal of Computer and System Sciences, 20(1):50 – 58, 1980.

[39] Z. Sweedyk. A 2 1 -approximation algorithm for shortest superstring. SIAM J. Comput., 29(3):954–986, December 1999.

[40] Marek Karpinski and Richard Schmied. Improved lower bounds for the shortest superstring and related problems. CoRR, abs/1111.5442, 2011.

[41] Virginia Vassilevska. Explicit inapproximability bounds for the shortest superstring problem. In Joanna Jedrzejowicz and Andrzej Szepietowski, editors, Mathematical Foundations of Computer Science 2005, volume 3618 of Lecture Notes in Computer Science, pages 793–800. Springer Berlin / Heidelberg, 2005.