Задачи оптимизации и аппроксимации на наследственных системах тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Ильев, Виктор Петрович

• Ильев, Виктор Петрович
• доктор физико-математических наук
• 2010

Оглавление диссертации доктор физико-математических наук Ильев, Виктор Петрович

Введение

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

1.1. Основные понятия.

1.2. Наследственные системы целочисленных векторов.

1.3. Наследственные системы и графы.

1.3.1. Графы баз и циклов.

1.3.2. Наследственные системы графов.

1.4. Наследственные системы и решетки.

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

1.4.2. Решетки замкнутых множеств наследственных систем

1.4.3. Решетки открытых множеств коматроидов.

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

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

2.2. Задачи на наследственных системах с аддитивными целевыми функциями.

2.2.1. Теорема Радо-Эдмондса и ее аналог для коматроидов

2.2.2. Оценки погрешности жадных алгоритмов для задач на наследственных системах

2.2.3. Примеры

2.2.4. Эквивалентность задачи о минимальном зависимом множестве и задачи о покрытии множества.

2.3. Оценки погрешности жадных алгоритмов в терминах допустимой области и целевой функции.

2.3.1. Уточнение оценки Дженкинса-Корте-Хаусмана

2.3.2. Оценка погрешности обратного жадного алгоритма

2.4. Задачи с неаддитивными целевыми функциями.

2.4.1. Обобщения теоремы Радо-Эдмондса.

2.4.2. Задачи, разрешимые жадным алгоритмом

3. Минимизация супермодулярных функций на матроидах и коматроидах

3.1. Задачи минимизации супермодулярных функций.

3.1.1. Постановки задач и известные результаты

3.1.2. Обобщения понятия супермодулярной функции

3.1.3. Свойства супермодулярных функций

3.2. Оценки погрешности обратного жадного алгоритма минимизации невозрастающей супермодулярной функции

3.2.1. Оценки в терминах параметров целевой функции и допустимой области.

3.2.2. Оценки погрешности обратного жадного алгоритма в терминах параметров целевой функции.

3.2.3. Апостериорная оценка.

3.3. Следствия для задачи о р-медиане на минимум.

3.4. Минимизация неубывающих супермодулярных функций

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

4.1. Задачи матроидной аппроксимации.

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

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

4.2.2. Оценка аппроксимационной сложности графа

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

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

4.4.2. Невзвешенные задачи.

4.5. Приближенное решение задачи аппроксимации графа

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

4.5.2. Гарантированно асимптотически точный алгоритм и полиномиальная приближенная схема

4.5.3. Алгоритмы с константными оценками точности

Введение диссертации (часть автореферата) на тему «Задачи оптимизации и аппроксимации на наследственных системах»

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

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

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

На фоне бурного развития теории матроидов наблюдается также рост интереса к жадным алгоритмам (см., например, [63,79,91]). Это объясняется тем, что в ряде случаев жадный алгоритм имеет максимальную точность в классе полиномиальных алгоритмов [92], либо является асимптотически точным алгоритмом [13].

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

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

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

Пусть 17 — непустое конечное множество, ЛС.2и — непустое семейство его подмножеств, удовлетворяющих следующей аксиоме наследств енноemu:

Ai еЛ, A2 с Ax) A2gA.

Множества семейства А называются независимыми, а само семейство А в литературе обычно называют системой независимости или наследственным семейством [88]. Через В обозначим семейство всех баз, т. е. максимальных по включению множеств семейства А.

Очень многие задачи комбинаторной оптимизации могут быть сформулированы следующим образом: extr{f(X) :XgB}, (1) где / : 2и —> R+ — монотонная неотрицательная функция множеств. Здесь запись extr{f(X) : X G В} означает, что мы будем рассматривать как задачу max{/(X) : X G В}, так и задачу min{f(X) : X G В}, ссылаясь на них как на максимизационную задачу (1) и на задачу минимизации (1), соответственно.

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

В то же время имеется большое число задач комбинаторной оптимизации, которые можно рассматривать как частные случаи следующих оптимизационных задач: extr{/pO : X G С}, (2) где / : 2и —> R+ — монотонная неотрицательная функция множеств, а С — семейство циклов (т. е. минимальных по включению множеств) непустого семейства Т> С 2и подмножеств U, обладающего свойством наследственности "вверх":

Di G Т>, Di С D2) =>D2eT>.

К ним относятся, в частности, задача о покрытии множества и ее частный случай — задача о минимальном вершинном покрытии в графе, задача об остовном /с-связном подграфе минимального веса и другие. Некоторые задачи, такие как уже упомянутые задачи об остовном дереве и о р-медиане, одинаково хорошо сводятся как к модели (1), так и к модели (2).

Множества семейства Т> обычно называют зависимыми, поэтому семейство Т> было бы естественно называть системой зависимости на U. Заметим однако, что каждая система независимости А однозначно определяет систему зависимости Т> — 2и \ А, и наоборот. Поэтому их можно рассматривать как различные стороны одного и того же универсального объекта, который мы будем называть наследственной системой.

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

Наследственные системы и их частные случаи — матроиды и кома-троиды — естественным образом возникают в различных областях математики, таких как линейная алгебра, теория графов, теория транс-версалей (см. [5, 20,127]) и других разделах комбинаторного анализа, например, при изучении свойств комбинаторных геометрий [78] или ко-митетной разрешимости систем ограничений [112].

Матроиды и коматроиды

Важным частным случаем понятия наследственной системы является понятие матроида, введенное в 1935 г. Уитни [129]. Исследуя комбинаторные характеристики планарных графов, Уитни обратил внимание на то, что некоторые алгебраические свойства графов аналогичны свойствам векторных пространств. Обобщение этих свойств привело к нескольким аксиоматическим определениям матриода (в терминах баз, циклов, независимых множеств, ранговой функции и др.) Приблизительно в то же время Биркгоф обнаружил подобные свойства в решетках [66], а Мак-лейн — в проективной геометрии [110]. Впрочем, годом рождения теории матроидов можно считать 1930 г., когда Ван дер Варден первым предложил аксиоиматический подход к понятию линейной и алгебраической независимости (см. [9]).

Матроид на множестве С/ может быть определен как наследственная система М = (С/, А), в которой все базы любого множества У/ € V имеют одинаковую мощность (базой множества \¥ называется любое его максимальное по включению независимое подмножество). Рангом матроида называется мощность любой базы множества и.

Примером матроида является р-однородный матроид Мр = (и>Ар), где Ар = {А С и : \А\ ^ р}, р — натуральное число, р < |£/|.

Хорошо известно определение матроида в терминах оператора замыкания, выявляющее связь матроидов и комбинаторных геометрий. Отображение X X множества 2и в себя называется оператором замыкания, если для всех X, У С II выполняются следующие условия:

Щ) 1С1, (Тр2) (срЗ) Т = Х.

Множество X С и называется замкнутым, если X == X.

Пара М — (и,Тр) называется матроидом (или комбинаторной пред-геометрией) на и, если для всех и,у Е II я X С и выполняется аксиома замены:

Тр4) и £ х, и е ХиН V е хи {«}. Матроид называют простым (или комбинаторной геометрией), если (у?5) 0 = 0 и {и} — {п} для всех и Е11.

Постепенно выяснилось, что матроиды сочетают в себе черты многих математических объектов из различных областей математики, таких как линейная алгебра, геометрия, теория графов, теория трансверсалей и т. д. Фундаментальная теорема Биркгофа-Уитни, раскрывающая связь между матроидами и геометрическими решетками, привела к тому, что понятие матроида стало центральным в комбинаторной теории решеток (см. [4]):

Пусть М= (U,Tp) — матроид на множестве U. Тогда решетка его замкнутых множеств — геометрическая.

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

По этой причине в книге Биркгофа [7] геометрические решетки названы матроидными.

Работы Радо [115,116], Дилуорса [80,81] и Татта [123-125] подстегнули исследовательский интерес к теории матроидов, бурное развитие которой пришлось на 70-80-е годы XX в. и продолжается до сих пор. Были предложены многочисленные обобщения понятия матроида (по-лиматроиды [84], суперматроиды [82], базисные системы [16], матроиды Кокстера [70] и т. д.). Наиболее полно теория матроидов представлена в книгах [127,128]. Теоретико-множественный подход, в основе которого лежит определение матроида через оператор замыкания, достаточно подробно изложен в монографии Айгнера [4]. В ней же нашли отражение некоторые геометрические аспекты теории матроидов. Введение в теорию матроидов, базирующееся на том же подходе, можно найти в книге Асанова, Баранского и Расина [5]. Книга Емеличева, Мельникова, Сар-ванова и Тышкевич [20] содержит элементарное изложение основ теории матроидов, специально приспособленное, по выражению авторов, к нуждам теории графов.

Имеются различные подходы к изучению структуры матроидов. Один из самых наглядных состоит в следующем. Матроиду М = (U, В) ставится в соответствие обыкновенный граф, вершины которого взаимно однозначно соответствуют базам матроида, а ребра — парам баз, различающимся ровно одним элементом. Такой граф называется графом баз или базисным графом матроида. Графы баз изучались на протяжении ряда лет различными авторами [69,95,111]. Маурер [111] предложил ха-рактеризацию графов баз матроидов в терминах их локальных подграфов. Позже этот результат был обобщен на графы баз целочисленных полиматроидов [24].

С каждой наследственной системой 5 = (£/, А) тесно связана дополнительная система или косистема семейство зависимых множеств которой определяется как ТУ = {II \А:Ае А}. Нетрудно проверить, что семейства независимых множеств, баз и циклов системы могут быть заданы как Л' = {И \ В : В 6 V}, В' = {И \ С : Се С}, С = {II \ В : В £ В}. Ясно, что (5/)/ = 5, так что наследственные системы в и Б' взаимно дополнительны.

В качестве примера рассмотрим наследственную систему графа и дополнительную к ней. Если С? = (V, Е) — обыкновенный граф, то наследственной системой графа С будем называть наследственную систему = (К*^), гДе »4<з ~ семейство всех независимых множеств вершин графа С. Циклы этой системы взаимно однозначно соответствуют ребрам графа С?. Хорошо известно, что дополнениями независимых множеств в графе являются вершинные покрытия. Поэтому семейство ТУС = {У \ А : А £ Лс} всех вершинных покрытий в графе (7 будет семейством зависимых множеств дополнительной наследственной системы

Наследственную систему, дополнительную к матроиду, будем называть коматроидом. Заметим, что коматроиды под именем верхних матроидов рассматривались Ковалевым [45].

Примером коматроида может служить р-однородный коматроид Кр = (и,Т>р), где Т>р = {В С и : |.0| ^ р}1 р — натуральное число, р <\и\. Очевидно, что этот коматроид дополнителен к (п — ^-однородному матроиду Мпр, где п = |£/|.

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

Оптимизационные задачи на наследственных системах

Наследственные системы и жадные алгоритмы

Вернемся к оптимизационным задачам ехЬт{/(Х) :ХеВ}, (1) ехЬт{/(Х) : X еС}, (2) где / : 2и —» — монотонная неотрицательная функция множеств, а В и С — семейства баз и циклов наследственной системы 5 = (и, Л) =

17,2?).

В большинстве задач, математическими моделями которых являются задачи (1) и (2), целевые функции являются аддитивными, субмодулярными или супермодулярными. Напомним, что функция множеств / : 2е7 —> В,+ называется субмодулярной, если для любых Х,У С II выполняется неравенство /(X и У) + /(X П У) ^ /(X) + /(У), и супермоду лярпой, если имеет место обратное неравенство. В случае равенства функцию / будем называть модулярной. Несложно показать, что неубывающая функция множеств с условием /(0) =0 модулярна тогда и только тогда, когда она аддитивна.

Многие задачи комбинаторной оптимизации, сводящиеся к схемам (1) и (2), являются МР-трудными.

Следующие три подхода к исследованию и решению МР-трудных оптимизационных задач являются общепринятыми [6]:

1) Разработка методов неявного перебора типа метода ветвей и границ;

2) Выделение полиномиально разрешимых классов подзадач;

3) Разработка приближенных полиномиальных алгоритмов с оценками точности получаемых решений.

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

Алгоритм G+ (жадный алгоритм).

Шаг 0. Хо 0, перейти на шаг 1.

Шаг г (г ^ 1). Выбрать такой Xi ^ Xi-i, что для задачи максимизации /(Xii U {xi}) = max U {ж}), x<£Xi-1, а для задачи минимизации

Xii и {Хг}) = min и {ж}).

Xi-iU{x}eA

Xi Xi^ 1 U {ajj}, перейти на шаг i + 1. Если такого Xi £ нет, то

Sg+ ^i-1

Конец.

Для приближенного решения задач (2) будем применять следующий "обратный" аналог жадного алгоритма.

Алгоритм G~ (обратный жадный алгоритм).

Шаг 0. Хо U, перейти на шаг 1.

Шаг г (г ^ 1). Выбрать такой Xi € что для задачи максимизации 7№1\{яг-})= max /(X<i \ {я}), а для задачи минимизации

Xii \ {Xi}) = min /(*<! \ {х}). xGXi-i,

Xi Xi-1 \ {a:i}, перейти на шаг г + 1. Если такого Xi 6 Х^j нет, то s'g

Конец.

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

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

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

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

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

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

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

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

Для подкласса Кп С /С задач размерности п говорят о семействах Рп и оценках (еп, 5п).

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

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

Если при этом все 5п = 0, то такой алгоритм называется гарантированно асимптотически точным.

Другими словами, алгоритм А гарантированно асимптотически точен на классе задач /С, если существует такая последовательность £п, что для любого п

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

Следует отметить, что между оптимизационными задачами (1) и (2) существует тесная связь. Так, во многих случаях оптимальное решение <5Ь максимизационной задачи (1) на наследственной системе 5 = (и, А) и оптимальное решение 3'0 задачи минимизации (2) на дополнительной системе = (£/, V) связаны соотношением = II \ Бо- Однако, чаще всего гарантированные оценки погрешности алгоритма приближенного решения одной из задач не могут быть использованы для получения подобных оценок для другой задачи. Например, для задачи о минимальном вершинном покрытии в графе известен простой 2-приближенный алгоритм [62], в то время как для задачи о максимальном независимом множестве вершин графа (которую можно рассматривать как задачу максимизации на дополнительной наследственной системе) приближенного алгоритма с подобной оценкой не существует, если Р ф NP [60]. Теорема Радо-Эдмондса и ее обобщения

Прототипом" жадного алгоритма послужил известный алгоритм Крас-кала, решающий точно задачу поиска остовного дерева максимального веса [109]. Радо [116] расширил применение этого алгоритма и доказал, что задача максимизации (1) с аддитивной целевой функцией на ма-троиде разрешима алгоритмом G+ (здесь следует отметить, что гораздо раньше подобный результат был установлен Борувкой [71], но остался практически неизвестным). "Жадным" ("greedy") алгоритм G+ впервые назвал Эдмондс [85], который усилил результат Радо:

Задача максимизации (1) на системе независимости разрешима оюадным алгоритмом G+ для любой аддитивной целевой'функции тогда и только тогда, когда данная система является матроидом.

Теорема Радо-Эдмондса является одной из центральных в теории ма-троидов. Ее можно рассматривать как еще одно эквивалентное определение матроида.

Многочисленные обобщения теоремы Радо-Эдмондса в основном были связаны с расширением допустимой области. Как правило, множество допустимых решений задачи (1) заменялось на систему достижимости, в которой для любого непустого допустимого множества существует его допустимое подмножество на единицу меньшей мощности. Примерами таких систем являются гридоиды и матроидные вложения (определения этих объектов будут даны в разделе 2.4.1). Так, в работах Корте и Ловаса [108] и Гоэтчела [86] охарактеризован класс гридоидов, на которых задача (1) разрешима жадным алгоритмом для любой аддитивной целевой функции, а в [58] Шенмайер установил аналогичные критерии для более общих классов задач. В статье Хельмана, Море и Шапиро [93] предельно расширен класс задач вида (1) с аддитивными целевыми функциями, разрешимых жадным алгоритмом. В этой статье доказано, что задача максимизации (1) на системе достижимости разрешима жадным алгоритмом для любой аддитивной целевой функции тогда и только тогда, когда допустимая область является матроидным вложением.

Обобщения теоремы Радо-Эдмондса за счет расширения класса целевых функций также сопровождались расширением допустимой области. В 1973 г. Глебов [14] независимо, не используя аппарат теории матроидов, доказал более общий, чем теорема Радо-Эдмондса, результат для задачи максимизации вогнутой сепарабельной функции на системе целочисленных векторов, обладающей свойством наследственности. Этот результат получил дальнейшее развитие в работах Глебова и Шенмайера [15,17]. В статье Корте и Ловаса [107] исследованы задачи на гридоидах с нелинейными (неаддитивными) целевыми функциями, а в уже упомянутой статье Хельмана, Море и Шапиро [93] описан класс целевых функций задач на матроидных вложениях, разрешимых жадным алгоритмом. Это так называемые согласованные функции, т. е. функции множеств, удовлетворяющие следующему условию: для любых множеств Т С Т' С U и для любых элементов х, у G U\T' таких, что /(TU {х}) ^ /(TU {?/}), имеет место неравенство f(T'U{x}) ^ f(T'U{y}). Очевидно, что любая аддитивная функция является согласованной.

Оценки погрешности жадного алгоритма для задачи максимизации аддитивной функции

Жадный алгоритм G+ представляет собой эффективный метод решения целого ряда дискретных оптимизационных задач. Как следует из теоремы Радо-Эдмондса, алгоритм G+ является точным алгоритмом решения задачи (1) с аддитивной целевой функцией на матроиде. Если же система S — не матроид, то алгоритм G+ в общем случае не находит оптимального решения и может рассматриваться лишь как приближенный метод решения задачи (1). В связи с этим большой интерес представляют оценки погрешности жадного алгоритма.

В работах Дженкинса [102], Корте и Хаусмана [92,106] получена следующая оценка погрешности алгоритма для задачи (1) максимизации аддитивной функции на наследственной системе.

Пусть Б = (и, Л) — произвольная наследственная система. Тогда для любой аддитивной целевой функции задачи максимизации (1) имеет место оценка

Ш > с{Л)> (3) где 5*0 — оптимальное решение задачи (1), — решение, полученное алгоритмом а с(Л) — кривизна системы независимости. Она определяется как с(Л) = ппп ---, wc.ii, гтах(И0 И где гт1П(1¥) и гтах(Ж) — минимальная и максимальная мощности баз множества соответственно, и характеризует близость наследственной системы 5 = (и, Л) к матроиду. Очевидно, что с(Л) ^ 1 для любой наследственной системы, причем с(Л) = 1 тогда и только тогда, когда система 5 является матроидом.

Кроме того, в [102,106] показано, что оценка (3) точна в следующем смысле: для любой наследственной системы 5 = (С/, Л) существует такая аддитивная функция / : 2и —> Я+, что

Для задачи минимизации (1), очевидно, имеет место неравенство ^ДЗо)^ ^ Однако> Для жадного алгоритма решения этой задачи в общем случае не существует верхней оценки погрешности, подобной (3). В статьях [92,106] показано, что алгоритм может давать сколь угодно плохое решение задачи минимизации (1) с аддитивной целевой функцией на наследственной системе, отличной от матроида. Это обстоятельство может служить основанием для вывода об ограниченной применимости жадного алгоритма для приближенного решения задач комбинаторной оптимизации, сводящихся к минимизационной схеме (1).

Лучших результатов позволяет добиться сведение таких задач к ми-нимизационной задаче (2) и применение обратного жадного алгоритма С?-. Подробнее об этом будет рассказано в главе 2.

Задачи с субмодулярными и супермодулярными целевыми функциями

Рассмотрим задачу максимизации (1), в которой В — семейство баз ма-троида ранга р, а / : — неубывающая субмодулярная функция множеств, /(0) = 0.

Частным случаем этой задачи является задача о р-медиане на максимум с целевой функцией /(X) = шахс^, где (с^-) — неотрицательная матрица размера п х т с множеством индексов строк I = и и множеством индексов столбцов J. Хорошо известно, что задача о р-медиане является КР-трудной [103].

В 1977 г. Корнуэджолс, Фишер и Немхаузер [77] получили оценку погрешности алгоритма для задачи о р-медиане на максимум:

Годом позже Немхаузер, Уолси и Фишер [113] обобщили оценку (4) для задачи максимизации неубывающей субмодулярной функции на р-одно-родном матроиде. В статье Конфорти и Корнуэджолса [76] эта оценка была уточнена с учетом дополнительной информации о целевой функции: где с € [0,1] — характеристика неубывающей субмодулярной функции /, описывающая замедление ее роста. Величина с определяется следующим образом: с =- тах хеи,

Д{«})>/(0)

Л {*»-/(0)-(/(*/)-Я*Л {*})) /({*})" /(0) и называется кривизной функции /. Нетрудно показать, что с = 0 тогда и только тогда, когда / модулярна.

Рассмотрим теперь минимизационные варианты задач (1) и (2), в которых В — семейство баз матроида М — (С/, В), С — семейство циклов коматроида К = (U,C), а / : 2и —» R+ — невозрастающая супермодулярная функция множеств.

Обе задачи являются обобщениями задачи о р-медиане на минимум с целевой функцией f{X) — ^ minQj, где (с^) — неотрицательная маjsJ ieX трица размера пхт с множеством индексов строк I = U и множеством индексов столбцов J. Задача о р-медиане называется метрической, если стоимости обслуживания удовлетворяют неравенству треугольника: C{j + Cjk ^ Cik для всех i,j, k Е I, и неметрической в противном случае.

Несложно показать, что после доопределения

0) = max {f(X) + f(Y) - f(X U У)}

А,Г С/, ХП F=0 невозрастающая целевая функция задачи о р-медиане на минимум становится супермодулярной.

Задача о р-медиане на минимум также NP-трудна [103]. Наиболее хорошо изучена метрическая задача о р-медиане на минимум, хотя вопрос о существовании для нее приближенных алгоритмов с константными оценками точности довольно долго оставался открытым. Первый алгоритм с константной оценкой точности для метрической задачи о р-медиане на минимум был-опубликован в 1999 г.: Чарикар, Гуа, Тардош и Шмойс [72], используя технику округления линейной релаксации, построили алгоритм с оценкой погрешности б|. В том же году Джейн и Вазирани [101] предложили прямо-двойственный 6-приближенный алгоритм, а Чарикар и Гуа [73], используя их результат, получили алгоритм с оценкой точности 4. В 2001 г. Арья, Гарг, Хандекар и др. [61] предложили (3 + е)-приближенный алгоритм локального поиска для метрической задачи о р-медиане на минимум.

В неметрическом случае ситуация принципиально иная. Известно (см. Немхаузер и Уолси [114]), что существование полиномиального алгоритма, который решал бы общую задачу о р-медиане на минимум с гарантированной оценкой погрешности, не превосходящей константы, означало бы, что Р = ЫР. Более того, как указано в обзоре Агеева [2], для задачи о р-медиане на минимум существование алгоритма даже с полиномиальной относительно размерности задачи оценкой точности повлекло бы Р = NP. Естественно, эти же отрицательные результаты справедливы и для более общих задач (1) и (2) минимизации супермодулярных функций на матроидах и коматроидах.

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

Если отбросить условие монотонности целевой функции, то частным случаем задач минимизации супермодулярных функций на матроидах и коматроидах является задача минимизации супермодулярной функции на булевой решетке всех подмножеств конечного множества. Впервые такая задача рассматривалась Черениным [57]. Задачи оптимизации супермодулярных функций на произвольных решетках были впервые сформулированы и исследованы Хачатуровым [56]. Обзор теоретических результатов и методов решения задач оптимизации супермодулярных функций на решетках содержится в [104].

В книге Схрейвера [119] рассмотрен ряд обобщений понятия субмодулярной функции, в частности, субмодулярные функции на решеточных семействах. В главе 3 введено обобщение понятия супермодулярной функции, определенной на семействе независимых множеств матроида. Частным случаем такой функции является целевая функция задачи аппроксимации графа, подробно рассмотренная в главе 4.

Задачи матроидной аппроксимации

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

Вновь рассмотрим задачу максимизации (1): таx{f(X) :Х еВ}, где / : 2и —» R+ — монотонная неотрицательная функция множеств, а В — семейство баз наследственной системы S = (U,A). Как следует из теоремы Радо-Эдмондса, задача (1) быстро разрешима жадным алгоритмом, если наследственная система S является матроидом. В связи с этим представляет интерес следующий вопрос: как сильно данная наследственная система отличается от матроида? Так мы приходим к задаче матроидной аппроксимации, самая общая постановка которой такова.

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

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

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

Фиксируем наследственную систему S= (U,A) = (U,B). Для матроида MG Л4(и) положим

М) - ЩЩ ' где OptS и OptM — оптимальные решения задачи (1) и аналогичной задачи с той же целевой функцией на матроиде М, соответственно.

Требуется для данной наследственной системы S найти такой матроид М0 £ M(U), что p(S, Mo) = min p(S, M) r(5).

MgM(U) 22

Если при этом ОрИИо Е В, то ОрЬМо может рассматриваться как приближенное решение задачи (1) на наследственной системе 5, имеющее относительную погрешность, равную т(5).

Другая постановка задачи матроидной аппроксимации, впервые сформулированная Р.И. Тышкевич, получается, если Бс = (V, Ас) — наследственная система графа = (V, Е), Л4(У) — класс всех матроидов разбиений на множестве У, а т(5с) равно минимуму (по всем М Е Л4(У)) мощности симметрической разности семейств циклов системы во и ма-троида М. Такая задача матроидной аппроксимации эквивалентна известной задаче аппроксимации графа.

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

Задача аппроксимации графа возникает при анализе систем взаимосвязанных объектов, в частности, в задачах классификации. При этом минимизируется число связей между классами и число недостающих связей внутри классов. Постановки и различные интерпретации этой задачи можно найти в работах Зана [130], Ляпунова [47], Миркина [48] и др.

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

Если = (у,Е\) и — (V, Е2) — графы на одном и том же множестве вершин У, то расстояние р(6?1,С?2) между ними определяется как р{ви ОД = \ЕгАЕ2\ = |Е! \ Е21 + \Е2 \ Ег\. т. е. р(Сп, 02) — число несовпадающих рёбер в графах и (?2

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

Задача А. Дан граф G = (V,E). Найти такой граф MoEM.(V), что Mo) = min p(G, M) dÜ T{G).

MeM(v)

Задача Ak. Дан граф G — (V, E) и целое число к, 2 ^ к ^ |У|. Найти такой граф М0 Е Mk(V), что p(G, М0) = min p(G, М) =7 rfc((?).

МбЛ^(У)

Задача А£. Дан граф G — (У, Е1) и целое число 2 ^ к ^ \V\. Найти такой граф M0EMlk{V), что p(G,M0) = min p(G, М) d= t£(G).

MeMl(V)

Очевидно, что для любого n-вершинного графа G и к ^ 2 имеют место неравенства т(О) < t*(G) < rt(G) <

Можно также сформулировать ориентированные и взвешенные варианты задач аппроксимации графов. В ориентированных задачах каждая бикомпонента аппроксимирующего орграфа является полным симметрическим графом и отсутствуют дуги, ведущие из одной бикомпоненты в другую. Во взвешенных вариантах задана весовая функция w : V х V —> N и p(Gi, G2) равно суммарному весу несовпадающих рёбер в графах Gi и 6?2

Первые теоретические результаты, относящиеся к задачам аппроксимации графов, были получены в 70-е годы XX в. В 1971 г. Фридманом [51] была решена задача А для графов без треугольников. Им было доказано следующее утверждение.

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

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

Фридман [52,54] показал также, что для любого п-вершинного графа имеет место оценка

Более сильный результат был установлен Томеску [120,121]: для любого к ^ 2 и любого п-вершинного графа (?

Ч < —1—

В 1982 г. Ильев и Фридман [21] показали, что для любого к ^ 2 и любого п-вершинного графа С? при п ^ 5(к — 1) справедлива оценка

Вычислительная сложность задач аппроксимации графов долгое время оставалась неизвестной. Известно было лишь [55], что ориентированная задача А с некоторыми дополнительными условиями КР-трудна. Только в 2004 г. Ильев и Талевнин (см. [49]) доказали, что взвешенная задача А^ является NP-тpyднoй при любом фиксированном к ^ 2. В 2006 г. Кононову удалось показать, что задача Аг на кубических графах ЫР-трудна. Используя этот результат, Агеев, Ильев, Кононов и Талевнин [3] установили, что все варианты задачи аппроксимации графа являются КР-трудными, откуда следует, что они ЫР-трудны и для ориентированных графов.

Практически отсутствовали также и алгоритмы решения задач аппроксимации графов. В 1971 г. Вейнер [10] предложил алгоритм решения задачи аппроксимации графов, не содержащих четырехвершинных подграфов ровно с пятью ребрами, однако не доказал, что результатом работы алгоритма действительно является М-граф, оптимально аппроксимирующий данный граф. Обоснование алгоритма Вейнера было дано Фридманом [53].

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

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

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

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

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

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

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

VIII - XIII Всероссийские конференции "Математическое программирование и приложения", Екатеринбург, 1993, 1995, 1997, 1999, 2003, 2007;

X - XIV Международные Байкальские школы-семинары "Методы оптимизации и их приложения", Иркутск, Северобайкальск, 1995, 1998, 2001, 2005, 2008;

II Сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-96), Новосибирск, 1996;

II школа по теории графов, Новосибирск, 1997;

I - IV Всероссийские конференции "Проблемы оптимизации и экономические приложения", Омск, 1997, 2003, 2006, 2009;

18th IFIP Conference "System Modelling and Optimization", Detroit, USA, 1997;

International Conference on Operations Research, Zurich, Switzerland, 1998;

Международная Сибирская конференция по исследованию операций (SCOR-98), Новосибирск, 1998;

Российские конференции "Дискретный анализ и исследование операций" (DAOR'2000, DAOR'02), Новосибирск, 2000, 2002;

II International Workshop "Discrete Optimization Methods in Production and Logistics" (DOM'2004), Omsk-Irkutsk, 2004;

IX Международный семинар "Дискретная математика и ее приложения", Москва, 2007;

Российская конференция "Дискретная оптимизация и исследование операций" (DOOR'07), Владивосток, 2007;

VIII Международная конференция "Дискретные модели в теории управляющих систем", Москва, 2009;

Международная научная конференция "Дискретная математика, алгебра и их приложения", Минск, Беларусь, 2009, а также на научных семинарах в Институте математики им. С.Л. Соболева СО РАН, в его Омском филиале и в Уральском государственном университете.

Автор выражает благодарность профессору Э.Х. Гимади, профессору В.А. Баранскому, всем своим соавторам, а также отдельно С.Д. Ильевой за внимание, поддержку и полезные замечания при выполнении данной работы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Ильев, Виктор Петрович

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

1. Исследована структура наследственных систем и их частных случаев — коматроидов. Предложены различные аксиоматизации коматро-идов. Получена характеризация графов циклов коматроидов и целочисленных полиматроидов.

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

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

4. Аналогичные оценки доказаны для задачи минимизации аддитивной функции на наследственной системе. Как следствие получены оценки погрешности обратного жадного алгоритма для задачи о минимальном двусвязном остовном подграфе и задачи о наименьшей раскраске графа. Установлена эквивалентность задачи минимизации аддитивной функции на наследственной системе и задачи о минимальном покрытии множества.

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

6. Предложена постановка задачи матроидной аппроксимации, частным случаем которой является задача аппроксимации графа. Получена оценка аппроксимационной сложности графа для одного варианта задачи аппроксимации графа. Доказано, что задача аппроксимации графами с заданным числом компонент связности АР-трудна.

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

Заключение

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

Список литературы диссертационного исследования доктор физико-математических наук Ильев, Виктор Петрович, 2010 год

1. Агеев АА. О сложности задач минимизации полиномов от булевых функций // Управляемые системы. Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1983. Вып. 23. С. 3-11.

2. Агеев A.A. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений / / Материалы между нар. конф. "Сибирская конф. по исследованию операций". Новосибирск. 1998. С. 4-10.

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

4. Айгнер М. Комбинаторная теория. М.: Мир. 1982.

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

6. Береснев B.JI., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука. 1978.

7. Биркгоф Г. Теория решеток. М.: Наука. 1984.

8. Боровков A.A. К вероятностной постановке двух экономических задач // Докл. АН СССР. 1962. Т. 1, N 5. С. 983-986.

9. Ван дер Варден Б. JI. Алгебра. М.: Наука. 1976.

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

11. Выплов М.Ю., Ильев В.П. О гиперграфах, соответствующих операторам слабого замыкания // Эл. сб. материалов VIII Междунар. конф. "Дискретные модели в теории управляющих систем". Москва. 2009. С. 30-34.

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

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

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

15. Глебов Н.И. О применимости метода покоординатного спуска к некоторым задачам выпуклого целочисленного программирования // Управляемые системы. Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1978. Вып. 17. С. 52-59.

16. Глебов Н.И. Базисные системы и задача минимизации на пересечении базисных систем // Управляемые системы. Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1984. Вып. 25. С. 58-67.

17. Глебов Н.И., Шенмайер В.В. О применимости алгоритма покоординатного подъема к задачам целочисленного программирования // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N 4. С. 38-47.

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

19. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука. 1981.

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

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

22. Ильев В.П., Фридман Г.Ш., Филичкина М.А. Об аппроксимации ориентированных графов графами с фиксированным числом бикомпо-нент // Моделирование и оптимизация структурных систем. Барнаул.1982. С. 54-61.

23. Ильев В.П., Фридман Г.Ш. К задаче аппроксимации трехкомпонент-ными графами // Численные методы и задачи оптимизации. Томск.1983. С. 80-95.

24. Ильев В.П. О базисных графах полиматроидов // Методы дискретного анализа в изучении реализаций логических функций. Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1984. Вып. 41. С. 35-48.

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

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

27. Ильев В.П. О задачах матроидной аппроксимации // Тез. докл. II школы по теории графов. Новосибирск. 1997. Дискрет, анализ и исслед. операций. Сер. 1. 1997. Т. 4, N 4. С. 104.

28. Ильев В.П., Молдованов И.А. О градиентном алгоритме построения надежных коммуникационных сетей // Труды ИВМиМГ. Сер. "Информатика". Новосибирск. 1998. С. 60-69.

29. Ильев В.П., Леванова Т.В. Анализ градиентного алгоритма минимизации супермодулярной функции на матроиде // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск. 1998. Т. 1. С. 143-146.

30. Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции // Дискрет, анализ и исслед. операций. Сер. 1. 1998. Т. 5, N 4. С. 45-60.

31. Ильев В.П., Линкер Н.В. О минимизации супермодулярных функций на коматроидах // Труды XII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск. 2001. Т. 1. С. 160-165.

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

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

34. Ильев В.П. Оценки погрешности приближенного алгоритма для задачи о раскраске графа // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск-Северобайкальск. 2005. Т. 1. С. 491-495.

35. Ильев В.П. Алгоритмы с оценками для задачи о р-медиане и ее обобщений // Материалы III Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск. 2006. С. 32-36.

36. Ильев В.П. Задачи комбинаторной оптимизации на наследственных системах // Материалы Российской конф. "Дискретная оптимизация и исследование операций". Владивосток. 2007. С. 41-45.

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

38. Ильев В.П. Оценки погрешности жадных алгоритмов для задач на наследственных системах // Дискрет, анализ и исслед. операций. 2008. Т. 15, N 1. С. 44-57.

39. Ильев В.П., Ильева С.Д. Оценка погрешности жадного алгоритма для задачи аппроксимации графа // Труды XIV Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск-Северобайкальск. 2008. Т. 1. С. 396-404.

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

41. Ильев В.П., Ильева С.Д. Задачи минимизации супермодулярных функций на матроидах и коматроидах // Материалы IV Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск. 2009. С. 51-55.

42. Ильев В.П., Ильева С.Д. 3-приближенный алгоритм для одного варианта задачи аппроксимации графа // Вестник Омского университета. 2009. N 4. С. 77-79.

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

44. Ковалев М. М. Матроиды в дискретной оптимизации. Минск: Университетское. 1987; 2-е изд. М.: УРСС. 2003.

45. Кукина О.Г., Ильев В.П. Коматроиды и решетки их открытых множеств // Труды 37-й Региональной молодежной конф. "Проблемы теоретической и прикладной математики". Екатеринбург. 2006. С. 53-57.

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

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

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

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

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

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

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

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

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

55. Хачатуров В.Р. Супермодулярные функции на решетках // Проблемы прикладной математики и информатики. М.: Наука. 1987. С. 251-262.

56. Черенин В.П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов // Научно-методические материалы экономико-математического семинара Лаборатории экономико-математических методов АН СССР. М. 1962. Вып. 2.

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

58. Arora S., Karger D., Karpinski М. Polynomial time approximation schemes for dense instances of NP-hard problems // J. Comput. System Sci. 1999. V. 58, N 1. P. 193-210.

59. Arora S., Safra S. Probabilistic checking of proofs // Proc. of the 33rd Ann. IEEE Symp. on Foundations of Comput. Sci. 1992. P. 2-13.

60. Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V. Local search heuristics for fc-median and facility location problems // Proc. of the 33rd Ann. ACM Symp. on Theory of Computing. 2001. P. 21-29.

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

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

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

64. Birkhoff G. Abstract linear dependence in lattices // Amer. J. Math. 1935. V. 57. P. 800-804.

65. Bixbi R.E., Cunningham W.H., Matroid optimization and algorithms. In: Handbook of Combinatorics. Graham R.O., Grotschel M., Lovasz L., eds. Amsterdam: Elsevier Science B.V. 1995. V. 1. P. 551-609.

66. Bollobas B. Extremal graph theory. London: Academic Press, 1978.

67. Bondy J.A., Ingleton A.W. Pancyclic graphs II // J. Combin. Theory. Ser. B. 1976. V. 20, N 1. P. 41-46.

68. Borovik A.V., Gelfand I.M., White N. Coxeter matroids. Boston: Birkhauser. 2003.

69. Boruvka O. O jistem problemu minimalnim, Prace Moravske Prirodove Spol. v Brne // Acta Societ. Scient. Natur. Moravicae. 1926. V. 3. P. 37-58.

70. Charikar M., Guha S., Tardos E., Shmoys D.B. A constant-factor approximation algorithm for the fc-median problem // Proc. 31st Ann. ACM Symp. on Theory of Comput. 1999. P. 1-10.

71. Charikar M., Guha S. Improved combinatorial algorithms for the facility location and ^-median problems // Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sci. 1999. P. 378-388.

72. Cheriyan J., Thurimella R., Approximating minimum-size ^-connected spanning subgraphs via matching // Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci. 1996. P. 292-301.

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

74. Conforti M., Cornuéjols G. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem // Discrete Appl. Math. 1984. V. 7, N 3. P. 251-274.

75. Cornuéjols G., Fisher M.L., Nemhauser G.L. Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms // Management Science. 1977. V. 23, N 8. P. 789-810.

76. Crapo H.H., Rota G.-C. On the foundations of combinatorial theory II: combinatorial geometries. Cambridge Mass.: MIT Press. 1970.

77. Dietrich B.L., Hoffman A.J. On greedy algorithms, partially ordered sets, and submodular functions // IBM J. Res. and Dev. 2003. V. 47, N 1. P. 25-30.

78. Dilworth R.P. The arithmetical theory of Birkhoff lattices // Duke Math. J. 1941. V. 8. P. 286-289.

79. Dilworth R.P. Dependence relations in a submodular lattice // Duke Math. J. 1944. V. 11. P. 575-587.

80. Dunstan F., Ingleton A., Welsh D. Supermatroids // Combinatorics, Southend-on Sea. 1972. P. 338-353.

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

82. Edmonds J. Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and their Applications. Proc. Calgary Int. Conf.

83. June 1969. Guy R.K., Hanani H., Sauer N., Schonheim J., eds. New York: Gordon and Breach. 1970. P. 69-82.

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

85. Goetchel R. Linear objective functions on certain classes of greedoids // Discrete Appl. Math. 1986. V. 14, N 1. P. 11-16.

86. Griggs J.R. Lower bounds on the independence number in terms of the degrees // J. Combin. Theory. Ser. B. 1983. V. 64. P. 22-39.

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

88. Hastad J. Some optimal inapproximability results // Proc. 29th Ann. ICM Symp. on Theory of Comput. 1997. P. 1-10.

89. Halldorsson M.M. A still better performance guarantee for approximate graph coloring // Inform. Process. Letters. 1993. V. 45. P. 16-23.

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

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

92. Helman P., Moret B.M.E., Shapiro H.D. An exact characterization of greedy structures // SIAM J. Discrete Math. 1993. V. 6, N 2. P. 274-283.

93. Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In: Approximation Algorithms for NP-hard Problems. Hochbaum D.S., ed. Boston: PWS Publ. Co. 1997. P. 94-143.

94. Holzmann C.A., Harary F. On the tree graphs of matroids // SIAM J. Appl. Math. 1972. V. 22. P. 187-193.

95. Il'ev V.P. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function // Discrete Appl. Math. 2001. V. 114, N 1-3. P. 131-146.

96. Il'ev V. Hereditary systems and greedy-type algorithms // Discrete Appl. Math. 2003. V. 132, N 1-3. P. 137-148.

97. Il'ev V., Linker N. Steepest descent algorithm for minimizing a supermodular set function on comatroid // Proc. 2nd Intern. Workshop "Discrete Optimization Methods in Production and Logistics". Omsk-Irkutsk. 2004. P. 166-168.

98. Il'ev V., Linker N. Performance guarantees of a greedy algorithm for minimizing a supermodular set function // European J. Oper. Res. 2006. V. 171, N 2. P. 648-660.

99. Jain K., Vazirani V.V. Primal-dual approximation algorithms for metric facility location and k-median problems // Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sci. 1999. P. 2-73.

100. Jenkyns Th.A. The efficacy of the "greedy" algorithm // Proc. 7th Southeastern Conf. on Combinatorics, Graph Theory and Computing. Hoffman F., Lesniak L., Mullin R., Reid K.B., Stanton R., eds. Winnipeg: Utilitas Math. 1976. P. 341-450.

101. Kariv O., Hakimi S.L. An algorithmic approach to network location problems. II. The p-medians // SIAM J. Appl. Math. 1979. V. 37, N 3. P. 539-560.

102. Khachaturov Vladimir R., Khachaturov Roman V., Khachaturov Ruben V. Supermodular programming on lattices // Computer Science J. of Moldova. 2003. V. 11, N 1 (31). R 43-66.

103. Khuller S., Raghavachari B. Improved approximation algorithms for uniform connectivity problems // J. of Algorithms. 1996. V. 21. P. 434450.

104. Korte B., Hausmann D. An analysis of the greedy heuristic for independence systems // Annals of Discrete Math. 1978. V. 5. P. 65-74.

105. Korte B., Lovasz L. Mathematical structures underlying greedy algorithm // Lecture Notes in Comput. Sci. Berlin: Springer-Verlag. 1981. V. 177. P. 205-209.

106. Korte B., Lovasz L. Greedoids and linear objective functirns // SIAM J. Alg. Discrete Meth. 1984. V. 5, N 2. P.229-238.

107. Kruskal J.B. On the shortest spanning subtree of a graph and the travelling salesman problem // Proc. Amer. Math. Soc. 1956. V. 7, N 1. P. 48-50.

108. Mac Lane S. Some interpretations of abstract linear dependence in terms of projective geometry // Amer. J. Math. 1936. V. 58. P. 236-240.

109. Maurer S.B. Matroid basis graphs I // J. Combin. Theory. Ser. B. 1973. V. 14, N 1. P. 216-240.

110. Mazurov Vl.D., Khachay M.Yu., Rybin A.I. Commitee constructions // Proc. of the Steklov Institute of Mathematics. Suppl. 1. 2002. P. 67-101.

111. Nemhauser G.L., Wolsey L.U., Fisher M.L. An analysis of approximations for maximizing submodular set functions I // Math. Programming. 1978. V. 14, N 13. P. 265-294.

112. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. New York: John Wiley & Sons, Inc. 1988.

113. Rado R. A theorem on independence relations // Quart J. Math. Oxford. 1942. V. 13. P. 83-89.

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

115. Ravi R., Williamson D. An approximation algorithms for minimum-cost vertex-connectivity problems // Algorithmica. 1997. V. 18. P. 21-43.

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

117. Schrijver A. Combinatorial optimization. Berlin: Springer-Verlag. 2003.

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

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

120. Turân P. On an extremal problem in graph theory (in Hungarian) // Mat. Fiz. Lapok. 1941. V. 48. P. 436-452.

121. Tutte W. T. A homotopy theorem for Matroids, I and II // TVans. Amer. Math. Soc. 1958. V. 88. P. 144-174.

122. Tutte W. T. Matroids and graphs // Trans. Amer. Math. Soc. 1559. V. 90. P. 527-553.

123. Tutte W. T. Lectures on matroids // J. Res. Nat. Bur. Stand. 1965. V. 69B. P. 1-44.

124. Wei V.K. A lower bound on the stability number of a simple graph // Technical Memorandum N 81-11217-9. Bell Laboratories. 1981.

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

126. White N., ed. Theory of matroids. Cambrige: Cambrige Univ. Press. 1986.

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

128. Zahn C. Approximating symmetric relations by equivalence relations // J. of the Society for Industrial and Applied Mathematics. 1964. V. 12, N 4. P. 840-847.