автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Сложность аппроксимации оптимизационных задач на наследственных системах

На правах рукописи ТАЛЕВНИН Антон Степанович

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

05.13.01 - системный анализ, управление и обработка информации (в научных исследованиях)

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

Омск - 2006

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

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

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

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

профессор Гимади Эдуард Хайрутдинович,

Защита состоится « 29 » июня 2006 г. в 16 часов на заседании диссертационного совета ДМ 212.179.03 при ГОУ ВПО «Омский государственный университет им. Ф.М. Достоевского» по адресу: 644077, г. Омск, ул. Нефтезаводская, 11.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского.

Автореферат разослан «Ж» мая 2006 г.

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

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

Ведущая организация: Уральский государственный университет

им. А.М. Горького.

к.ф.-м.н.

Семенов А.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

Основные результаты диссертации, выносимые на защиту, получены автором лично.

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

Апробация работы. Основные результаты диссертации докладывались на Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2002), 12-ой Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2003), Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2003), ХШ-ой Байкальской международной школе-

семинаре «Методы оптимизации и их приложения» (Иркутск, 2005), а также на научных семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН.

Публикации. По теме диссертации автором опубликовано 9 научных работ, список которых приведен в конце автореферата.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Пусть V - конечное множество. Системой независимости на V называется пара (V, Д), где А С 2У - непустое семейство подмножеств V, обладающее свойством: если А 6 Л и А' С А, то А! € А. Множества семейства А называются независимыми, а все подмножества из 2У \ А -зависимыми.

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

Очевидно, что как семейство В, так и семейство С однозначно определяют наследственную систему «5, поэтому будем записывать Я = (V, В) или 5 = (У, С) в зависимости от того, какая информация о наследственной системе нас интересует в данный момент.

Рассматриваются две задачи комбинаторной оптимизации.

Задача 1 (о наибольшем независимом множестве). Дана наследственная система S = (V, С). Найти такое X* Е Л, что

\Х*\ = max{|X| : X & Л} = тах{|Х| : X € В].

Задача 2 (о наименьшем зависимом множестве). Дана наследственная система S = (V, В). Найти такое X* £ Т>, что

\Х*\ = min{|X| : X € Т>} — mm{|X| : X £ С}.

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

В разделе 1.2 задача 1 рассматривается как задача поиска наибольшего независимого множества вершин гиперграфа.

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

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

Тогда, полагая S = Sh в задаче 1, полу чаем задачу о наибольшем независимом множестве вершин гиперграфа Н.

Будем говорить, что е £ Е является к-ребром гиперграфа Н, если |е| — к, и обозначим через Et¡ множество всех его Л-ребер. Для каждой вершины v £ V множество инцидентных ей ребер обозначим через E(v), т.е. E(v) = {е 6 Е | v £ е}. Введем понятия степени и к-степени вершины v £ V, соответственно, как d(v) = |.Е(и)| и dk(v) ~ |.£(t>) Для каждой вершины v £ V через N(v) = {и £ V \ uv £ Е2} обозначим множество вершин, смежных с V. Среднюю степень d(H) вершин в гиперграфе Н определим как £ d(v)/|V|.

veV

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

Процедура Э(Я)

1. Любые два ребра ei,e2, такие, что |ei П ег) > 2, заменяются одним 2-ребром, соединяющим произвольную пару вершин из eifl^.

2. Любое ребро е, такое, что |е| > 3, заменяется 2-ребром, соединяющим произвольную пару вершин из е.

3. Если существуют ребра е\ — {v, г>2}, е2 — {и, 173,114} (т.е. ехПег = {f}), то они заменяются на 2-ребра е\ = {г;,?^} и е'2 = {^з»^}.

Жадный алгоритм Gr(i/) S (Я);

So 0;

Пока Я ^ 0 выполнять Шаг 1. Выбрать вершину v, такую, что d2{v) + d{v) = mm (d2(u) +

Шаг 2. SG SGU {v};" Шаг 3. e e \ {v} для всех e € ¿'(w) Л Шаг 4. Я ч- Я \ ({«} U JV(w)); конец цикла; конец алгоритма.

На шаге 4 алгоритма Gr из гиперграфа Я удаляется вершина г; вместе со всеми смежными ей вершинами, а также все ребра, инцидентные этим вершинам.

Теорема 1.1. Пусть So - оптимальное решение задачи 1 и So -решение, полученное алгоритмом Gr. Тогда

|50| < So], (1)

где d, = d(H) средняя степень вершин в гиперграфе Н.

Оценка (1) является обобщением известной оценки погрешности жадного алгоритма для задачи о наибольшем независимом множестве в графе1.

1HaIld6rsson М. М., Radhakrishnan J. Greed is good: approximating independent sets in sparse and bounded-degree graphs // Algorithmic*. 1997. V. 18, N 1. P. 145-163.

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

С каждой наследственной системой S = (V, В) тесно связана дополнительном система S', семейство циклов которой определяется как С = {V \ В | В е В}.

Если положить S = S'H, где <S# = (V,Ch) - наследственная система некоторого гиперграфа Н — (У, Е), циклы которой соответствуют минимальным но включению ребрам гиперграфа Н, a S'jj - дополнительная система, то задача 2 становится задачей о наименьшем вершинном покрытии ребер гиперграфа Н.

Это дает возможность применить для решения задачи 2 па наследственной системе 5 — S'n известный алгоритм Хватала2.

Из эквивалентности задачи 2 и задачи о покрытии множества следует гарантированная оценка погрешности алгоритма Хватала для задачи 2, которая остается справедливой и для взвешенной задачи 2.

Теорема 1.2. Пусть So - оптимальное решение задачи 2, Sc ~ решение, полученное алгоритмом Хватала. Тогда

где Д - максимальная степень вершин гиперграфа Н.

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

aChvata) V. A greedy heuristic for the set-covering problem // Math. Oper. Res. 1979. V. 4, N 3. P. 233-235.

В разделе 2.1 приводятся основные определения и постановки задач аппроксимации графа. Обыкновенный граф называется М-графом, ссли каждая его компонента связности есть полный граф. Обозначим через M(V) класс всех М - графов на множестве вершин V, Мк{У) ~ класс всех А/-графов на множестве вершин V, имеющих ровно к непустых компонент связности, ßA\{V) - класс всех М-графов на множестве V, имеющих не более к компонент связности, 2 < к < |V|.

Если Gi и G2 - графы на одном и том же множестве вершин V, то расстояние между ними определяется как

d(G1,G2) = |Е(Сг) \ E(G2)| + \E{G2) \ £(C?i)|,

то есть d(Gi,G2) равно числу несовпадающих ребер в графах G\ и G2.

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

Задача А. Для обыкновенного графа G — (У, Е) найти такой граф М* е М (F), что d(G, М*) = min d(G, М).

Задача Ak. Дан граф G=(V, Е) и целое число к, 2 < к < ¡Vj. Найти такой граф М* 6 Mk(V), что d(G, М*) = min d(G, М).

Задача h\ формулируется аналогично.

Несмотря на то, что задача аппроксимации графа исследуется уже более 30 лет, ее вычислительная сложность долгое время оставалась неизвестной. Лишь недавно A.B. Кононовым было доказано, что задача А2 NP-трудна уже на кубических графах3.

В разделе 2.2 доказан следующий результат.

Теорема 2.2. Задача Ау является NP-трудпой для любого фиксированного значения к > 2.

Следствие. Задача А£ NP-трудна для любого фиксированного значения к >2.

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

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

4 Arora S., Karger D., and Karpinski М. Polynomial time approximation schemes for dense instances of TVP-hard problems // Proc. 27th Ann. ACM Symp. on Theory of Comp. 1995. P. 284-293.

Теорема 2.3. Для задачи существует полиномиальная аппрок-симациоиная схема.

Раздел 2.3 посвящен исследованию приближенных алгоритмов решения задачи А\. Рассмотрим следующую эквивалентную постановку задачи А^-

Для данного графа G={V,E) найти разбиение (Vi, V2) множества V, на котором достигает минимума функция

f{Vi,V2) = \{uveE:u&VuveV2}\ т

В этой постановке допускается, что одно из множеств VI, V2 может быть пустым.

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

Пусть К некоторый класс задач минимизации. Для задачи / б /С обозначим через /0(7) и /а(1) оптимальное решение и решение, найденное алгоритмом А, соответственно. Алгоритм А имеет оценки относительной погрешности еп и вероятности несрабатывания 5п, если для каждого тг

Рг Ш(/) < (1 + е„)/0(/)} > 1 - 6п

на множестве fCn С 1С задач размерности п. Алгоритм с оценками (еп, 5п) называется асимптотически точным, если еп —> 0 и <5П —> 0 при п —У оо5.

Рассмотрим класс fCn редких графов G — (V, Е), имеющих не более сп ребер, где п — |V[, а с > 0 некоторая константа. Поскольку для кубических графов \Е\ = Зп/2, то из результатов предыдущего параграфа следует, что и для редких графов задача А\ остается NP-трудной.

Для задачи AJ существуют простые полиномиальные алгоритмы, которые находят решение {V\, V2), удовлетворяющее неравенству:

(з)

и имеют оценки (е„, 0), где е„ —> 0 при п —> оо.

Теорема 2.4. Пусть некоторый алгоритм для задачи А\ строит решение (Vi, V2), удовлетворяющее (3). Тогда он является асимптотически точным на классе редких графов.

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

Предложены алгоритмы Gr и Т приближенного решения задачи которые гарантированно находят решения, удовлетворяющие (3). Следовательно, по теореме 2.4 оба алгоритма являются асимптотически точными на редких графах.

В разделе 2.3.2 для задачи Aj разработан вероятностный приближенный алгоритм А(5,с) с константной оценкой точности (здесь <5 и с -параметры алгоритма, 5 S (0,1), а с > 0). Идея этого алгоритма заключается в том, чтобы построить разбиение (Fi, V2) множества вершин аппроксимируемого графа, основываясь па разбиении выборки вершин небольшого объема. Это небольшое разбиение затем расширяется вершинами, для которых отношение приращения целевой функции к мощности выборки не больше (1 + 6)/4. Оставшиеся вершины распределяются но принципу жадного алгоритма.

Трудоемкость алгоритма А(5,с) зависит от параметра с и составляет 0(псЫ2+2).

Теорема 2.6. С вероятностью, не меньшей 1 — 0(1/пк), где к -некоторая константа, для решения (Vj, V2) задачи Aj, полученного алгоритмом А(5, с), справедливо неравенство:

W,v2)< sVp + 8_p) (4)

где (V{, V2 ) - оптимальное решение задачи А|.

Легко видеть, что при 5 —» 1 правая часть неравенства (4) стремится к 2/(Vj*, V2*). Однако, при этом уменьшается константа к, зависящая от <5 и с, что ведет к уменьшению вероятности выполнения неравенства (4).

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

В разделе 3.1 приведено описание вычислительного эксперимента. Цель эксперимента заключается в том, чтобы сравнить три приближенных алгоритма решения задачи А\ и выявить лучший из них.

Эксперимент проводился на случайных n-вершинных графах G(n,p), которые получаются с помощью следующей процедуры: для каждой пары вершин и, v проводится независимый случайный эксперимент, исходами которого будут наличие ребра uv с вероятностью р и отсутствие ребра

с вероятностью 1 — р. Параметр р в используемой вероятностной модели представляет собой математическое ожидание плотности случайного графа G — (V, Е), которая определяется как ■ В проведенном эксперименте использовались значения р из множества {0.1,0.2,0.3,0.4,0.5}. Причину, но которой не рассматривались значения р > 0.5, можно объяснить, используя следующее свойство задачи А^.

Лемма 3.1. Пусть граф G = {V,E) - вход задачи Aj. Выберем произвольную вершину V G V и рассмотрим граф Gv — (V, Е„), где

Ev = Е \ {uv : uv е Е] U {uu : uv g Е}.

Пусть (Vi*, ) оптимальное решение задачи Aj на графе G и v (Е. V{. Тогда (V^* \ {v}, V2* U {и}) оптимальное решение задачи А\ на графе Gv, причем оптимальные значения целевой функции (2) совпадают.

Результат леммы 3.1 позволяет при изучении задачи А^ рассматривать графы, в которых степень каждой вершины не превосходит Следовательно, плотность таких графов не будет превосходить 0.5. Это означает, что для эксперимента можно ограничиться значениями р из интервала (0,0.5].

В разделе 3.2 приведено описание точного алгоритма решения задачи Ад на основе метода ветвей и границ, а также трех эвристических алгоритмов: градиентного алгоритма Gr; алгоритма Т, идея которого содержится в работе И.Томсску6; вероятностного алгоритма Рг, который является модификацией алгоритма А(<5,с) при S — 0.5 и с = 1.2.

Напомним, что алгоритмы Gr и Т являются асимптотически точными на редких графах.

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

Предварительный эксперимент проводился на графах размерности 20, 25, 30, 35, 40 вершин, по 400 графов в серии. Для таких графов методом ветвей и границ удалось найти точные решения и вычислить погрешности исследуемых алгоритмов.

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

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

1,1 1 лв 1.08 1,07 1.0в 1.0в 1,04 1,03 1Я2 IjOI 1

20 25 30 3 5 40

Рис. 1: Средняя погрешность алгоритмов Gr, Т и Рг на графах малой размерности.

нию целевой функции. Обозначим ¿Gr(rc)> и <5рг(п) погрешности

алгоритмов Gr, Т и Рг, соответственно.

По итогам предварительного эксперимента удалось получить представление о характере изменения средней погрешности эвристических алгоритмов (рис. 1). Для алгоритмов Gr и Т отмечено убывание погрешности с ростом размерности графа. Наиболее перспективным приближенным алгоритмом можно считать алгоритм Gr, поэтому в качестве объекта дальнейшего исследования были выбраны две случайные величины:

6Рт(п) 6т(п)

Ррг{п) = т—т—г» Рт{п) = с > v.

°Gr("J àGr (n)

В эксперименте на графах G(n,p) большой размерности (при п от 60 до 1000, решалось по 200 задач в серии) исследовалось поведение случайных величин ррг(п) и рт(п). Тенденции изменения средних значений и границ доверительных интервалов при уровне значимости 0.05 представлены на рисунке 2. Комментируя результаты, можно сказать следующее.

На графах с р < 0.5 алгоритм Gr имеет подавляющее преимущество над алгоритмом Т, которое с ростом размерности задачи распространяется и на графы с р = 0.5. При увеличении числа вершин в графе наблюдается уменьшение среднего значения случайной величины рт(п). Это можно объяснить тем, что скорость убывания погрешности алгорит-

1.СХ38

юге-

1,013 •

1.000

0Ц»в

п

0.875

90

1» 180 180 210 213

500 700

Рис. 2: Средние значения случайных величин ррг(п) и рт{п) при р = 0.3. ма Т несколько больше, нем скорость убывания погрешности алгоритма

При п > 240 нижняя граница доверительного интервала случайной величины ррт(п) была больше 1 при всех значениях р. Это позволяет говорить о том, что использование алгоритма Сг предпочтительнее использования алгоритма Рг на графах большой размерности.

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

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

Сг.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ильев В.П., Талевнин A.C. К задаче о наибольшем независимом множестве // Материалы Российской конф. «Дискретный анализ и исследование операций». Новосибирск, 2002. С. 211.

2. Талевнин A.C. К задаче о наибольшем независимом множестве в гиперграфе // Материалы ежегодного научного семинара аспирантов и студентов-выпускников «Под знаком «Сигма». Омск: ООО «Издатель-Полиграфист», 2003. С. 41-47.

3. Ильев В.П., Талевнин A.C. Оценки точности приближенных решений двух задач на наследственных системах // Тез.докл. XII Всерос. конф. «Математическое программирование и приложения». Екатеринбург, 2003. С. 225.

4. Ильев В.П., Талевнин A.C. О сложности и приближенном решении задачи аппроксимации графов // Материалы Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2003. С. 93.

5. Ильев В.П., Талевнин A.C. Две задачи на наследственных системах // Дискр. анализ и исслед. операций. Сер. 1. 2003. Т. 10, N 3. С. 54-66.

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

7. Талевнин A.C. Приближенный вероятностный алгоритм для одной задачи аппроксимации графов // Труды XIII Байкальской школы-семинара «Методы оптимизации и их приложения». Иркутск, 2005. Т. 1. С.583-588.

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

9. Талевнин A.C. Экспериментальное исследование алгоритмов приближенного решения задачи аппроксимации графов. Препринт. Омск: «Полиграфический центр КАН», 2006. 18 с.

Отпечатано с оригинал-макета, предоставленного автором

Подписано в печать 22,05.06. Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Уч. изд. л. 1,0. Тираж 120 экз. Заказ № 180.

Отпечатано в «Полиграфическом центре К АН» 644050, г. Омск, пр. Мира, 11а, тел. (3812) 65-23-73 Лицензия ПЛД № 58-47 от 21.04.97.

Введение

1 Общие задачи на наследственных системах

1.1 Наследственные системы. Определения и примеры.

1.1.1 Определения и постановки задач на наследственных системах.

1.1.2 Некоторые задачи на графах и соответствующие наследственные системы.

1.2 Задача о наибольшем независимом множестве.

1.2.1 Приближенный алгоритм для задачи о наибольшем независимом множестве.

1.2.2 Оценка погрешности алгоритма для задачи о наибольшем независимом множестве.

1.3 Задача о наименьшем зависимом множестве.

1.3.1 Связь задачи о наименьшем зависимом множестве с задачей о покрытии множеств

1.3.2 Оценка погрешности приближенного алгоритма для задачи о наименьшем зависимом множестве.

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

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

2.1.1 Определения и постановки задачи аппроксимации графа.

2.1.2 Задача о бисекции графа.

2.2 Сложность задачи аппроксимации графа.

2.2.1 Вычислительная сложность задачи аппроксимации графами с фиксированным числом компонент

2.2.2 Полиномиальная аппроксимационная схема для задачи А\.

2.3 Приближенные алгоритмы для задачи

2.3.1 Асимптотически точные алгоритмы для задачи А на редких графах.

2.3.2 Вероятностный приближенный алгоритм для задачи аппроксимации графа А^.

3 Экспериментальное исследование приближенных алгоритмов для задачи аппроксимации графов

3.1 Описание вычислительного эксперимента.

3.2 Точный и приближенные алгоритмы для задачи аппроксимации А\.

3.2.1 Градиентный алгоритм

3.2.2 Алгоритм Томеску.

3.2.3 Приближенный вероятностный алгоритм.

3.2.4 Метод ветвей и границ для задачи А^.

3.3 Результаты экспериментального исследования.

3.3.1 Предварительный эксперимент и выдвижение гипотез

3.3.2 Экспериментальная проверка гипотез на графах большой размерности.

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

Наследственная система представляет собой семейство подмножеств конечного множества, обладающее свойством наследственности: подмножество любого множества, входящего в семейство, само является элементом этого семейства. Наследственные системы можно рассматривать как формализованные модели реальных систем. В соответствии с одним из принятых в системном анализе определений, система есть совокупность взаимосвязанных объектов, обособленная от среды и взаимодействующая с ней как целое [14].

Широко распространенной моделью реальных систем является также структурная схема системы. В структурной схеме указываются все элементы системы, все связи между элементами внутри системы, а также связи определенных элементов с окружающей средой (входы и выходы системы). Абстрагируясь от содержательной стороны структурной схемы и выявляя ее математическую сущность, мы получаем абстрактную схему, в которой содержится только информация о наличии элементов и связей между ними. Такая схема называется графом, вершины которого соответствуют элементам системы, а ребра - наличию связей между элементами. Таким образом, графы являются адекватными и наглядными математическими моделями реальных систем. Графы могут также содержать дополнительную информацию о системе. Например, если требуется отразить несимметричность связей, то ребра снабжают стрелками и получают ориентированный граф; в случае необходимости указать другие различия между элементами или связями, приписывают вершинам или ребрам графа веса и получают взвешенный граф, и т.д.

В процессе взаимодействия со средой система способна изменятся, переходя из одного состояния в другое. Широко трактуя будущее состояние системы как цель, можно также определить систему как средство достижения цели [14]. Разумеется, сложные системы могут иметь не одну, а множество целей. Эти цели могут быть субъективными (идеальные образы желаемых состояний искусственных систем, созданных человеком, а также систем смешанного типа, испытывающих влияние человеческого фактора) и объективными (будущие реальные состояния систем, в том числе естественных, существующих независимо от человека).

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

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

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

В диссертации реализуются все три названных подхода. Получены гарантированные оценки погрешности приближенных алгоритмов решения задач о наибольшем независимом множестве и наименьшем зависимом множестве наследственной системы. Определена вычислительная сложность (в худшем случае) задачи аппроксимации графа и для одного варианта задачи предложен вероятностный алгоритм. Для исследования качества другого приближенного алгоритма решения задачи аппроксимации графа использована идея построения алгоритмов с оценками, предложенная Э.Х. Гимади, Н.И. Глебовым и В.А. Перепелицей [3, 4]. Проведено экспериментальное исследование приближенных алгоритмов решения задачи аппроксимации графа.

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

Наследственные системы

Пусть V - конечное множество. Системой независимости на V называется пара (V, Д), где Л С 2У - непустое семейство подмножеств V, такое, что

АеЛиА'СЛ=>А'еЛ аксиома наследственности). Множества семейства А называютсялеза-висимыми, а все подмножества из 2У \ А - зависимыми. Семейство всех зависимых множеств обозначим через Т>. Легко видеть, что Т> обладает свойством наследственности «вверх»: если

ДеРи^С!)', то Б' € V.

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

В [39] наследственная система Б на множестве V определяется как разбиение семейства 2У всех подмножеств V на два непересекающихся подсемейства А и V, где (V, Л) - система независимости, а V = 2У \ А. Базами системы £ называются максимальные по включению независимые, а циклами - минимальные по включению зависимые множества. Семейства всех баз и всех циклов системы «5 будем обозначать через Б и С соответственно. Очевидно, что каждое из семейств В, С также однозначно определяет наследственную систему «5. Будем записывать 5 = (V, А), Я = (V, В), в = (V, С) или 5 = (V, V) в зависимости от того, какая сторона наследственной системы нас в данный момент интересует.

С каждой наследственной системой «5 = (V, Л) тесно связана дополнительная система с?', семейство зависимых множеств которой определяется как V = {V \ А | А е А}. Очевидно, что семейства независимых множеств, баз и циклов системы ¿>' могут быть заданы как л = {V \ И I и е V}, Б' = {V \ с I С е С}, С = {V \ в I в е В}.

Ясно, что (¿>'У = 5, т. е. наследственные системы ¿> и взаимно дополнительны.

Пример. Наследственная система графа и дополнительная к ней. Рассмотрим произвольный (связный) граф С? = (V, Е) и наследственную систему = (V, Д&), где Ав ~ семейство всех независимых множеств вершин графа (3. Тогда Во есть семейство всех максимальных по включению независимых множеств вершин. Легко видеть, что любой цикл системы имеет мощность 2 и соответствует ребру графа С?. Известно, что вершинными покрытиями в графе являются дополнения независимых множеств и только они. Поэтому семейство Т>д всех вершинных покрытий в произвольном графе С? = (V, Е) можно рассматривать как семейство зависимых множеств наследственной системы Бд = {У,Т>о), дополнительной к наследственной системе графа. Циклами системы Бд являются минимальные по включению вершинные покрытия, а базами -максимальные непокрытия, т.е. дополнения ребер графа Заметим, что система обычно задается с помощью графа (7, например, перечнем его ребер, что равносильно заданию наследственной системы «5^ с помощью семейства баз В'с.

Рассмотрим наследственную систему ¿> = (У, А) и множество IV С V. Базой мнооюества IV называется любое максимальное по включению независимое множество, содержащееся в IV.

Для произвольной наследственной системы S = (V, Л) обозначим: tl{W) = min{|B| : В - база множества W}, ru(W) = max{|B| : В - база множества W}.

Числа rL(W),ru(W) называются соответственно нижним и верхним рангом мноэ/сества W. Величина я\ • TLW

СА — с j (о) = mm —7—7 л АК } wcvru(W) называется кривизной системы независимости или просто кривизной независимости наследственной системы S. Очевидно, что 0 < сд < 1 для любой наследственной системы. В случае сд = 1 система S = (V, А) называется матроидом.

Матроиды были введены в 1935 г. Уитни как абстрактный объект со свойствами, обобщающими свойства линейной независимости в векторных пространствах [45]. Матроиды оказались универсальными комбинаторными объектами, объединяющими в себе черты таких разных математических понятий, как семейства остовных деревьев связного графа, семейства частичных трансверсалей, геометрические решетки и т.д. Достаточно полное введение в теорию матроидов можно найти в книге [2].

Циклом множества W С V называется любое минимальное по включению зависимое множество, содержащее W.

Для произвольной наследственной системы S = (V, V) обозначим: gL{W) = min{|C| : С - цикл множества W}, gu(W) = max{|C| : С - цикл множества W}.

Числаgb(W),gu(W) называются соответственно нижним и верхним обхватом множества W. Величина

9u(W) - \W\ Cv = CV{S) = max———-—T называется кривизной системы зависимости или просто кривизной зависимости наследственной системы ¿>. Очевидно, что ср > 1 для любой наследственной системы. В случае с-р = 1 система 5 = (VV) называется коматроидом. Коматроиды под именем верхних матроидов изучались М.М. Ковалевым [12].

В работе [39] доказано, что

Наследственная система является матроидом тогда и только тогда, когда ее дополнительная система - коматроид.

Задача о максимальном независимом множестве наследственной системы

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

Задача 1 (о максимальном независимом множестве). Дана наследственная система 5 на множестве V и аддитивная весовая функция / : V —> Я+. Требуется найти независимое множество системы е> максимального веса.

Обычно предполагается, что система ¿> задана при помощи оракула независимости. На практике это означает, что существует эффективный метод проверки независимости множества.

К задаче 1 сводятся или ее частными случаями являются многие ИР-трудные задачи дискретной оптимизации, такие, как задача о максимальном независимом множестве вершин графа, задача о максимальном паросочетании, задача о рюкзаке и другие.

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

Одним из центральных результатов теории матроидов является классическая теорема Радо-Эдмондса [31, 41]:

Задача 1 разрешима жадным алгоритмом для любой аддитивной целевой функции тогда и только тогда, когда наследственная система <5 является матроидом.

Независимо без использования аппарата теории матроидов Н.И. Глебов [5] доказал более общий результат о разрешимости алгоритмом покоординатного подъема задач максимизации вогнутой сепарабельной функции на целочисленном полиматроиде. В [19] установлены критерии разрешимости жадным алгоритмом задач максимизации аддитивных функций, области допустимых решений которых удовлетворяют более слабым ограничениям.

Как следует из теоремы Радо-Эдмондса, в случае, когда наследственная система не является матроидом, жадный алгоритм может не найти оптимального решения задачи 1. Т.А. Дженкинс [40] и, независимо, Б. Корте и Д. Хаусманн [37, 38] доказали точную нижнюю оценку погрешности жадного алгоритма для задачи 1 в терминах кривизны системы независимости:

Для любой системы независимости ¿> = (V, Л) кривизны сд и любой аддитивной целевой функции задачи 1 жадный алгоритм гарантированно находит приближенное решение Б, для которого > -/(в.) где 50 - оптимальное решение задачи 1.

Невзвешенную задачу 1 можно рассматривать как задачу о наибольшем независимом множестве вершин гиперграфа. Напомним, что гиперграфом называется пара Н = (V, Е), где V = У(Н) - непустое конечное множество, а Е = Е{Н) - семейство подмножеств V. Элементы множества V называются вершинами, а элементы семейства Е - ребрами гиперграфа Н.

Множество вершин гиперграфа называется независимым, если никакое ребро гиперграфа не является его подмножеством.

Рассмотрим следующую задачу.

Задача 1° (о наибольшем независимом мноэюестве вершин гиперграфа).

Дан гиперграф Н = (V, Е). Найти независимое множество его вершин, имеющее наибольшую мощность.

Очевидно, что при удалении из Н ребра, содержащего другое ребро как подмножество, семейство допустимых решений этой задачи не изменяется. Поэтому далее будем рассматривать только гиперграфы, в которых ни одно ребро не содержит другое в качестве подмножества. Любой такой гиперграф Н порождает наследственную систему <5>я, независимыми множествами которой являются независимые множества вершин Н. Следовательно, задача 1° о наибольшем независимом множестве вершин гиперграфа Н - это невзвешенная задача 1 на системе <5#.

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

В работе [33] для задачи 1, которую можно рассматривать как взвешенную задачу о максимальном независимом множестве вершин гиперграфа, предложен \V\/log\V¡-приближенный алгоритм. В случае, когда Н является графом, известен ¡V^/log2 |V¡-приближенный алгоритм [27], а один из вариантов жадного алгоритма является одновременно (сМ-2)/2-и (А + 2)/3-приближенным алгоритмом решения задачи 1° на графе [34], где d и Д - средняя и максимальная степени вершин в графе соответственно.

Задача о минимальном зависимом множестве наследственной системы

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

Задача 2 [о минимальном зависимом множестве). Дана наследственная система S на множестве V и аддитивная весовая функция / : V —R+. Требуется найти зависимое множество системы S минимального веса.

Как и в случае задачи о максимальном независимом множестве, предполагается, что система S задана при помощи оракула зависимости. На практике это означает, что существует эффективный метод проверки зависимости множества.

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

Задача 2 в общем случае была исследована В.П. Ильевым [8, 39], который доказал точную верхнюю оценку погрешности градиентного алгоритма - дискретного аналога алгоритма наискорейшего спуска:

Для любой наследственной системы S = (V,T>) кривизны зависимости ст> и любой аддитивной целевой функции задачи 2 градиентный алгоритм гарантированно находит приближенное решение S, для которого f(S) < ,

Ж)-1" где SQ - оптимальное решение задачи 2.

Как следствие может быть получен аналог теоремы Радо-Эдмондса для коматроидов [39]:

Задача 2 разрешима градиентным алгоритмом для любой аддитивной целевой функции тогда и только тогда, когда наследственная система S является коматроидом.

В работе [9] была установлена связь задачи 2 с задачей о покрытии множества, что позволяет для приближенного решения задачи 2 использовать алгоритмы решения задачи о покрытии. Обзор известных результатов по задаче о покрытии множества можно найти в [7].

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

К задаче 1 может быть сведена также известная задача аппроксимации графа. Постановки и различные интерпретации этой задачи можно найти в работах [11, 13, 46].

Будем рассматривать обыкновенные графы, т.е. графы без петель и кратных ребер. Граф называется M-графом, если каждая его компонента связности есть полный граф. Обозначим через Л4(У) класс всех М-графов на множестве вершин V, A4k(V) ~ класс всех М-графов на

15 множестве вершин V, имеющих ровно к непустых компонент связности, Л4ЦУ) ~ класс всех М-графов на множестве V, имеющих не более к компонент связности, 2 < к < \V\.

Если G\ и G2 ~ графы на одном и том же множестве вершин V, то расстояние между ними определяется как d(Gh G2) = \E(G\) \ E(G2)| + |E(G2) \ E{Gi) то есть d{Gi, G2) - число несовпадающих ребер в графах G\ и G2.

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

Задача А. Дан граф G= (V, Е). Найти такой граф М* GM{V), что d(G, М*) = min d(G, М) ^ t(G). v ' MGM(V) v ' 4 '

Задача Ak. Дан граф G= (V, Е) и целое число к, 2 < к < \V\. Найти dp,

Задача AJ и величина tI(G) определяются аналогично. такой граф M*eMk(V), что d(G, М*) = min d(G, М) = rk(G).

MeMk(V)

Г.Ш. Фридманом [16, 17] доказано следующее утверждение: Для любого п-вершиниого графа С имеет место оценка

ПО) <

Как показал И. Томеску [43, 44], аналогичная оценка справедлива и в задаче А£:

Для любого к > 2 и любого п-вершинного графа G < Щ^].

Наконец, В.П. Ильев и Г.Ш. Фридман [10] показали, что Для любого к > 2 и любого п-вершинного графа (7 при п > 5(к — 1) имеет место оценка тк(С) < п - l)s

4 16

Исследовались также ориентированные и взвешенные варианты задач аппроксимации графов. В ориентированных задачах каждая бикомпо-нента аппроксимирующего орграфа является полным симметрическим графом и отсутствуют дуги, ведущие из одной бикомпоненты в другую. Во взвешенных вариантах задана весовая функция т : V х V —> N и <¿((71, (З2) равно суммарному весу несовпадающих рёбер в графах Сп и Сг2- Известно [18], что ориентированная задача А с некоторыми дополнительными условиями ./УР-трудна.

Вычислительная сложность задач А, Ак, А£ аппроксимации графов до последнего времени оставалась неизвестной. Лишь недавно удалось доказать, что все эти задачи, а также их взвешенные и ориентированные аналоги Л^Р-трудны [1].

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

Для произвольного графа б? = (У,Е) построим граф С = (V7, Е'), полученный из (3 заменой каждого ребра цепью длины 2 и добавлением всех ребер вида иу, где иу ф Е, и,у Е. V.

Легко видеть, что граф 6? принадлежит классу М\(У), если и только если С = (V7, Е') является двудольным графом. Поэтому для любого графа С? = {V, Е) существует взаимно-однозначное соответствие между М-графами из класса М.\(у) и максимальными по включению двудольными подграфами графа С = (V7, Е'). При этом удаление ребра иу Е Е графа С соответствует удалению одного из ребер цепи длины 2, соединяющей вершины и и у в графе С, а добавление ребра иу ф Е к графу С соответствует удалению ребра иу из графа С. Таким образом, задача А1 на графе С = (V, Е) эквивалентна задаче отыскания наибольшего по числу ребер двудольного подграфа графа С = (V7, Е').

Двудольные подграфы графа С = (У,Е'), рассматриваемые как множества ребер, образуют семейство независимых множеств наследственной системы ^ = (Е',А). Следовательно, задачу А.\ можно рассматривать как невзвешенную задачу 1 на системе ¿> = (Е',А).

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

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

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

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

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

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

Заключение

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

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

2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика». 2001.

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

4. Гимади Э.Х., Перепелица В.А. Асимптотический подход к решению задачи коммивояжера // Управляемые системы. Новосибирск: Ин-т математики СО АН СССР. 1974. Вып. 12. С. 35-45.

5. Глебов Н.И. Об одном классе задачв выпуклого целочисленного программирования // Управляемые системы. Новосибирск: Ин-т математики СО АН СССР. 1973. Вып. 11. С. 38-42.

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

7. Еремеев A.B., Заозерская JI.A., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. // Дискрет, анализ и исслед. операций. Сер. 2. 2000. Т. 7, N 2. С. 22-46.

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

9. Ильев В.П., Талевнин A.C. Две задачи на наследственных системах // Дискретный анализ и исследование операций. 2003. Сер. 1. Т. 10, N 3. С. 54-66.

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

11. Кемени Дж., Снелл Дж. Кибернетическое моделирование. М.: Сов. радио, 1972.

12. Ковалев М.М. Матроиды в дискретной оптимизации. Минск: Университетское. 1987.

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

14. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа. Томск: НТЛ. 1997.

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

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

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

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

19. Шенмайер В.В. Максимизация линейной целевой функции с помощью жадного алгоритма // Дискрет, анализ и исслед. операций. Сер. 1. 1999. Т. 6, N 4. С. 104-120.

20. Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике // М.: Мир, 1976.

21. Alon N., Spencer J.H. The probabilistic method // New York: Wiley and Sons, 1992.

22. Arora S., Karger D., and Karpinski M. Polynomial time approximation schemes for dense instances of NP-haid problems // Proc. 27th Ann. ACM Symp. on Theory of Сотр. 1995. P. 284-293.

23. Arora S., Lund C. Hardness of approximations // Approximation Algorithms for NP-hard problems, Ed. by D.S.Hochbaum, PWS Publishing Company, 1995, p. 399-445.

24. Bellare M., Rompel J. Randomness-efficient oblivious sampling // Proc. 35th Ann. Symp. on Found, of Сотр. Science, 1994, p. 276-287.

25. Berman P. and Karpinski M. Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION // ECCC. Technical report TR01-26.

26. Bollobas B. The chromatic number of random graphs // Combinatorica. 1988. V.8, P.49-55.

27. Boppana R. B., Halldorsson M. M. Approximating maximum independent sets by excluding subgraphs // BIT. 1992. V. 32, N 2. P. 180-196.

28. Chvatal V. A greedy heuristic for the set-covering problem // Math. Oper. Res. 1979. V. 4, N 3. P. 233-235.

29. Edmonds J. Paths, trees and flowers // Canadian Math. J. 1965. V. 17, P. 449.

30. Edmonds J. Maximum matching and a polyhedron with 0-1 vertices // J. of Res., Nat. Bur. of Stand. 1965. V. 69B, P. 125-.

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

32. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // J. of ACM. 1972. V. 19, N 2. P. 248-264.

33. Halldorsson M. M. Approximations of weighted independent set and hereditary subset problems //J. Graph Algorithms Appl. 2000. V. 4, N 1. P. 1-16.

34. 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.

35. Hastad J. Fast and efficient testing of the long code. //Proc. ACM STOC. 1996.

36. Hâstad J. Some optimal inapproximability results // Proc. 29th Ann. ACM Symp. on Theory of Comp. 1997. P. 1-10.

37. Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete math. 1978. V. 24, N 3. P. 261-276.

38. Hausmann D., Korte B. An analysis of the greedy heuristic for independence systems // Ann. Discrete Math. 1978. V. 2, N 3. P. 65-74.

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

40. Jenkyns Th.A. The efficacy of the «greedy» algorithm // Proc. of the 7th S-E Conf. on Combinatorics, Graph Theory, and Computing. Winnipeg: Utilitas Math. 1976. P. 341-350.

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

42. Sahni S.K., Gonzales T.F. P-complete approximation problems //J. ACM. 1976. V. 23. P. 555-565.

43. 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.

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

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

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

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

48. Ильев В.П., Талевнин A.C. К задаче о наибольшем независимом множестве // Материалы Российской конф. «Дискр. анализ и ис-след. операций». Новосибирск, 2002. С. 211.

49. Талевнин A.C. К задаче о наибольшем независимом множестве в гиперграфе // Материалы ежегодного научного семинара аспирантов и студентов-выпускников «Под знаком «Сигма». Омск: ООО «Издатель-Полиграфист», 2003. С. 41-47.

50. Ильев В.П., Талевнин A.C. Оценки точности приближенных решений двух задач на наследственных системах // Тез.докл. XII Все-рос. конф. «Матем. программирование и приложения». Екатеринбург, 2003. С. 225.

51. Ильев В.П., Талевнин A.C. О сложности и приближенном решении задачи аппроксимации графов// Материалы Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2003. С. 93.

52. Ильев В.П., Талевнин A.C. Две задачи на наследственных системах // Дискретный анализ и исследование операций. 2003. Сер. 1. Т. 10, N 3. С. 54-66.

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

54. Талевнин A.C. Приближенный вероятностный алгоритм для одной задачи аппроксимации графов // Труды XIII Байкальской школы-семинара «Методы оптимизации и их приложения». Иркутск, 2005. Т. 1. С.583-588.

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

56. Талевнин A.C. Экспериментальное исследование алгоритмов приближенного решения задачи аппроксимации графов. Препринт. Омск: «Полиграфический центр КАН», 2006. с.18.