Задачи аппроксимации графов и наследственных систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л. СОБОЛЕВА

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

005049655

НАВРОЦКАЯ Анна Александровна

ЗАДАЧИ АППРОКСИМАЦИИ ГРАФОВ И НАСЛЕДСТВЕННЫХ СИСТЕМ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 л ФЕЗ 2013

Новосибирск - 2013

005049655

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского».

Научный руководитель: доктор физико-математических наук

Ильев Виктор Петрович.

Официальные оппоненты: доктор физико-математических наук

Пяткин Артём Валерьевич,

Ведущая организация: ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»

Защита, состоится 28 февраля 2013 г. в 15 часов на заседании диссертационного совета Д 003.015.01 при Учреждении Российской академии наук Институт математики им. С.Л. Соболева СО РАН (630090, Новосибирск, пр. академика Коптюга, 4).

С диссертацией можно ознакомиться в библиотеке Института математики им. С.Л. Соболева СО РАН.

кандидат физико-математических наук Соколовский Мирон Наумович.

Автореферат разослан

2013 г.

Ученый секретарь диссертационного совета д. ф.-м. н.

Ю.В. Шамардин

Общая характеристика работы

Актуальность темы. Задачи аппроксимации графов являются адекватными моделями имеющих широкие приложения задач кластеризации и классификации взаимосвязанных объектов, а наследственными системами являются множества допустимых решений большого числа сложных практически важных задач. Задачи аппроксимации графов и наследственных систем в общем случае относятся к классу ЫР-трудных, поэтому актуальным направлением исследований является разработка алгоритмов приближенного решения этих задач и получение гарантированных оценок точности алгоритмов. В последнее десятилетие исследования указанных задач активно ведутся в России и за рубежом.

Цель работы. Целью настоящей диссертации является исследование различных вариантов задачи аппроксимации графа и ее обобщений — задач аппроксимации наследственных систем, а также разработка и анализ приближенных алгоритмов решения этих задач.

Методы исследований. При выполнении работы использовались методы теории графов, теории матроидов, дискретной оптимизации, методы анализа алгоритмов в худшем случае.

Научная новизна. В диссертационной работе предложены новые полиномиальные алгоритмы приближенного решения различных вариантов задачи аппроксимации графа. Получены гарантированные оценки точности предложенных алгоритмов. Исследованы различные постановки более общей задачи аппроксимации наследственных систем, найдены оценки аппроксимационной сложности наследственных систем. Рассмотрена новая постановка задачи аппроксимации графа. Доказано, что в общем случае эта задача является ЛгР-трудной, найдены полиномиально разрешимые случаи.

Основные результаты. 1. Для задачи аппроксимации графами, имеющими не более к компонент связности, предложен алгоритм локального улучшения. Для любого фиксированного к ^ 2 доказано, что алгоритм локального улучшения гарантированно асимптотически точен на семействе неплотных графов. На основе этого алгоритма построена полиномиальная приближенная схема решения задачи на неплотных графах. Для задачи аппроксимации графами, имеющими ровно 2 компоненты связности, предложен приближенный алгоритм с достижимой гарантированной оценкой точности.

2. Для задачи аппроксимации линейной наследственной системы, являющейся обобщением задачи аппроксимации графа, доказана достижи-

мая оценка аппроксимационной сложности. Исследованы другие постановки задачи аппроксимации наследственных систем, связанные с оптимизационными задачами. Для двух вариантов задачи получены оценки аппроксимационной сложности наследственных систем, которые можно рассматривать как гарантированные оценки точности алгоритмов приближенного решения задач о максимальном независимом и о минимальном зависимом множестве наследственной системы.

3. Рассмотрена новая постановка задачи аппроксимации графами с компонентами связности ограниченного размера. Выделены полиномиально разрешимые случаи. Доказано, что задача аппроксимации графами, мощности компонент связности которых не превосходят р, является ЛгР-трудной для любого фиксированного р ^ 3. Для случая р = 3 предложен алгоритм приближенного решения задачи и получена гарантированная оценка его точности.

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

Апробация работы. Основные результаты диссертации докладывались на Ш-У Всероссийских конференциях «Проблемы оптимизации и экономические приложения» (Омск, 2006, 2009, 2012); 39-й Всероссийской молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 2008); VIII Международной научной конференции «Дискретные модели в теории управляющих систем» (Москва, 2009); X Международном семинаре «Дискретная математика и ее приложения» (Москва, 2010); XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2011), а также на научных семинарах в Омском государственном университете им. Ф.М. Достоевского, в Институте математики им. С. Л. Соболева СО РАН и его Омском филиале..

Публикации. По теме диссертации автором опубликовано 14 научных работ, из них 3 в рецензируемых изданиях из списка ВАК. Конфликта интересов с соавторами нет, в совместных работах соискателю принадлежат идеи доказательств результатов, включенных в диссертацию.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 59 наименований, Общий объем работы 90 страниц.

Содержание работы

Во введении обосновывается актуальность темы диссертации, формулируется цель исследования, приводится обзор известных результатов, посвященных рассматриваемым задачам.

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

Параграф 1.1 содержит необходимые определения, постановки задач аппроксимации графов и краткий обзор известных результатов.

Будем рассматривать обыкновенные графы, т. е. графы без петель и кратных ребер. Граф называется М-графом, если каждая его компонента связности является полным графом. Обозначим через М(У) класс всех М-графов на множестве вершин V, Л4к(У) — класс всех М-графов на множестве V, имеющих к непустых компонент связности, МКк{У) — класс всех М-графов на множестве V, имеющих не более к компонент связности, 2 < к ^ |У|.

Если С\ = (V, Ег) и Ст2 ~ (У,Е2) — помеченные графы на одном и том же множестве вершин V, то расстояние /9(61,62) между ними определяется как р{Оъ <32) = \ЕгАЕ2\ = ¡ЯДДгМ^Яг!, т. е. р(Съ С2) равно числу несовпадающих ребер в графах и

В литературе рассматривались три варианта задачи аппроксимации графа.

Задача А. Для произвольного графа <3 = (V, Е) найти такой граф М- е М(У), что /?(<?, М*) = шш р{0, М) т(<3).

МеМ{У)

Задача Ак. Дан граф С = (V, Е) и целое.число к, 2 < к < \У\. Найти такой граф М* е Мк(У), что р(в, М%) = шп М) тк{в).

МеМк(У)

Задача А.-^ формулируется аналогично.

Все варианты задачи аппроксимации графов являются АГР-трудными [1, 7, 9, 17].

В 2004 г. Бансал, Блюм и Чаула [9] предложили простой 3-приближен-ный алгоритм для задачи А^2- В 2006 г. Агеев, Ильев, Кононов и Та-левнин [1] доказали существование рандомизированной полиномиальной приближенной схемы для задачи а Гиотис и Гурусвами [14] предложили рандомизированную полиномиальную приближенную схему для задачи А^к (для любого фиксированного к > 2). В том же году Навроцкая, Ильев и Талевнин [5, 6] показали, что алгоритм локального поис-

ка является гарантированно асимптотически точным для задачи А<;2 на семействе неплотных графов. Указав, что сложность полиномиальной приближенной схемы из [14] лишает ее перспективы практического использования, Коулман, Сандерсон и Вирт [12] в 2008 г. предложили 2-приближенный алгоритм для задачи А<2, применив процедуру локального поиска к допустимому решению, полученному с помощью 3-приближенного алгоритма из статьи [9].

Основными результатами главы 1 являются доказательство того, что алгоритм локального поиска есть гарантированно асимптотически точный алгоритм решения задачи А<к на неплотных графах, и 3-прибли-женный алгоритм для задачи А2.

Рассмотрим следующую эквивалентную постановку задачи Ask-Для данного графа G = {V,E) найти разбиение Р = (Vb V2,Vk) множества V, на котором достигает минимума функция f{P) = |{uv <£E:u,veVi,i£ {1, ...,Ä}}| + +\{uv е Е -.ueVi.v eVj,ie {l,..., k - l},j e {»' +1, -, ft}}|-Какие-то из множеств Vi, V2,..., Vk могут быть пустыми.

Очевидно, что f(P) = p(G,M), где М - М-граф с компонентами связности, порожденными множествами Vi, У2, •••, Vk-

Обозначим Ng(v) — {u&V \ uv е Е}, a NG{v) = V\ (NG{v) и {и}). Каждой вершине v € V графа G и разбиению Р = (Vi, ■■■,Vk) поставим в соответствие величины:

bi{v, Р) = \Na(v) П (V \ Ví)| + | Ng{v) пЩ, i el,...,k. Заметим, что bi(v,P) — это вклад вершины v в целевую функцию при помещении v в V¿.

В параграфе 1.2 для приближенного решения задачи А<к предложен следующий вариант алгоритма локального поиска. На каждом шаге алгоритм выбирает вершину и перемещает ее в соответствующую компоненту так, чтобы уменьшалось значение целевой функции.

Алгоритм локального улучшения L. Шаг О. Положим Vi = V, V2 = V3 = ... = Vk = 0 и определим разбиение P = P(V1,V2,...,Vk).

Шаг s (s ^ 1). Выберем два номера р, q и вершину v 6 Vp такие, что bp{v,P)-bq(v,P) = тазе (6¿(u, Р) - b¡{u, Р)).

иеЦ

Если bp(v, Р) - bq(v, Р) > 0, то полагаем VP = VP\ {«}, Vq = VqU {и} и переходим на шаг s + 1, иначе конец алгоритма.

Пусть Оп — семейство п-вершинных графов. Графы семейства бп назовем неплотнъши, если для любого графа С? = (V, Е) этого семейства |2?| ^ где а, ¡3 — некоторые константы, а > 0, 0 < /3 < 2.

Для исследования качества алгоритма Ь на семействе неплотных графов применена идея алгоритмов с оценками [3].

Теорема 1.2. При любом к ^ 2 для решения Р задачи А^к на произвольном неплотном графе С? € Яп, полученного алгоритплюм Ь, справедлива оценка:

(4ап0 + п)(к - I)4

где Р* — оптимальное решение задачи Аф. Очевидно, что (4an0

+ п)(к - 1 )/(п2 - 2kocnß - кп) —> 0 при п —¥ оо

и фиксированном к ^ 2.

Следствие 1.1. Для любого фиксированного к ^ 2 алгоритм локального улучшения является гарантированно асимптотически точным алгоритмом решения задачи Аф на неплотных графах.

В параграфе 1.3 предложен алгоритм приближенного решения задачи А2 с достижимой оценкой точности. Будем считать, что G ф Кп, так как для Кп задача А2 решается аналитически. Алгоритм N.

Шаг 1. Для каждой вершины и € V определим М-граф Ми G M^iV) следующим образом: вершина и и все смежные с ней вершины графа G принадлежат одной компоненте связности графа Ми, а все несмежные с и вершины —другой компоненте.

Шаг 2. Среди всех графов Ми выберем такой граф М' € Л^К), что

p(G,M')= min p(G,Mu). ueV: MueM2(V)

Шаг 3. Пусть w G V — вершина минимальной степени в графе G. Определим М-граф М" е вершина w принадлежит одной компоненте связности графа М", а все оставшиеся вершины — другой компоненте. Если p(G, М') < p(G, М"), то MN = М', иначе MN = М". Конец алгоритма.

Теорема 1.4. Пусть п ^ 3. Тогда для любого п-вершинного графа p(G,MN) ^ ( 3--) p(G, М*),

\ 71 /

где М* 6 Л42(У) — оптимальное решение задачи Аг на графе (7, а Мн — решение, полученное алгоритмом N.

Замечание 1.1. Существует бесконечное семейство графов {£?„} (п — число вершин графа Сп, п = 4г + 2, г = 2,3,...) такое, что

p(Gn, MN) = (3 - M*)>

m. е. гарантированная оценка точности алгоритма N достижима.

Результаты параграфа 1.3 получены совместно с В.П. Ильевым и С.Д. Ильевой.

В главе 2 рассматриваются задачи аппроксимации наследственных систем, являющиеся обобщениями задач аппроксимации графов.

Пусть V — непустое конечное множество. Наследственной системой S на множестве V называется разбиение семейства всех подмножеств V на два непустых непересекающихся семейства А и Т>, где А удовлетворяет следующей аксиоме наследственности: Ai <£ Л, Аг С А^ € А [4, 15]. Очевидно, что семейство V = 2V \ А обладает свойством наследственности «вверх»: Di е Т>, Di С D2 => D2 е V. Множества семейства А называются независимыми, а множества семейства V — зависимыми.

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

max{f(X) :ХеА}, (1)

min {f(X):X&V}, (2)

где / : У -»■ R+, f(X) = ]Г/(х).

хеХ

Базами наследственной системы S называются максимальные по включению независимые, а циклами — минимальные по включению зависимые множества. Семейства всех баз и всех циклов системы S обозначим через В и С, соответственно. Очевидно, что каждое из семейств А, В, С, V однозначно определяет наследственную систему 5, поэтому будем записывать S = {V,A), S = (V,B), S = (V,C) или S = (V,V).

Примером наследственной системы является наследственная система графа SG = (V, AG), где Аа — семейство всех независимых множеств вершин произвольного графа G = (V,E). Циклы этой системы взаимно однозначно соответствуют ребрам графа G.

Произвольной наследственной системе S = (V,C) можно поставить в соответствие гиперграф Hs = (V,E), ребра которого взаимно однозначно соответствуют циклам этой системы. Наоборот, любой гиперграф Н порождает наследственную систему Sh = (V,C#), циклами которой являются минимальные по включению ребра гиперграфа Н. Поэтому

наследственную систему можно отождествлять с гиперграфом, никакое ребро которого не содержит другое ребро в качестве подмножества. Гиперграф Н = (V, Е) называется линейным, если любые два его ребра имеют не более одной общей вершины [И]. Линейный гиперграф будем называть М-гиперграфом, если каждая его компонента связности либо состоит в точности из одного ребра, либо является полным графом.

Наследственная система называется линейной, если соответствующий ей гиперграф линеен. Примером линейной наследственной системы является наследственная система графа.

Частными случаями наследственных систем являются матроиды и ко-матроиды. Эти объекты могут быть определены следующим образом.

Пусть Б = (V, Л) ~ произвольная наследственная система и IV С V. Базой множества IV называется любое максимальное по включению независимое множество, содержащееся в IV. Наследственная система Б называется матроидом, если все базы любого множества IV С V имеют одинаковую мощность. Эквивалентные определения матроида можно найти в книге [2].

Известно [10], что наследственная система графа С = (V, В) является матроидом тогда и только тогда, когда С? — М-граф. Такой матроид называется матроидом разбиения на множестве V.

С каждой наследственной системой Б = (V, Л) связана дополнительная cucme.ua или косистема Б' = (V, Т>'), семейство зависимых множеств которой определяется как V = {V \ А : А е Л}. Наследственная система, дополнительная к матроиду, называется коматроидом.

Примером коматроида является коматроид разбиения — наследственная система, дополнительная к матроиду разбиения М-графа С. Циклами этого коматроида являются вершинные покрытия графа б.

В параграфе 2.2 рассматривается непосредственное обобщение задачи аппроксимации графа — задача аппроксимации линейной наследственной системы. В этой задаче для заданной линейной наследственной системы 5 = (V, С) требуется найти ближайший матроид из класса С(У) всех матроидов на множестве V, являющихся линейными наследственными системами. Мера близости системы Б и матроидов из £(У) определяется как т(Б) = X), где р{Б,Ь) — число несовпадающих

циклов системы Б и матроида Ь. Другими словами, для данного гиперграфа требуется найти ближайший М-гиперграф. Расстояние между гиперграфами равно числу несовпадающих ребер.

В [8] показано, что для любого п-вершинного графа С имеет место

достижимая оценка

(п-1)2

(3)

4

Основной результат параграфа 2.2 — оценка аппроксимационной сложности линейной наследственной системы, аналогичная оценке (3).

Теорема 2.1. Пусть Б = (У, С) - линейная наследственная систе-

ма, = п. Тогда

(п-1)

3

Замечание 2.1. Оценка, доказанная в теореме 2.1, достижима.

В параграфе 2.3 рассмотрены две задачи аппроксимации наследственных систем, постановки которых тесно связаны с оптимизационными задачами (1) и (2). Мера близости наследственных систем в этих задачах понимается как близость оптимальных значений целевых функций оптимизационных задач на наследственных системах.

Как следует из теоремы Радо-Эдмондса [13, 16], задача (1) разрешима жадным алгоритмом, если наследственная система Б является мат-роидом. В связи с этим представляет интерес следующий вопрос: как сильно данная наследственная система отличается от матроида? Этот вопрос приводит нас к задаче матроидной аппроксимации, самая общая постановка которой такова.

Пусть М(У) — некоторый класс матроидов на множестве V. Для заданной наследственной системы Б = (У,Л) найти матроид М & М(У), который является самым близким к системе Б.

Мера близости т(Б) наследственной системы Б и матроидов класса М(У) (аппроксимационная сложность системы Б) может определяться по-разному в различных задачах. Например, пусть М{У) — класс всех матроидов разбиений на множестве V. Определим меру близости наследственной системы 5= (У,А) и матроидов класса М(У) как

ЦОрЬМ) (А)

т(Б) = тах ¿г,

у ' мем(у) ¡{ОрЬБ)

где Ор1Б — оптимальное решение задачи (1) на системе Б, а ОрЬМ — оптимальное решение аналогичной задачи на матроиде М с той же самой

целевой функцией.

Теорема 2.6. Для любой наследственной системы Б = (У, -4)

т(5) >

где А - максимальная степень вершин гиперграфа соответствующего системе Б, а т(Б) определена формулой (4).

Поскольку OptM 6 Л, то оценку аппроксимационной сложности t(S) можно рассматривать как гарантированную оценку точности жадного алгоритма приближенного решения задачи (1).

Для невзвешенной задачи (1) получена оценка аппроксимационной сложности г(5) в терминах средней степени вершин гиперграфа Я?.

В параграфе 2.3 рассмотрена также аналогичная задача аппроксимации наследственной системы коматроидами разбиений, связанная с оптимизационной задачей (2).

Результаты параграфа 2.3 получены совместно с В.П. Ильевым.

В главе 3 изучаются новые постановки задачи аппроксимации графа. В отличие от главы 1, где ограничения накладывались на количество компонент связности, в этой главе рассматриваются задачи аппроксимации графами с компонентами связности ограниченного размера.

Обозначим через MP{V) множество всех М-графов на V, в которых мощность каждой компоненты связности равна р, 2 ^ р ^ |У|. Будем говорить, что iW-граф принадлежит множеству M<P(V), если мощность каждой его компоненты не превышает целого числа р, 2 ^ р < |У|.

Как и ранее, расстояние между помечеными графами Gi = {V,E{) и G2 = (V,E2) определяется следующим образом: p(Gi,G2) = \ЕгАЕ2\.

Задача А<р. Дан n-вершинный граф G = (V, Е) и целое число р, 2 < р ^ п. Найти такой граф М* 6 Mip(V), что

p(G, М') = min p(G,M).

Задача Ар. Дан граф G — (V.E) такой, что \V\ = pq, где p,q — целые положительные числа. Найти такой граф М* е MP(V), что p(G, М") = min p(G,M).

В параграфе 3.1 рассмотрены случаи, когда оптимальные решения задач Aip и Ар можно найти за полиномиальное время.

Лемма 3.1. Для любого графа G — (V, Е) существует такое оптимальное решение М* ~ (V, Е*) задачи AiP при 2 < р < 3, что Е~ С Е.

Как следует из леммы 3.1, в задачах А<2 и А<3 всегда существует оптимальное решение, которое может быть получено из исходного графа G путем удаления ребер.

Теорема 3.1. Задача Ai2 полиномиально разрешима.

Следствие 3.1. Задача Ai3 на графах, не содержащих полных трех-вершинных подграфов, полиномиально разрешима.

Теорема 3.2. Задача А2 полиномиально разрешима.

В параграфе 3.2 доказано, что для любого фиксированного р ^ 3 задачи А<р и Ар являются iVP-трудными.

Теорема 3.3. Задача А<р NP-трудна для произвольного фиксированного р 3.

Следствие 3.2. Задача Ар NP-трудна при любом фиксированном р^ 3.

В параграфе 3.3 для задачи А«3 предложен полиномиальный приближенный алгоритм с гарантированной оценкой точности.

Обозначим через P(G) М-граф, построенный следующим образом: для графа G решаем задачу о наибольшем паросочетании, найденное паросочетание образует двухвершинные компоненты связности графа P(G), а вершины, не вошедшие в паросочетание, образуют тривиальные компоненты.

Если Т — подграф графа G, то через G-T будем обозначать подграф графа G, из которого удалены все вершины подграфа Т и инцидентные им ребра.

Алгоритм Т.

Дан граф G = (V,E) и семейство Т = {TUT2, ... ,7}} всех полных трех-вершинных подграфов графа G.

Шаг 0. Пусть G0 = G, М0 = P(G0). Если Т ф 0, то переходим на шаг 1, иначе на шаг 1 + 1.

Шаг i (1 < i < 1). Обозначим через Г» такой подграф из Т. что граф P{Gi-i - Т{) содержит наибольшее количество ребер среди всех графов вида P(Gi-1 - Т-) для 7) € Т.

Положим Gi = Gi-i - Ti и Mi = Тх U Т2 U ... U T4 U P{Gi). Удалим из T все подграфы, множество вершин которых имеет непустое пересечение с множеством вершин подграфа Т». Если Т ф 0, то переходим на шаг i + 1, иначе переходим на шаг I + 1.

Шаг 1+1. Среди всех построенных М-графов М0, Мь М2, ...,MS выберем такой М-граф Мт, что

p(G,MT)= min p(G, Mj).

Конец алгоритма.

Теорема 3.4 Пусть G = (V,E) - произвольный граф, п = \ V\ ^ 3. Через Мт обозначим приближенное решение задачи А<3, найденное алгоритмом Т, а через М* — оптимальное решение задачи А<3 на графе G. Тогда справедливо неравенство

Результаты параграфа 3.2 получены совместно с В.П. Ильевым, а результаты параграфа 3.3 — в соавторстве с В.П. Ильевым и С.Д. Ильевой.

Список литературы

[1] Агеев A.A., Ильев В.П., Кононов A.B., Талевнин A.C. Вычислительная сложность задачи аппроксимации графов // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13, N 1. С. 3-15.

[2] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб: Лань, 2010.

[3] Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука, 1975. Вып. 31. С. 35-42.

[4] Ильев В.П. Наследственные системы, матроиды и коматроиды. Задачи оптимизации и аппроксимации. Saarbrücken: LAP LAMBERT Academic Publishing. 2011.

[5] Ильев В.П., Навроцкая A.A., Талевнин A.C. Полиномиальная приближенная схема для задачи аппроксимации неплотных графов // Вестник Омского университета. 2007. Вып. 4. С. 24-27.

[6] Навроцкая A.A., Ильев В.П., Талевнин A.C. Асимптотически точный алгоритм для задачи аппроксимации неплотных графов //' Материалы III Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2006. С. 115.

[7] Талевнин А. С. О сложности задачи аппроксимации графов // Вестник Омского университета. 2004. N 4. С. 22-24.

[8] Фридман Г.Ш. Исследование одной задачи классификации на графах // В сб.: Методы моделирования и обработки информации. Новосибирск : Наука, 1976. С. 147-177.

[9] Bansal N.. Blum A., Chawla Sh. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113.

[10] Benzaken C., Hammer P.L. Boolean techniques for matroidal decomposition of independence systems and applications to graphs // Discrete Math. 1985. V. 56. P. 7-34.

[11] Berge С. Hypergraphes. Paris: Gauthier — Villars. 1987; English transi.: Berge С. Hypergraphs: Combinatorics of Finite Sets, Amsterdam: North-Holland, 1989.

[12] Coleman Т., Saunderson J., Wirth A. A local-search 2-approximation for 2-correlation-clustering // Algorithms - ESA 2008: Lecture Notes in Computer Science. 2008 V. 5193. P. 308-319.

[13] Edmonds J. Matroids and the greedy algorithm // Math. Programming. 1971. V. 1, N 2. P. 127-136.

[14] Giotis I., Guruswami V. Correlation clustering with a fixed number of clusters // Theory of Computing. 2006. V. 2, N 1. P. 249-266.

[15] Il'ev V. Hereditary systems and greedy-type algorithms // Discrete Appl. Math. 2003. V. 132. P. 137-148.

[16] Rado R. Note on independence functions // Proc. London Math. Soc. 1957. V. 7, N 3. P. 300-320.

[17] Shamir R-, Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144, N 1-2. P. 173-182.

Публикации автора по теме диссертации

1. Навроцкая А.А., Ильев В.П., Талевнин А.С. Асимптотически точный алгоритм для задачи аппроксимации неплотных графов / / Материалы III Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2006. С. 115.

2. Ильев В.П., Навроцкая А.А., Талевнин А.С. Полиномиальная приближенная схема для задачи аппроксимации неплотных графов // Вестник Омского университета. 2007. Вып. 4. С. 24-27.

3. Навроцкая А. А. Алгоритм с оценкой для задачи аппроксимации графов // Труды 39-й Всерос. молодежной конф. «Проблемы теоретической и прикладной математики». Екатеринбург, 2008. С. 313-317.

4. Ильев В.П., Ильева С.Д., Навроцкая А.А. Оценки погрешности алгоритмов приближенного решения задачи аппроксимации графа / / Труды VIII Междунар. конф. «Дискретные модели в теории управляющих систем». Москва, 2009. С. 120-127.

5. Навроцкая А.А. Полиномиальная приближенная схема для одного варианта задачи аппроксимации графа // Материалы IV Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2009. С. 153.

6. Навроцкая А.А. Алгоритм приближенного решения задачи аппроксимации графа // Материалы X Междунар. семинара «Дискретная математика и ее приложения». Москва, 2010. С. 316-319.

7. Навроцкая A.A., Ильев В.Г1. Оценка аппроксимационыой сложности линейных наследственных систем // Материалы Рос. конф. «Дискретная оптимизация и исследование операций». Новосибирск, 2010. С. 107.

8. Ильев В.П., Ильева С.Д., Навроцкая A.A. Приближенные алгоритмы для задач аппроксимации графов // Дискрет, анализ и исслед. операций. 2011. Т. 18, N 1. С. 41-60.

9. Навроцкая A.A. Задача аппроксимации графами с ограничениями на мощности компонент связности // Тезисы докладов XIV Всерос. конф. «Математическое программирование и приложения». Екатеринбург, 2011. С. 203.

10. Навроцкая A.A. Задача аппроксимации линейной наследственной системы // Вестник Омского университета. 2011. N 2. С. 34-38.

11. Ильев В.П., Навроцкая A.A. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикладная дискретная математика. 2011. N 3. С. 80-84.

12. Ильев В.П., Ильева С.Д., Навроцкая A.A. О задаче аппроксимации графами с компонентами связности ограниченного размера // Материалы Всерос. конф. «Статистика. Моделирование. Оптимизация». Челябинск, 2011. С. 150-154.

13. Ильев В.П., Навроцкая A.A. Задача аппроксимации наследственной системы // Материалы V Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2012. С. 129.

14. Навроцкая A.A. Три варианта задачи аппроксимации наследственных систем. Препринт. Омск: «Полиграфический центр КАН». 2012. 20 с.

Подписано в печать 11 января 2013. Формат 60x84 1/16.

_Печ. л. 1,0. Тираж 100 экз. Заказ № 05._

Издательство Омского государственного университета 644077, г. Омск, пр. Мира, 55а Отпечатано на полиграфической базе ОмГУ 644077, г. Омск, пр. Мира, 55а

Введение

1 Задачи аппроксимации графов

1.1 Постановки задач.

1.2 Алгоритм локального улучшения для задачи аппроксимации неплотных графов.

1.3 Алгоритм с константной оценкой точности для задачи аппроксимации двухкомпонентными графами.

2 Задачи аппроксимации наследственных систем

2.1 Наследственные системы, матроиды и коматроиды

2.2 Задача аппроксимации линейной наследственной системы

2.3 Задачи аппроксимации наследственных систем матроидами и коматроидами.

3 Задача аппроксимации графами с компонентами связности ограниченного размера

3.1 Полиномиально разрешимые случаи.

3.2 ІУР-трудньїе задачи.

3.3 Приближенный алгоритм для задачи аппроксимации графами с компонентами мощности, не превышающей трех

В диссертационной работе исследуются различные варианты задач аппроксимации графов и их обобщения — задачи аппроксимации наследственных систем.

Задачи аппроксимации графов наряду с задачами о мииимальных разрезах в графах являются наиболее адекватными математическими моделями задач кластеризации и классификации взаимосвязанных объектов. Однако, в отличие от задачи о минимальном разрезе в задаче аппроксимации графа минимизируется не только число «лишних» связей между классами, но и число «недостающих» связей внутри классов.

Актуальность темы диссертации обусловлена тем, что задачи на наследственных системах являются математическими моделями множества сложных в вычислительном плане практически важных задач. Одна из таких задач — задача аппроксимации наследственных систем матрои-дами, являющаяся обобщением задачи аппроксимации графа. Эта задача относится к классу А^Р-трудных, поэтому отыскание точного решения представляется весьма сложной проблемой. В то же время возрастает актуальность построения эффективных приближенных алгоритмов и получения гарантированых оценок точности таких алгоритмов.

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

Рассмотрены известные и новые варианты задачи аппроксимации графа и ее обобщения — задачи аппроксимации наследственных систем. Получены оценки аппроксимационной сложности наследственных систем, предложена новая постановка задачи аппроксимации графа и исследована ее вычислительная сложность. Предложены новые алгоритмы приближенного решения различных вариантов задачи аппроксимации графа, получены гарантированные оценки точности этих алгоритмов.

Приведем формулировки исследуемых задач и дадим краткий обзор известных результатов.

Задачи аппроксимации графов

Задачи аппроксимации графов возникают при анализе систем взаимосвязанных объектов, в частности, в задачах классификации. При этом минимизируется число связей между классами и число недостающих связей внутри классов. Постановки и различные интерпретации этих задач можно найти в работах [21, 23, 31, 34, 37, 59] и др.

Будем рассматривать только обыкновенные графы, т. е. графы без петель и кратных ребер [9]. Следуя Тышкевич [27], обыкновенный граф будем называть М-графом, если каждая его компонента связности является полным графом. Обозначим через А4(У) класс всех М-графов на множестве вершин У, — класс всех М-графов на множестве вершин V, имеющих ровно к непустых компонент связности, Л4^к{У) класс всех М-графов на множестве V, имеющих не более к компонент связности, 2 ^ к < \У\.

Если = (V, Е\) и (?2 = (V, Е2) — помеченные графы на одном и том же множестве вершин V, то расстояние /9(61, С72) между ними определяется как p(Gu G2) = \Е^Е2\ = \Е\ \ Е21 + \Е2\Е11 т. е. p(Gі, G2) — число несовпадающих ребер в графах G\ и G2.

Впервые задача аппроксимации графа была сформулирована в 1964 г. Заном [59].

Задача А. Дан граф G—{V,E). Найти такой граф М* eM(V), что p(G, М*) = min p(G, М) = t(G).

MeM(V)

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

Задача Ак- Дан граф G = (V, Е) и целое число /с, 2 ^ к ^ Найти такой граф М* єМк(У), что р(С,ЛГ) = min p(G,M) =f rk(G).

MeMk(V)

Задача A^k- Дан граф G = (V,E) и целое число fc, 2 ^ к ^ |V|. Найти такой граф М* что p(G, М*) = min p(G, М) тф{С). M€M^k{V)

Каждая из величин т(бг), 7*^(6?), Tk(G) называется аппроксимаци-онной сложностью графа G в соответствующей задаче аппроксимации графа. Очевидно, что для любого n-вершинного графа G и А: ^ 2 имеют место неравенства t{G) < r<k(G) < Tfe(G) ^ n(n~1).

Известны также взвешенные и ориентированные аналоги этих задач. В ориентированных задачах каждая бикомпонента аппроксимирующего орграфа является полным симметрическим орграфом и отсутствуют дуги, ведущие из одной бикомпоненты в другую. Во взвешенных вариантах задана весовая функция т : V х V —>■ N и Сгг) равно суммарному весу несовпадающих ребер в графах С\ и Сг

Первые теоретические результаты, относящиеся к задачам аппроксимации графов, были получены в 60-70-е гг. XX в. В 1964 г. Заном [59] была решена задача А для графов, представляющих иерархические структуры. В 1971 г. Фридман [28] показал, что задача А для любого графа без треугольников сводится к построению в нем наибольшего паросочетания. В том же году Вейнер [5] предложил алгоритм решения задачи аппроксимации графов, не содержащих четырехвершинных подграфов ровно с пятью ребрами, однако не доказал, что результатом работы алгоритма действительно является М-граф, оптимально аппроксимирующий данный граф. Обоснование алгоритма Вейнера было дано Фридманом [30]. Он же [29, 31] показал, что для любого тг-вершинного графа С имеет место достижимая оценка

Более сильный результат был установлен Томеску [55, 56]: для любого к ^ 2 и любого п-вершинного графа п - I)2 т<к(С) < 4

Позже Ильев и Фридман [20] доказали, что для любого к > 2и любого тгвершинного графа С при п ^ Ъ(к — 1) справедлива достижимая оценка

Во всех случаях авторами описаны классы критических графов, т. е. графов, для которых указанные неравенства выполняются как равенства.

В последние 12 лет задача А неоднократно переоткрывалась и независимо изучалась под разными названиями (Correlation Clustering [34], Cluster Editing [37, 54]). В этих и других работах изучались и варианты задачи, в которых число кластеров ограничено, а также рассматривались более общие постановки задач.

В 2004 г. Бансал, Блюм и Чаула [34] и независимо Шамир, Шаран и Цур [54] показали, что задача А является iVP-трудной, а Ильев и Та-левнин (см. [26]) установили, что взвешенная задача А^ iVP-трудна при любом фиксированном к ^ 2. В [54] доказано также, что задача Ak NP-трудна при любом фиксированном к ^ 2; в 2006 г. Гиотис и Гурусвами [46] опубликовали более простое доказательство этого результата. В том же году независимо Агеев, Ильев, Кононов и Талевнин [2] показали, что задачи А 2 и А^2 ^Р-трудны уже на кубических графах, откуда вывели, что все упомянутые варианты задачи аппроксимации графа, а также их взвешенные и ориентированные аналоги являются ./VP-трудными.

Так как было показано, что задачи аппроксимации графов NP-трудны, то дальнейшие исследования были сосредоточены на построении приближенных алгоритмов. Приведем необходимые понятия, характеризующие качество алгоритмов приближенного решения задач на минимум. Для задач максимизации подобные характеристики определяются аналогичным образом.

Полиномиальный алгоритм решения задачи минимизации называется а-приближенным, если он находит допустимое решение, для которого значение целевой функции не более чем в а раз хуже оптимального значения. Величина а называется гарантированной оценкой точности этого алгоритма. Говорят, что задача комбинаторной оптимизации принадлежит классу АРХ, если для нее существует а-приближенный алгоритм, где а — некоторая константа.

Семейство алгоритмов Ае приближенного решения задачи на минимум называют полиномиальной приближенной схемой, если для любого £ > 0 каждый алгоритм из А£ является (1 + ^-приближенным алгоритмом.

Для исследования качества приближенных алгоритмов часто используется следующая идея построения алгоритмов с оценками (г, 6), предложенная Гимади, Глебовым и Перепелицей [6].

Пусть /С — некоторый класс задач минимизации, V — семейство вероятностных мер, определенных на /С. Для К е К. обозначим ОРТ(К) — оптимальное значение целевой функции, а А {К) — значение, найденное алгоритмом А.

Говорят, что алгоритм А имеет оценки (г, 8) относительно V, если

Р{А{К) > (1 + £)ОРТ(К)} ^ 6 для всех К € К. и Р Е V. Параметры ей 5 могут трактоваться как оценки относительной погрешности и вероятности несрабатывания алгоритма А, соответственно. Для подкласса Кп С /С задач размерности п говорят о семействах и оценках (еп, 5п).

Примером алгоритма с оценками (£п,5п) является алгоритм Боров-кова [4] для класса К,п задач коммивояжера, в которых распределения из Тп получаются в результате случайного выбора п точек в ограниченной, односвязной области г-мерного евклидова пространства с достаточно гладкой границей.

Алгоритм А называется асимптотически точным на классе задач /С, если существуют такие последовательности (£п,6п), что для любого п алгоритм А имеет оценки (£п,8п) на подмножестве Кп С /С, причем £п -*" 0, 6п —> 0 при п —> оо.

Если при этом все 5п = 0, то такой алгоритм называется гарантированно асимптотически точным. Другими словами, алгоритм А гарантированно асимптотически точен на классе задач /С, если существует такая последовательность єп, что для любого п

А{К) < (1 + єп)ОРТ(І<) на подмножестве Кп С /С задач размерности п, причем еп —> 0 при п —>• оо.

Пусть @п — такое семейство п-вершинных графов, что для любого графа Є = (У,Е) Є 9п выполнено ^ ст^, где а > О, 0 < /? < 2 — некоторые константы. Графы семейства Оп назовем неплотными.

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

В 2004 г. Бансал, Блюм и Чаула [34] предложили простой З-приближен-ный алгоритм для задачи А<^ и полиномиальный приближенный алгоритм с константной оценкой точности для задачи А, а также доказали, что взвешенная задача А АРХ-трудна. В 2005 г. Чарикар, Гурусвами и Вирт [40] показали, что невзвешенная задача А является ЛРХ-трудной и предложили для нее 4-приближенный алгоритм. В 2008 г. Айлон, Чарикар и Ньюман [33] предложили 3-приближенный алгоритм для невзве-шенной задачи А и 2.5-приближенный алгоритм для ее взвешенной версии.

В 2006 г. Агеев, Ильев, Кононов и Талевнин [2] доказали существование рандомизированной полиномиальной приближенной схемы для задачи а Гиотис и Гурусвами [46] предложили рандомизированную полиномиальную приближенную схему для задачи А^к (для любого фиксированного к ^ 2). В том же году Навроцкая, Ильев и Талевнин [19, 24] показали, что алгоритм локального поиска является гарантированно асимптотически точным для задачи на неплотных графах. Указав, что сложность полиномиальной приближенной схемы из [46] лишает ее перспективы практического использования, Колман, Саундерсон и Вирт [42] в 2008 г. предложили 2-приближенный алгоритм для задачи применив процедуру локального поиска к допустимому решению, полученному с помощью 3-приближенного алгоритма из статьи [34]. Для задачи А2 в работе [17] Ильевым, Ильевой и Навроцкой предложен простой (3 — 6/п)-приближенный алгоритм.

В диссертации исследуется также новый вариант задачи аппроксимации графа. Отличие новой постановки в том, что ограничения накладываются не на количество компонент связности, а на их мощность. Обозначим через A4P(V) множество всех М-графов на множестве V, в которых мощность каждой компоненты связности равна целому числу р, 2 ^ р ^ |V|, при этом |V| кратно р. Будем говорить, что М-граф принадлежит классу A4<P(V), если мощность каждой его компоненты не превышает целого числа р, 2 ^ р ^ |V|.

Задача Ар. Дан граф G = {V,E) такой, что |V| = pq, где p,q — целые положительные числа. Найти такой граф М* £ A4P(V), что p(G,M*)= min p(G,M).

MeMP(V)

Задача А<р. Дан n-вершинный граф G = (V, Е) и целое число р, 2 ^ р ^ п. Найти такой граф М* £ M<P(V), что p(G,M*)= min P(G,M).

MeM<P{V)

Данные постановки рассматриваются впервые.

Задачи аппроксимации наследственных систем

Задача аппроксимации графа является частным случаем задачи аппроксимации наследственной системы. Пусть V — непустое конечное множество, А С 2У — непустое семейство его подмножеств, удовлетворяющее следующей аксиоме наследственности:

Ах еЛ, А2 С А\ Л2 в А.

Множества семейства А называются независимыми, все остальные подмножества V — зависимыми. Семейство А обычно называют системой независимости или наследственным семейством на V [48].

Семейство всех зависимых множеств обозначим V. Очевидно, что семейство V обладает свойством наследственности «вверх»:

1 е £>, А С Д> £>2 е V.

Каждое из семейств А,Т> однозначно определяет другое, поэтому естественно рассматривать их как различные стороны одного и того же объекта — наследственной системы [13, 50].

Наследственной системой 5 на множестве V называется разбиение семейства 2У всех подмножеств V на два непересекающихся семейства А и V, где А — система независимости, а Т> = 2У \ А. Базами наследственной системы 5 называются максимальные по включению независимые, а циклами — минимальные ио включению зависимые множества. Семейства всех баз и всех циклов системы 5 будем обозначать через В и С, соответственно. Очевидно, что каждое из семейств А, В, С и Т> однозначно определяет наследственную систему поэтому будем записывать £ = (V, А), 5 = (V, В), £ = (V, С) или £ = (V, V) в зависимости от того, какая сторона наследственной системы будет нас интересовать.

В качестве примеров можно привести наследственные системы, в которых независимыми множествами являются линейно независимые семейства вектор-столбцов матрицы, паросочетания в графе, а также системы, зависимыми множествами которых являются /¿-связные остов-ные подграфы или вершинные покрытия графа. Еще одним примером наследственной системы является наследственная система графа. Рассмотрим произвольный связный граф = (V, Е) и наследственную систему Бс = (V, где Ас — семейство всех независимых множеств вершин графа С. Легко видеть, что любой цикл системы во имеет мощность 2 и соответствует ребру графа С.

Гиперграфом называется пара Н = (У,Е), где V — непустое конечное множество, а Е — семейство подмножеств V. Элементы множества V называются вершинами, а элементы семейства Е — ребрами гиперграфа Н. Произвольной наследственной системе в = (V, V) поставим в соответствие гиперграф = (У,Е), ребра которого взаимно однозначно соответствуют циклам этой системы. Наоборот, любой гиперграф Н порождает наследственную систему = циклами которой являются минимальные по включению ребра гиперграфа Н. Поэтому наследственную систему можно отождествлять с гиперграфом, никакое ребро которого не содержит другое ребро в качестве подмножества. Гиперграф Н = (У,Е) называется линейным [39], если любые два ребра гиперграфа Н пересекаются не более чем по одной вершине.

Пусть 5 = (V, С) — наследственная система, С — семейство ее циклов. Наследственная система называется линейной, если любые два ее цикла имеют не более одного общего элемента [47]. Очевидно, частным случаем линейной наследственной системы является наследственная система графа.

Важным частным случаем понятия наследственной системы является понятие матроида, введенное Уитни [58].

Матроид на множестве У может быть определен как наследственная система М = (У, А), в которой все базы любого множества И7 6 У имеют одинаковую мощность (базой множества IV называется любое его максимальное по включению независимое подмножество). Рангом матроида называется мощность любой базы множества У.

Наследственная система графа 6? = (У, Е) является матроидом тогда и только тогда, когда (7 — М-граф [38]. Такой матроид называется матроидом разбиения. Имеется в виду разбиение множества V вершин М-графа С на подмножества У\,., 14 , гДе У% ~~ множество попарно смежных вершин г-й компоненты связности, г — 1,. ,к. Таким образом, наследственная система М-графа может служить примером матроида.

С каждой наследственной системой 5 = (У, А) тесно связана дополнительная система или косистема & = (У,Т>'), семейство зависимых множеств которой определяется какТ>' = : А 6 А}. Наследственная система, дополнительная к матроиду, называется коматроидом.

Примером коматроида является коматроид разбиения — наследственная система, дополнительная к матроиду разбиения. Циклами этого коматроида являются вершинные покрытия М-графа С.

Наследственные системы и их частные случаи — матроиды и коматро-иды — естественным образом возникают в различных областях математики, таких как линейная алгебра, теория графов, теория трансверсалей (см. [3, 8, 57]) и других разделах комбинаторного анализа, а также в комбинаторной оптимизации [11, 12, 13, 15, 18, 27, 44, 45, 50, 51, 52, 53].

Рассмотрим одну из центральных оптимизационных задач на наследственных системах — задачу о максимальном независимом множестве наследственной системы. Пусть V — конечное множество, / : V —> П+ — весовая функция, Л — семейство независимых множеств наследственной системы = (V, А). Требуется найти шах{/(Х) : X € Л}, (1) где /(.X) = £/(*). х€Х

Многие известные оптимизационные задачи являются частными случаями задачи (1). Некоторые из них полиномиально разрешимы (задача об остовном дереве максимального веса [51, 52], задача о максимальном паросочетании [43]). Однако, большая часть этих задач относится к классу А^Р-трудных (задача о рюкзаке, о максимальном независимом множестве вершин и о максимальной клике в графе, задача о 3-сочетании и другие).

Очень часто для приближенного решения N Р-труддых задач, сводящихся к схеме (1), применяется жадный алгоритм [36, 44, 45, 49].

Как следует из теоремы Радо-Эдмондса [45, 53], задача (1) разрешима жадным алгоритмом, если наследственная система 5 является матрои-дом. В связи с этим представляет интерес следующий вопрос: как сильно данная наследственная система отличается от матроида? Этот вопрос приводит нас к задаче аппроксимации наследственных систем, самая общая постановка которой такова.

Пусть АЛ(у) — некоторый класс матроидов на множестве V. Для заданной наследственной системы 5 = (V, Л) найти матроид М из класса Л4(У), который в каком-то смысле является самым близким к системе 5.

Мера близости т(5) наследственной системы £ и матроидов класса Л4(У) (аппроксимационная сложность системы 5) может определяться по-разному в различных задачах.

Одна из постановок задачи матроидной аппроксимации, впервые сформулированная Р.И. Тышкевич, получается, если Sq = {V, Ag) — наследственная система графа G = (V, Е), АА(у) — класс всех матроидов разбиений на множестве V, a t(Sg) равно минимуму (по всем Me Л4(У)) мощности симметрической разности семейств циклов системы Sc и мат-роида М. Такая задача матроидной аппроксимации эквивалентна задаче аппроксимации графа. Непосредственным обобщением этой задачи является задача аппроксимации линейной наследственной системы, если S = (V, А) — линейная наследственная система, A4(V) — класс всех линейных наследственных систем, являющихся матроидами на V, a r(S) равно минимуму (по всем М € A4(V)) мощности симметрической разности семейств циклов системы S и матроида М.

В связи с задачей о максимальном независимом множестве (1) представляет интерес следующая постановка задачи аппроксимации наследственной системы.

Пусть ЛЛ(у) — класс всех матроидов разбиений с носителем V, величина t(S) определяется следующим образом: t(S) = min \f (OptS) - f(OptM)I,

MeM(V) где OptS — оптимальное решение задачи (1) на системе S = (V,A), а OptM ~ оптимальное решение аналогичной задачи на матроиде М с той же самой целевой функцией.

Получаем следующую задачу матроидной аппроксимации.

Для заданной наследственной системы S = (V,A) найти такой матроид разбиения М* € A4(V), что f(OptS) — f(OptM*)\ = t(S).

Если определить аппроксимациониую сложность наследственной системы 5 как г!*- тах /(°РШ) то оценка величины т(5) может рассматриваться как гарантированная оценка точности жадного алгоритма приближенного решения задачи (1).

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

Пусть У — конечное множество, / : У —» — весовая функция, V — семейство зависимых множеств наследственной системы Б = (V, Т>). Необходимо найти тт{/(1) :XeV}, (2) где = х€Х

Многие задачи комбинаторной оптимизации, такие как задача о минимальном остовном А>связном подграфе [22, 25, 41], о минимальном вершинном покрытии [35], о покрытии множества [1] и другие, сводятся к задаче о минимальном зависимом множестве.

В работе [50] доказана теорема, являющаяся аналогом теоремы Радо-Эдмондса, из которой следует, что задача (2) разрешима «обратным» жадным алгоритмом, если наследственная система 5 является коматро-идом. Тогда возникает следующий вопрос: как сильно данная наследственная система отличается от коматроида? Так мы приходим к задаче аппроксимации наследственных систем коматроидамц самая общая постановка которой такова.

Пусть /С(У) — некоторый класс коматроидов на мноснсествеУ. Для заданной наследственной системы 5 = (V, Т>) найти коматроид К из класса К(У), который в каком-то смысле является самым близким к системе 5.

Мера близости т (Б) наследственной системы 5 и коматроидов класса /С(У) (аппроксимационная сложность системы 5) может определяться по-разному в различных задачах.

Пусть 1С(у) — класс всех коматроидов разбиений с носителем V. В связи с задачей (2) величина т(5) может быть введена следующим образом: т{8) = тіп^\fiOptS) - !{ОріК)І, где ОуЬБ — оптимальное решение задачи (2) на системе 5 = (V, Р), а ОрЬК — оптимальное решение аналогичной задачи на коматроиде К с той же самой целевой функцией.

Рассмотрим следующую задачу аппроксимации наследственных систем коматроидами.

Для заданной наследственной системы Б = (V, Т>) найти такой ко-матроид разбиения К* Є /С(У), что fiOptS) — /(ОрШ*)\ = т(£). Можно также рассмотреть другое определение величины т(5):

• КОрж) и задачу аппроксимации наследственных систем коматроидами с новой величиной т(5).

Мера близости наследственных систем в этих задачах понимается как близость оптимальных значений целевых функций оптимизационных задач на наследственных системах. При этом оценки аппроксимационной сложности наследственных систем характеризуют качество приближенных алгоритмов решения соответствующих оптимизационных задач на этих наследственных системах.

Структура диссертации

Диссертационная работа состоит из введения, трех глав, заключения и списка литературы.

Основные результаты диссертационной работы:

1. Для задачи аппроксимации графами, имеющими не более к компонент связности, предложен алгоритм локального улучшения. Для любого фиксированного к ^ 2 доказано, что алгоритм локального улучшения гарантированно асимптотически точен в классе неплотных графов. На основе этого алгоритма построена полиномиальная приближенная схема решения задачи на неплотных графах. Для задачи аппроксимации графами, имеющими ровно 2 компоненты связности, предложен приближенный алгоритм с достижимой гарантированной оценкой точности.

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

3. Рассмотрена новая постановка задачи аппроксимации графами с компонентами связности ограниченного размера. Выделены полиномиально разрешимые случаи. Доказано, что задача аппроксимации графами, мощность компонент связности которых не превосходит р, ./УР-трудна для любого фиксированного р ^ 3. Для случая р = 3 предложен алгоритм приближенного решения задачи и получена его гарантированная оценка точности.

Заключение

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

1. Агеев A.A. Алгоритмы с улучшенными оценками точности для задачи о покрытии множествами //Дискрет, анализ и исслед. онер. Сер. 2. 2004. Т. 11, N 1. С. 3-10.

2. Агеев A.A., Ильев В.П., Кононов A.B., Талевнин A.C. Вычислительная сложность задачи аппроксимации графов // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13, N 1. С. 3-15.

3. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб: Лань. 2010.4J Боровков A.A. К вероятностной постановке двух экономических задач // Докл. АН СССР. 1962. Т. 1, N 5. С. 983-986.

4. Вейнер Г.А. Об аппроксимации симметричного рефлексивного бинарного отношения отношением эквивалентности // Труды Таллинского политех, института. Сер. А. 1971. N 313. С. 45-49.

5. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука, 1975. Вып. 31. С. 35-42.

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука. 1990.

8. Зыков A.A. Основы теории графов. М.: Наука. 1987.

9. Ильев В.П. Одна задача матроидной аппроксимации // Методы решения и анализа задач дискретной оптимизации. Омск. 1992. С. 42-51.

10. Ильев В.П. Оценка погрешности градиентного алгоритма для систем независимости // Дискрет, анализ и исслед. операций. 1996. Т. 3, N 1. С. 9-22.

11. Ильев В.П. Задачи на системах независимости, разрешимые жадным алгоритмом // Дискретная математика. 2009. Т. 21, вып. 4. С. 85-94.

12. Ильев В.П. Наследственные системы, матроиды и коматроиды. Задачи оптимизации и аппроксимации. Saarbrücken: LAP LAMBERT Academic Publishing. 2011.

13. Ильев В.П., Линкер Н.В. К задаче минимизации супермодуляриой функции на коматроиде // Вестник Омского университета. 2002. N 1. С. 16-18.

14. Ильев В.П., Навроцкая A.A., Талевнин A.C. Полиномиальная приближенная схема для задачи аппроксимации неплотных графов// Вестник Омского университета. 2007. Вып. 4. С. 24-27.

15. Ильев В.П., Фридман Г.Ш. К задаче аппроксимации графами с фиксированным числом компонент // Доклады АН СССР. 1982. Т. 264, N 3. С. 533-538.

16. Ляпунов A.A. О строении и эволюции управляющих систем в связи с теорией классификации // Проблемы кибернетики. М.: Наука, 1973. Вып. 27. С. 7-18.

17. Мадер В. Минимальные n-связные графы с максимальным числом ребер. В сб.: Теория графов. Покрытия, укладки, турниры. М.: Мир, 1974.

18. Миркин Б.Г. Задачи аппроксимации в пространстве отношений и анализ нечисловых данных // Автоматика и телемеханика. 1974. N 9. С. 53-61.

19. Навроцкая A.A., Ильев В.П., Талевнин A.C. Асимптотически точный алгоритм для задачи аппроксимации неплотных графов // Материалы III Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2006. С. 115.

20. Попков В.К. Математические модели живучести сетей связи. Новосибирск: ВЦ СО АН СССР, 1990.

21. Талевнин А.С. О сложности задачи аппроксимации графов// Вестник Омского университета. 2004. N 4. С. 22-24.

22. Тышкевич Р.И. Матроидные разложения графа // Дискретная математика. 1989. Т. 1, вып. 3. С. 129-139.

23. Фридман Г.Ш. Одна задача аппроксимации графов // Управляемые системы. Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1971. Вып. 8. С. 73 75.

24. Фридман Г.Ш. Об одном неравенстве в задаче аппроксимации графов // Кибернетика. 1974. N 3. С.151.

25. Фридман Г.Ш. О некоторых результатах в задаче аппроксимации графов // Проблемы анализа дискретной информации. Новосибирск: ИЭиООП СО АН СССР. 1975. С. 125-152.

26. Фридман Г.Ш. Исследование одной задачи классификации на графах //В сб.: Методы моделирования и обработки информации. Новосибирск : Наука, 1976. С. 147-177.

27. Фридман Г. Ш. Полиномиальная полнота некоторых модификаций задачи аппроксимации графов // Тез. докл. IV Всесоюз. конф. по проблемам теоретической кибернетики. Новосибирск. 1977. С. 150.

28. Ailon N., Charikar М., Newman A. Aggregating inconsistent information: Ranking and clustering //J. ACM. 2008. V. 55, N 5. P. 1-27.

29. Bansal N., Blum A., Chawla Sh. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113.

30. Bar-Yehuda R., Even S. A linear time approximation algorithm for the weighted vertex cover problem // J. of Algorithms. 1981. V. 2. P. 198203.

31. Bednorz W., ed. Advances in greedy algorithms. Wienna: I-Tech Education and Publishing KG. 2008.

32. Ben-Dor A., Shamir R., Yakhirni. Clustering gene expression patterns //J. Comput. Biol. 1999. V. 6, N 3-4. P. 281-297.

33. Benzaken C., Hammer P.L. Boolean techniques for matroidal decomposition of independence systems and applications to graphs // Discrete Math. 1985. V. 56. P. 7-34.

34. Berge C. Hypergraphs. Paris: Gauthier — Villars. 1987; English transl.: Berge C. Hypergraphs: Combinatorics of Finite Sets, Amsterdam: North Holland, 1989.

35. Charikar M., Guruswami V., Wirth A. Clustering with qualitative information //J. Comput. Syst. Sci. 2005. V. 71, N 3. P. 360-383.

36. Cheriyan J., Thurimella R. Approximating minimumu-size k-connected spanning subgraphs via matching // Electronic Colloquium on Computational Complexity (ECCC). 1998. Report N 25. P. 1-36.

37. Coleman T., Saunderson J., Wirth A. A local-search 2-approximation for 2-correlation-clustering // Algorithms ESA 2008: Lecture Notes in Computer Science. 2008 V. 5193, P. 308-319.

38. Edmonds J. Paths, trees, and flowers // Canadian J. of Mathematics. 1965. V. 17, N 3. P. 449-467.

39. Edmonds J. Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and their Applications. Proc. Calgary Int. Conf. June 1969. Guy R.K., Hanani H., Sauer N., Schonheim J., eds. New York: Gordon and Breach. 1970. P. 69-82.

40. Edmonds J. Matroids and the greedy algorithm // Math. Programming. 1971. V. 1, N 2. P. 127-136.

41. Giotis I., Guruswami V. Correlation clustering with a fixed number of clusters // Theory of Computing. 2006. V. 2, N 1. P. 249-266.

42. Grama Y., Hammer P.L. Methods and Models of Operations Research. 1989. V. 33, N 3. P. 149-165.

43. Grotschel M., Lovasz L. Combinatorial optimization. In: Handbook of Combinatorics. Graham R.O., Grotschel M., Lovasz L., eds. Amsterdam: Elsevier Science B.V. 1995. V. 2. P. 1341-1598.

44. Halldorsson M. M., Radhakrishnan J. Greed is good: approximating independent sets in sparse and bounded-degree graphs // Algorithmica. 1997. V. 18, N 1. P. 145-163.

45. Il'ev V. Hereditary systems and greedy-type algorithms // Discrete Appl. Math. 2003. V. 132. P. 137-148.

46. Kruskal J.B. On the shortest spanning substree of a graph and the traveling salesman problem // Proc. AMS. 1956. V. 7, N 1. P. 48-50.

47. Prim R.C. Shortest connection networks and some generalizations // Bell System Technical Journal. 1957. N 36. P. 1389-1401.

48. Rado R. Note on independence functions // Proc. London Math. Soc. 1957. V. 7, N 3. P. 300-320.54j Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144, N 1-2. P. 173-182.

49. Tomescu I. Note sur une caractérisation des graphes done le degreé de deséquilibre est maximal // Mathématiques et sciences humaines. 1973. V. 11, N 42. P. 37-40.

50. Tomescu I. La reduction minimale d'un graphe à une reunion de cliques // Discrete Math. 1974. V. 10, N 1-2. P. 173-179.

51. Welsh D. J. A. Matroid theory. London: Academic Press. 1976.

52. Whitney H. On the abstract properties of linear dependence // Amer. J. Math. 1935. V. 57. P. 509-533.

53. Zahn C. Approximating symmetric relations by equivalence relations // J. of SIAM. 1964. V. 12, N 4. P. 840-847.

54. Публикации автора по теме диссертации

55. Навроцкая A.A., Ильев В.П., Талевнин A.C. Асимптотически точный алгоритм для задачи аппроксимации неплотных графов // Материалы III Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2006. С. 115.

56. Ильев В.П., Навроцкая A.A., Талевнин A.C. Полиномиальная приближенная схема для задачи аппроксимации неплотных графов // Вестник Омского университета. 2007. Вып. 4. С. 24-27.

57. Навроцкая A.A. Алгоритм с оценкой для задачи аппроксимации графов // Труды 39-й Всерос. молодежной конф. «Проблемы теоретической и прикладной математики». Екатеринбург, 2008. С. 313-317.

58. Ильев В.П., Ильева С.Д., Навроцкая A.A. Оценки погрешности алгоритмов приближенного решения задачи аппроксимации графа // Труды VIII Междунар. конф. «Дискретные модели в теории управляющих систем». Москва, 2009. С. 120-127.

59. Навроцкая A.A. Полиномиальная приближенная схема для одного варианта задачи аппроксимации графа // Материалы IV Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2009. С. 153.

60. Навроцкая A.A. Алгоритм приближенного решения задачи аппроксимации графа // Материалы X Междунар. семинара «Дискретная математика и ее приложения». Москва, 2010. С. 316-319.

61. Навроцкая A.A., Ильев В.П. Оценка аппроксимационной сложности линейных наследственных систем // Материалы Рос. конф. «Дискретная оптимизация и исследование операций». Новосибирск, 2010. С. 107.

62. Ильев В.П., Ильева С.Д., Навроцкая A.A. Приближенные алгоритмы для задач аппроксимации графов // Дискрет, анализ и исслед. операций. 2011. Т. 18, N 1. С. 41-60.

63. Навроцкая A.A. Задача аппроксимации графами с ограничениями на мощности компонент связности // Тезисы докладов XIV Всерос. конф. «Математическое программирование и приложения». Екатеринбург, 2011. С. 203.

64. Навроцкая A.A. Задача аппроксимации линейной наследственной системы // Вестник Омского университета. 2011. N 2. С. 34-38.

65. Ильев В.П., Навроцкая A.A. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикладная дискретная математика. 2011. N 3. С. 80-84.

66. Ильев В.П., Ильева С.Д., Навроцкая A.A. О задаче аппроксимации графами с компонентами связности ограниченного размера // Материалы Всерос. конф. «Статистика. Моделирование. Оптимизация». Челябинск, 2011. С. 150-154.

67. Ильев В.П., Навроцкая A.A. Задача аппроксимации наследственной системы // Материалы V Всерос. конф. «Проблемы оптимизации иэкономические приложения». Омск, 2012. С. 129.

68. Навроцкая A.A. Три варианта задачи аппроксимации наследственных систем. Препринт. Омск: «Полиграфический центр КАН». 2012. 20 с.