Сложность аппроксимации оптимизационных задач на наследственных системах тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Талевнин, Антон Степанович

• Талевнин, Антон Степанович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Талевнин, Антон Степанович

Введение

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. Предложены эвристические алгоритмы решения одного варианта задачи аппроксимации графа, для поиска оптимальных решений разработан и реализован точный алгоритм на основе метода ветвей и границ. Проведенное экспериментальное исследование эвристических алгоритмов показало, что решения, найденные этими алгоритмами, как правило, достаточно близки к оптимальным.

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Талевнин, Антон Степанович, 2006 год

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.