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

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

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

003494586

ИЛЬЕВ Виктор Петрович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени 2 5 .\]ДР 20^0 доктора физико-математических наук

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

003494586

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

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

профессор Э.Х. Гимади, доктор физико-математических наук, профессор В.А. Баранский, доктор физико-математических наук М.Ю. Хачай.

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

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

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

Автореферат разослан \9 ахгьрада 2010 г.

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

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

Актуальность темы. Наследственные системы - это универсальные комбинаторные объекты, сочетающие в себе черты систем независимости (систем подмножеств конечного множества, обладающих свойством наследственности) и систем множеств с аналогичным свойством наследственности "вверх". Задачи оптимизации и аппроксимации на наследственных системах являются математическими моделями множества сложных в вычислительном плане практически важных задач. Оптимизационные задачи на наследственных системах, как правило, являются УУР-трудными.

Следующие три подхода к исследованию и решению /УТ-трудных задач оптимизации являются общепринятыми [3]: 1) разработка точных методов неявного перебора; 2) выделение полиномиально разрешимых классов подзадач; 3) построение приближенных полиномиальных алгоритмов с оценками точности получаемых решений.

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

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

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

в классе полиномиальных алгоритмов [29], либо является асимптотически точным алгоритмом [б].

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

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

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

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

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

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

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

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

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

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

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

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

Теоретические результаты диссертации используются в учебном процессе в Омском государственном университете.

Апробация работы. Результаты диссертации прошли апробацию на VIII - XIII Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 1993, 1995, 1997, 1999, 2003, 2007); X - XIV Международных Байкальских школах-семинарах "Методы оптимизации и их приложения" (Иркутск, Северобайкальск, 1995,1998, 2001, 2005, 2008); II Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 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); Международной Сибирской конференции по исследованию операций (Новосибирск, 1998); Российских конференциях "Дискретный анализ и исследование операций" (Новосибирск, 2000, 2002); II International Workshop "Discrete Optimization Methods in Production and Logistics" (Omsk-Irkutsk, 2004); IX Международном семинаре "Дискретная математика и ее приложения" (Москва, 2007); Российской конференции "Дискретная оптимизация и исследование операций" (Владивосток, 2007), VIII Международной конференции "Дискретные модели в теории управляющих систем" (Москва, 2009), Международной научной конференции "Дискретная математика, алгебра и их приложения" (Минск, Беларусь, 2009), а также на научных семинарах в Институте математики им. C.JI. Соболева СО РАН, в его Омском филиале и в Уральском государственном университете.

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

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

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

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

В главе 1 изучается структура наследственных систем, их обобщений и частных случаев - наследственных систем графов и коматроидов.

В первых двух параграфах приводятся определения основных понятий и первоначальные сведения о наследственных системах.

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

А1 еЛ, А2 С Лх А2 € Л.

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

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

шах{/(Х) : X еВ}, (1)

где / : 2и —* И.+ - монотонная неотрицательная функция множеств.

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

1шп{/(Х) : X е С], (2)

где / : 2и —* - монотонная неотрицательная функция множеств, а С - семейство циклов (т. е. минимальных по включению множеств) непустого семейства V С 2и подмножеств и, обладающего свойством наследственности "вверх":

£>1 6 V, £>1 С £>2 =» Аг € Х>.

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

Итак, определим наследственную систему 5" на множестве II как разбиение семейства 2и всех подмножеств {/ на два непересекающихся семейства А и Т>, где А - система независимости, а V = 2и \ А. Семейства всех баз и всех циклов системы 5 будем обозначать через В и С, соответственно. Очевидно, что каждое из семейств А, В, С, V однозначно определяет наследственную систему Б, поэтому будем записывать

в = (и, Л), {и, В), 5 = (1/, С) или 5 = (17, Х>) в зависимости от того, какая сторона наследственной системы будет нас интересовать.

Важными частными случаями наследственных систем являются ма-троиды и коматроиды. Дадим определения этих объектов.

Пусть 5 = {и, Л) - наследственная система и IV С 17. Базой множества № называется любое максимальное по включению независимое множество, содержащееся в IV. Циклом множества \¥ называется любое минимальное по включению зависимое множество, содержащее IV.

Система 5 называется матроидом, если все базы любого множества IV С и имеют одинаковую мощность. В частности, все базы множества и равномощны; их общая мощность г называется рангом матроида.

Понятие матроида было введено Уитни [42]. Различные аксиоматизации матроидов можно найти в [41].

С каждой наследственной системой 5 = (17, Л) тесно связана дополнительная система или косистема 5' = (С/, V), семейство зависимых множеств которой определяется как V = {17 \ А : А € А}.

Наглядным примером наследственной системы является наследственная система графа 5с = (V, Аз), где V - множество вершин обыкновенного графа С = (V, Е), Ло ~ семейство всех независимых множеств вершин. Заметим, что семейство Сс циклов системы 5с взаимно однозначно соответствует множеству Е ребер графа С?. Поскольку дополнениями независимых множеств в графе являются вершинные покрытия, то в системе = (У,ТУС), дополнительной к наследственной системе семейство зависимых множеств Фс = {V \ А : А € Лв} совпадает с семейством всех вершинных покрытий в графе (7.

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

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

Предложение 1.1. Наследственная система 5 = (17, V) есть ко-матроид тогда и только тогда, когда для любого IV С 17 все циклы множества IV имеют одинаковую мощность.

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

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

Теорема 1.2. Наследственная система S является коматроидом, если и только если имеет место одно из следующих свойств: (Л') Ль Л2 £ А, Ах U Л2 <£ А, а $ Ах U Л2 (Лх П Л2) U а £ А; (В') Bi,B2€B,Bi^B2,b^BiUB2=^3B€B:BD(B1nB2)Llb; (С') СьС2еС, c2eC2\C1=>3c1GCl\C2:(Ci\c1)Uc2€C-t (£>') Di,D2 £ V, |£>i| = \D2\ + 1=>В d£D1\D2:D1\d£V.

Кроме того, в параграфе 1.1 введены понятия двойственных наследственных систем и исследованы связи между ними.

Естественным обобщением понятия наследственной системы является понятие наследственной системы целочисленных векторов.

Пусть U = {1,2,..., п} - непустое конечное множество, Z+ - множество всех векторов с целыми неотрицательными координатами, пронумерованными элементами множества U. Наследственной системой целочисленных векторов будем называть пару S = (U, А), где А Q -непустое конечное семейство векторов, обладающее свойством наследственности:

а £ А, а' ^ а => а' £ А. Легко видеть, что тогда семейство векторов Т> = Z+ \ А удовлетворяет условию наследственности вверх: deV, d^d' =» d' £ V.

Целочисленный полиматроид - это наследственная система целочисленных векторов Р = (U, Л) такая, что для любого z 6 Z+ все максимальные (относительно элементы семейства {а £ А : а < z} имеют одинаковую сумму компонент.

Пусть V С - семейство векторов, обладающее свойством наследственности вверх и удовлетворяющее следующему условию: для всякого z £ все минимальные элементы семейства {d £ "D : d ^ z} имеют одинаковую сумму компонент. Тогда наследственная система целочисленных векторов Q = (U, V) называется верхним целочисленным поли-матроидом.

Системы А, Т> С Я^ вещественнозначных неотрицательных векторов с аналогичными свойствами, определяющие многогранные множества в называются полгшатроидами и верхними полгшатроидами. Поли-матроиды были введены Эдмондсом [26], он же впервые исследовал целочисленные полиматроиды. Верхние полиматроиды под именем неограниченных полиматроидов рассматривались в [9].

Имеются различные подходы к изучению структуры матроидов, ко-матроидов и полиматроидов. Один из самых наглядных состоит в следующем. Матроиду М = (и, В) ставится в соответствие обыкновенный граф, вершины которого взаимно однозначно соответствуют базам матро-ида, а ребра - парам баз, различающихся ровно одним элементом. Такой граф называется графом баз или базисным графом матроида М. Графом циклов коматроида К = (II, С) называется граф, вершины которого взаимно однозначно соответствуют циклам коматроида, а ребра - парам циклов, различающихся ровно одним элементом. Аналогично определяются графы баз и графы циклов целочисленных полиматроидов.

Графы баз изучались на протяжении ряда лет различными авторами [22, 31, 36]. Маурер [36] предложил характеризацию графов баз матроидов в терминах их локальных подграфов. В разделе 1.3.1 результат Маурера обобщен на целочисленные полиматроиды, как следствие получена характеризация графов циклов коматроидов и верхних целочисленных полиматроидов.

Наиболее тесно с графами связаны наследственные системы графов. Возникают естественные вопросы: когда наследственная система графа является матроидом и когда - коматроидом? Ответы на эти вопросы содержатся в разделе 1.3.2.

Следуя Тышкевич [12], обыкновенный граф С? будем называть М-графом, если каждая его компонента связности есть полный граф. Ответ на первый вопрос содержится в работе Бензакена и Хаммера [21]:

Наследственная система обыкновенного графа (7 = (V, Е) является матроидом тогда и только тогда, когда С - М-граф.

Матроид, о котором идет речь в данном утверждении, называется матроидом разбиения. Имеется в виду разбиение множества вершин М-графа С? = (V, Е) на подмножества V],..., 14, где V* - множество попарно смежных вершин г-й компоненты связности, г = 1,..., к.

Ответ на второй вопрос дан в следующем утверждении.

Теорема 1.8. Наследственная система обыкновенного графа является коматроидом тогда и только тогда, когда любая пара его несмежных ребер принадлежит циклу длины 4-

Заметим, что семейства Л и V независимых и зависимых множеств наследственной системы Б = (и, Л) — {и, Т>) представляют собой порядковый идеал и фильтр булевой решетки всех подмножеств конечного множества {/. В параграфе 1.4 изучаются другие связи между наследственными системами и решетками. В нем дано эквивалентное определе-

ние наследственной системы в терминах замыкания и доказаны аналоги теоремы Биркгофа-Уитни о представлении геометрических решеток.

Хорошо известно определение матроида в терминах оператора замыкания (см. [1, 2]). Пусть и - непустое конечное множество. Отображение X Д X множества 2и в себя называется оператором замыкания, если

для всех X, У С [/ выполняются следующие условия:_

(£1 )ХСХ, (552) X СУ =>ХСУ, {Щ)Х_=Х. Множество X си называется замкнутым, если X = X.

Пара М = (1/, 1р) называется матроидом (или комбинаторной пред-геометрией) на и, если для всех и, V £ I/ и X С и выполняется аксиома

замены: _

(¡¡54) и $ X, и 6 X и {г»} и € X и {«}. Матроид называют простым (или комбинаторной геометрией), если (у5) 0 = .0 и {и} = {и} для всех и € О.

Между матроидами и комбинаторными геометриями существует взаимно однозначное соответствие, определяемое по правилам:

Х = ХЦ{и&Ц:ЗАСХ такое, что Л € Л, Аи{и}$.А), (3) А = {А С и : а £ А \ {а} для всех а € А}. (4)

В разделе 1.4.1 дано аналогичное определение наследственной системы в терминах замыкания. Каждой наследственной системе 5 = (С/, А) поставим в соответствие оператор Тр : 2и —* 2и по правилу (3). Он обладает свойствами (¡¡51), (¡¿52) и (^4), но может не удовлетворять аксиоме идемпотентности (^3). Отображение X Д X множества 2и в себя будем называть оператором слабого замыкания, если оно удовлетворяет условиям (<р1), (<р2)-

Правило (4) ставит в соответствие каждому оператору слабого замыкания, удовлетворяющему аксиоме (^4), наследственную систему. Однако, разным операторам слабого замыкания может соответствовать одна и та же наследственная система. Таким образом, чтобы получить определение наследственной системы в терминах замыкания, мы должны не просто отбросить аксиому идемпотентности (£>3), а заменить ее более слабым требованием. Рассмотрим следующее условие.

($539 УХ СИ Уи € У»б£и{«}\(Ли{и})Зго е X : V 6 Хи{и}\{и>}.

Заметим, что при этом г/ € X \ X. В следующей теореме установлено соответствие между операторами слабого замыкания и наследственными системами.

Теорема 1.10. Пусть S = (U,A) - наследственная система, где Л -семейство независимых множеств. Тогда отображение X X множества 2и в себя, определенное по правилу (3), обладает свойствами (<¿>1), (у>2), (у53') и (у54), причем имеет место равенство (4).

И наоборот, если Тр - оператор слабого замыкания, удовлетворяющий аксиомам (<^3') и (Jp4), то семейство Л С 2и, определенное по правилу (4), удовлетворяет аксиоме наследственности, причем имеет место (3).

Установленное в теореме 1.10 соответствие между операторами слабого замыкания, удовлетворяющими аксиомам (<¡53') и (<¿54), и наследственными системами является взаимно однозначным. Поэтому понятие оператора слабого замыкания, удовлетворяющего аксиомам (^3') и (¡¿54), можно рассматривать как эквивалентное определение наследственной системы. Если v? : 2и —* 2и - такой оператор, то пару S = (U,lp) будем называть наследственной системой.

В следующем разделе исследована решетка замкнутых множеств наследственной системы графа. Наследственной системе S = (U, 1р) сопоставим решетку L(U) замкнутых подмножеств U, упорядоченных по включению. Если X,Y € L(U), то положим XhY — XC\Y, a XvY -минимальное по включению замкнутое множество, содержащее XUY.

В случае, когда наследственная система является матроидом, имеет место следующее утверждение (теорема Биркгофа-Уитни, см. [1, 2]).

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

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

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

Заметим, что существуют наследственные системы, отличные от ма-троидов, решетки замкнутых множеств которых также являются геометрическими. В частности, решетки замкнутых множеств наследственных систем графов - геометрические. В разделе 1.4.2 для наследственных систем графов доказана теорема, аналогичная теореме Биркгофа-Уитни.

Теорема 1.13. Пусть Sg ~ наследственная система обыкновенного графа G. Тогда семейство всех ее замкнутых множеств образует дистрибутивную геометрическую решетку.

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

Продолжая топологическую аналогию, можно определить понятия открытых множеств наследственных систем, решеток открытых множеств и коматроидных решеток как решеток, двойственных матроидным (т. е. геометрическим). В разделе 1.4.3 доказана теорема, аналогичная теореме Биркгофа-Уитни, дающая интерпретацию решеток, двойственных геометрическим. Этот результат получен в соавторстве с О.Г. Кукиной.

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

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

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

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

Алгоритм (?+ (жадный алгоритм). Шаг 0. X *— 0. Перейти на шаг 1. Шаг к (к ^ 1). Выбрать такой элемент Хк $ X, что

/(X и хк) = тах /(X и х). „ „ х$х-.хихел

X <— X и Хк и перейти на шаг «4-1. Если такого элемента х* £ X нет, то 5(7+ +— X. Конец.

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

Алгоритм С?- (обратный жадный алгоритм). Шаг 0. X <— и. Перейти на шаг 1. Шаг к {к ^ 1). Выбрать такой элемент Хк € X, что

/(Х\хк)= тт НХ\х).

хеХ-.х\хеР

X «— X \ Хк и перейти на шаг к + 1. Если такого элемента Хк € X нет, то Бс *— X. Конец.

Заметим, что алгоритм С+ всегда находит базу, а алгоритм С?" - цикл наследственной системы, т. е. множество 5с+ является допустимым решением задачи (1), а £>с- - допустимым решением задачи (2).

В параграфах 2.2, 2.3 рассматриваются задачи (1) и (2) с аддитивными целевыми функциями. Следующая теорема, доказанная Радо [38] и Эдмондсом [26], - один из центральных результатов теории матроидов.

Пусть 5 = (¿7, Л) - наследственная система. Алгоритм гарантированно находит оптимальное решение задачи (1) для любой аддитивной целевой функции тогда к только тогда, когда 5 - матроид.

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

В работах Дженкинса [32], Корте и Хаусмана [33] получена оценка погрешности алгоритма С?+ для задачи (1) максимизации аддитивной функции на наследственной системе:

)(0 ! > пил -= с{Л), (5)

/(5о) И'СУ, гтах(И0

где Бо - оптимальное решение задачи (1), ^^(Ж) и гшах(1У) - минимальная и максимальная мощности баз множества IV, соответственно. Причем оценка (5) точна в следующем смысле: для любой наследственной системы Я = Щ,Л) существует такая аддитивная функция / : 2и -у В.+, что = с{Л).

Величина с(Л), называемая кривизной системы независимости, отражает близость наследственной системы к матроиду: с(Д) < 1 для любой наследственной системы, причем с{Л) = 1 тогда и только тогда, когда система 5 является матроидом.

Между оптимизационными задачами (1) и (2) и между жадными алгоритмами и существует тесная связь. Во многих случаях оптимальное решение 5о задачи (1) на наследственной системе 5 = (и, Л) и оптимальное решение 5 '0 задачи (2) на дополнительной системе 5' = (С, 2)') связаны соотношением = \7\So, т. е. алгоритм, точно решающий одну из этих задач, находит также и оптимальное решение другой задачи. Так, с помощью перехода к дополнительной наследственной системе как следствие теоремы Радо-Эдмондса несложно доказать следующий двойственный аналог этой теоремы для задачи (2).

Теорема 2.2. Пусть 5 = (и,Т>) - наследственная система. Алгоритм С~ находит оптимальное решение задачи (2) на системе 5 для любой аддитивной целевой функции тогда и только тогда, когда 5 -коматроид.

Учитывая равенство 5 'с- = С/\5с+, где 5с+ ~ допустимое решение задачи (1) на наследственной системе $ = (II, Л), полученное алгоритмом С", а 5- допустимое решение задачи (2) на дополнительной системе 5' = (и, ТУ), найденное алгоритмом можно утверждать, что любой из этих алгоритмов находит приближенное решение обеих оптимизационных задач. Однако, чаще всего гарантированные оценки погрешности алгоритма приближенного решения одной из задач (1), (2) не могут быть использованы для получения подобных оценок для другой задачи на дополнительной наследственной системе. Применяя оценку Дженкинса-Корте-Хаусмана (5), не удается получить априорную верхнюю оценку погрешности алгоритма 0~ для задачи минимизации (2). Для получения верхней оценки погрешности алгоритма для задачи (2) введем величину, характеризующую близость системы 5 к коматроиду.

Пусть 5 = (17, V) - произвольная наследственная система и W Q 17. Определим кривизну зависимости системы 5 как

с(V) = шах -—-———,

и'сс/, \Щ

где дт¡П(И0 и дтах(№) - минимальная и максимальная мощности циклов множества \У, соответственно. Очевидно, что с(р) ^ 1 для любой наследственной системы и с(Т)) = 1 тогда и только тогда, когда система является коматроидом.

Следующая теорема - основной результат параграфа 2.2.

Теорема 2.4. Пусть 5 = (17, V) - произвольная наследственная система. Тогда для любой аддитивной целевой функции задачи (2) имеет место оценка

Щ^сф), (6)

причем оценка (6) точна в следующем смысле: для всякой наследственной системы 5 = (£/, Т>) существует такая аддитивная целевая функция минимизационной задачи (2), что —

Как следствия теоремы 2.4 получены оценки погрешности обратного жадного алгоритма для задач о минимальном ¿-связном остовном подграфе, о наименьшей раскраске графа, о минимальном покрытии множества. Кроме того, показано, что задача (2) минимизации аддитивной функции на наследственной системе Б = (и, V) эквивалентна задаче о минимальном покрытии множества. Этот результат дает возможность применять для приближенного решения задачи (2) известный алгоритм Хватала [23]. Этот алгоритм имеет оценку погрешности, равную 1п Д +1, где Д - максимальная степень вершин вспомогательного гиперграфа Я = {и,С), ребра которого взаимно однозначно соответствуют циклам системы 5.

Центральным результатом параграфа 2.3 является усиление оценки Дженкинса-Корте-Хаусмана (5). Как следует из результата Дженкинса-Корте-Хаусмана, имея только информацию о множестве допустимых решений задачи (1), невозможно улучшить оценку (5) погрешности жадного алгоритма. Однако, используя дополнительную информацию об аддитивной целевой функции задачи (1), удается получить более точную оценку погрешности алгоритма С?+.

Теорема 2.12. Пусть 5 = (и, Л) - произвольная наследственная система, а > 0. Тогда для любой аддитивной целевой функции задачи (1) такой, что /(х) € [а, 6] для всех х 6 V, имеет место оценка

/(ад ъ „,,„ (Ь - аУпйп^) + аг^и) ы , . м

. ^ тш -т-г--г—г.-г—г = с(Л, а, о). (7)

/(•?£>) та (6 — а)гтдх(1У) + ОГтах(^) I

Для любой наследственной системы 5 = (II, Л) и любой неотрицательной аддитивной функции / справедливо неравенство с(Л,а,Ь) > с(Л). Более того, величина с(Л, а, Ь) может быть сколь угодно близка к 1, в то время как с(Л) близка к 0. Заметим также, что оценка (7) достижима, но в более слабом смысле, чем оценка (5).

Доказана также оценка погрешности алгоритма <3~ для задачи (2) минимизации аддитивной функции на наследственной системе, аналогичная оценке (7).

Теорема 2.13. Пусть 5 = (и, V) - произвольная наследственная система, а ^ 0. Тогда для любой аддитивной целевой функции задачи (2)

такой, что /(х) € [а, Ь] для всех х 6 II, имеет место достижимая оценка

ДА?-) . _ (г»-а)(^тпх(^)-|Ж|) + а^т(ис(0) А/

/(50) (Ь-а)(9^)-т) + а9тиЩ " ( ' ' '' ( ;

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

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

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

Многочисленные обобщения теоремы Радо-Эдмондса в основном были связаны с расширением допустимой области ([35, 27, 30, 19] и др.) Обобщения теоремы Радо-Эдмондса за счет расширения класса целевых функций также сопровождались расширением допустимой области (см., например, [7, 8, 30, 34]).

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

Пусть I/ - конечное множество, / : 2и —► Л+. Рассмотрим множество V С. и мощности ^ 3 и натуральное число к < |У| — 2. Множество X С V назовем градиентным подмножеством множества V, если существует такое упорядочение X — {хх,...., Хк} его элементов, что

Ж^}) > /({У» Для любого у € V,

Д{Я1,*2}) > /({Я1, У» для любого уеу\ {х1>,

/(X) ^ /({хи..., хк-и у}) для любого у € V \ {х1}..., хк-1}. Функция множеств / : 2и —* В.+ называется градиентно-согласованной, если для любых множеств Т С Т' С и и любых элементов х,у € и \ Т' таких, что множество Т и {х} = {хх, ... ,х^_х,х} является градиентным подмножеством множества Т" и {х, у}, имеет место неравенство

/(Г и х) ^ /(Г и у).

Заметим, что любая аддитивная функция градиентно-согласована.

Доказано следующее обобщение теоремы Радо-Эдмондса для задачи (1) на системе независимости.

Теорема 2.16. Пусть S={U,A) - наследственная система. Жадный алгоритм гарантированно находит оптимальное решение задачи (1) на системе S для любой градиентно-согласованной целевой (функции тогда и только тогда, когда S - матроид.

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

Теорема 2.17. Пусть f : 2V —> R+ - неотрицательная функция множеств. Жадный алгоритм гарантированно находит оптимальное решение задачи (1) с целевой функцией f на произвольном матроиде S — (U, А), если и только если f является градиентно-согласованной.

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

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

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

min {/(X) : X € В], (9)

min {f{X) :ХеС}, (10)

где В - семейство баз матроида М — (С/, Ai) ранга р, С - семейство циклов коматроида К = (U, V) обхвата р, р < п = \U\, f : 2U —> R+ - невозрас-тающая супермодулярная функция множеств такая, что f(U) = 0.

Обе задачи являются обобщениями задачи о р-медиане на минимум:

mm{f(X):XCI,\X\=p} (11)

с целевой функцией }{Х) = ]Г) mincy, где С = (су) - неотрицательная

j6J i€X

матрица размера n х ш с множеством индексов I — U строк и множеством индексов J столбцов. Как и задача о р-медиане, задачи (9) и (10) являются ЛГР-трудными.

Достаточно хорошо изучена в литературе аналогичная задача максимизации субмодулярной функции множеств:

max {f(X) : X € В}, (12)

в которой / : 2У —> Я+ - неубывающая субмодулярная функция множеств, /(0) = 0, а В - семейство баз матроида ранга р. Частным случаем этой задачи является задача о р-медиане на максимум с целевой функцией /(X) = тахс^. Как и задача о р-медиане на максимум, задача

(12) является Л^Р-трудной.

Корнуэджолсом, Фишером и Немхаузером [25] была получена оценка погрешности жадного алгоритма для задачи о р-медиане на максимум, не зависящая от размерности задачи:

ЛЗД ' V р ) е

где Б0 - оптимальное решение максимизационной задачи о р-медиане, а - решение, полученное жадным алгоритмом Позже Конфорти и Корнуэджолс [24] обобщили и уточнили эту оценку для задачи (12).

К сожалению, несмотря на внешнее сходство задач (9) и (10) с задачей максимизации (12), в случае минимизации супермодулярных функций ситуация принципиально иная. И жадный алгоритм £7+, и обратный жадный алгоритм С~ могут давать сколь угодно плохие решения задач (9) и (10). Более того, известно, что существование полиномиального алгоритма, который бы решал задачу о р-медиане на минимум с гарантированной оценкой погрешности, не превосходящей константы, означало бы, что Р = N Р [37]. Однако, привлечение дополнительной информации о целевой функции задачи (10) делает возможным получение гарантированных оценок погрешности алгоритма С?"".

Для любых X С и и х е X положим <1х(Х) = /(X \ {аг}) — /(X) и

пусть <Щ*}) -йх{Ц)

с = шах -11 -.

хеи, а*(М) <ММ)>о

Для с < 1 определим крутизну 5 = с/( 1 — с) функции /.

Параметры с € [0,1] и 5 6 [0, оо) характеризуют замедление убывания невозрастающей супермодулярной функции /. Нетрудно показать, что с = я = 0 тогда и только тогда, когда / - модулярная функция.

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

Теорема 3.2. Для любого коматроида К = (I/, Т>) обхвата р и любой невозрастающей супермодулярной целевой функции задачи (10) крутизны 5^0 имеет место оценка

где во - оптимальное решение задачи (10), а 5с- - решение, полученное алгоритмом д — п — р, тг — |£/|.

Теорема 3.4. Для любого коматроида К = (II,V) и любой невоз-растающей суперомодулярной целевой функции задачи (10) крутизны й ^ 0 имеет место оценка

/(5с-)

< 1 + А (14)

Следует отметить, что оценка (13) представляет собой полином от в степени д — 1. Обе оценки обращаются в равенства при в = 0 и взаимно дополняют друг друга.

В параграфе 3.2 доказана также достижимая апостериорная оценка погрешности алгоритма которая в ряде случаев значительно лучше оценок (13) и (14). Введем величину

с' = тах

йЛва- и {х})

Очевидно, с* 6 [0,1] и с* < с. Положим з' = с'/( 1 — с7).

Теорема 3.5. Для любого коматроида К = (и, Т>) и любой невозрас-тающей суперомодулярной целевой функции задачи (10) имеет место апостериорная оценка /(5с-)

+ (15)

где Бо - оптимальное решение задачи (10), Бо- - решение, найденное алгоритмом С~.

Оценка (13) вначале была доказана автором для задачи о р-медиане на минимум. Позже совместно с Н.В. Линкером этот результат был обобщен для задачи (10). Оценки (14), (15) получены в соавторстве с С.Д. Ильевой.

В параграфе 3.3 как следствия теорем 3.2 и 3.4 получены гарантированные оценки погрешности алгоритма для общей задачи о р-медиане на минимум в терминах матрицы стоимостей обслуживания С.

Следствие 3.4. Алгоритм 0~ находит решение общей задачи о р-медиане на минимум, удовлетворяющее оценкам (13) и (14), где крутизна в определяется формулами

а = шах ^ _ 1 /(0) = шахУ^тах (си,сь<). (16)

Формулы (16) дают эффективный способ вычисления крутизны целевой функции задачи о р-медиане на минимум.

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

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

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

Вновь рассмотрим задачу максимизации:

max{/(X) : X G В}, (17)

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

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

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

В параграфе 4.1 рассматривается следующий вариант задачи матроидной аппроксимации. Рассмотрим произвольную наследственную систему 5 = (t/,Л) и в качестве M(U) рассмотрим класс всех матроидов разбиений на множестве U. Для М G M{U) положим

n(qm JHOptS)-noptM)\

где OptS - оптимальное решение задачи (17), a OptM - оптимальное решение аналогичной задачи на матроиде М с той же целевой функцией. Требуется для данной наследственной системы S найти такой матроид Mo€M(U), что

p(S, Mo) = min p(S, M) *Ü r(5).

M€M(U)

Если при этом Opt Mo € В, то Opt Mo может рассматриваться как приближенное решение задачи (17) на наследственной системе S, имеющее относительную погрешность, равную r(S).

В связи с этим представляют интерес верхние оценки аппроксимаци-онной сложности т (S). Такие оценки можно получить, воспользовавшись оценками погрешности жадного алгоритма, в частности, оценкой (7) (см. теорему 2.12).

Теорема 4.1. Для любой наследственной системы S = (U,A) и любой аддитивной целевой функции задачи (17) такой, что f{x) € [а, Ь] для всех х £ U, где а ^ 0, имеет место оценка

t(S) ^ 1 -с(А,а,Ь).

Другая постановка задачи матроидной аппроксимации, впервые сформулированная Р.И. Тышкевич, получается, если Sq = (V, Ag) - наследственная система графа G — (V, Е), M(V) - класс всех матроидов разбиений на множестве V (им взаимно однозначно соответствуют А/-графы на множестве V) и t(Sg) равно минимуму (по всем Мб A^(V)) мощности симметрической разности семейств циклов системы Sg и матроида М. Тогда задача матроидной аппроксимации эквивалентна известной задаче аппроксимации графа.

Обозначим через M{V) класс всех М-графов на множестве вершин V, ■Mkty) ~ класс всех М-графов на множестве вершин V, имеющих ровно к непустых компонент связности, Ml(V) - класс всех М-графов на множестве V, имеющих не более к компонент связности, 2 ^ к ^ \V\. Если Gi = (V, Ei) и С?2 = (V, Е2) - графы на одном и том же множестве вершин V, то расстояние p(Gi, G2) между ними определяется как p(Gu G2) = \ЕуЬЕг\ = |£?! \ Е2\ + \Е2 \ Ех\.

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

Задача А. Дан граф G={V, Е). Найти такой граф Mo€M(V), что p(G, Mo) = min p(G, M) r{G).

М£М\У)

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

def

такой граф MoeAlfc(V'), что р(С, Mo) = min p(G, М) = rk(G).

M€Mic(V)

Задача A£. Дан граф G=(V, E) и целое число к, 2 < к < |V|. Найти

такой граф Mo€M\{V), что p(G,М0) = min p(G,М) r^G).

M€M\(V)

Известны также взвешенные и ориентированные аналоги этих задач.

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

I

(п - I)2

4

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

(п-1)2

г1к(С) ^

4

Основным результатом параграфа 4.2 является следующая теорема, доказанная в соавторстве с Г.Ш. Фридманом.

Теорема 4.2. Для любого к ^ 2 и любого п-вершинного графа С? при

п^Цк- 1)

(п-1)

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

Вычислительная сложность задач аппроксимации графов долгое время оставалась неизвестной. Известно было лишь, что ориентированная задача А с некоторыми дополнительными условиями Л^Р-трудна [16]. В 2004 г. Ильев и Талевнин (см. [11]) показали, что взвешенная задача А^ является АГР-трудной при любом фиксированном к > 2. В 2006 г. Кононов доказал, что задача А2 на кубических графах ЛТ'-трудна. Используя этот результат, Агеев, Ильев, Кононов и Талевнин [43] установили, что все варианты задач аппроксимации графов являются МР-трудными.

Следующие две теоремы - основные результаты параграфа 4.4.

Теорема 4.7. Задача Аь является ЫР-трудной при любом фиксированном к ^ 2.

Теорема 4.8. Задача А£ является ЫР-трудной при любом фиксированном к > 2, причем при к = 2 она ЫР-трудна на кубических графах.

В параграфе 4.5 показано, как задача А£ аппроксимации произвольного графа С = (V, Е) может быть сведена к задаче минимизации супермодулярной функции на некотором матроиде разбиения и доказана следующая оценка погрешности жадного алгоритма для задачи А^.

Теорема 4.10. Пусть та ^ 3. Для любого п-вершинного графа

лад4 •

где /(50) = р{й,Мо) - расстояние от графа (У <?о оптимально аппроксимирующего графа, а /(5с+) - расстояние до М-графа, построенного жадным алгоритмом.

В разделе 4.5.2 для исследования качества жадного алгоритма на семействе неплотных графов применена идея алгоритмов с оценками, предложенная Гимади, Глебовым и Перепелицей [5].

Рассмотрим семейство Яп п-вершинных графов, удовлетворяющих следующему условию: для любого С? = (V, Е) € Яп ^ отР, где а и /3 - некоторые константы, а > 0, 0</?<2. Графы семейства £7„ будем называть неплотными.

Теорема 4.11. Пусть Мо 6 -М\{У) - оптимальное решение задачи Аз на произвольном неплотном графе С = (V, Е) € Я„, а М € ЛЛЦУ) -М-граф, полученный с помощью жадного алгоритма С+. Тогда

/?(С,М) Аап0 +1

^ 1 +

р(<?, М0) ^ п2 - 4ст<3 - 2п'

Следствие 4.1. Жадный алгоритм является гарантированно асимптотически точным алгоритмом аппроксимации неплотных графов.

Графы семейства Яп называются всюду плотными, если для любого О € Яп минимальная степень вершин в графе б не меньше 7п для некоторой константы 7 > 0. В разделе 4.5.2 доказано также существование полиномиальной приближенной схемы для задачи А£ путем ее сведения к задаче о бисекции на всюду плотных графах.

В разделе 4.5.3 для задач А£ и А2 предложены простые приближенные алгоритмы с константными оценками точности. Алгоритм приближенного решения задачи А^ имеет следующий вид.

Алгоритм

Шаг 1. Для каждой вершины и 6 V определим М-граф Му б МЦУ) следующим образом: вершина V и все смежные с ней вершины графа (7 принадлежат одной компоненте связности графа А/„, а все несмежные с V вершины графа (7 - другой компоненте.

Шаг 2. Среди всех графов М„ выберем такой граф М\, что

р{в, М0 = ттр(С,М„).

Конец. "

Справедлива следующая оценка погрешности алгоритма

Теорема 4.13. Для любого п-вершинного графа G M\{V)

p(G,M1) 2 р(С,М0р п' где Mo € Ml(V) - оптимальное решение задачи А\ на графе G.

Алгоритм N2 приближенного решения задачи А2 представляет собой модификацию алгоритма Показано, что гарантированная оценка погрешности алгоритма N2 меньше 5 —

Все результаты параграфа 4.5, за исключением теоремы 4.11 и следствия 4.1, получены в соавторстве с С.Д. Ильевой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[21] 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.

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

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

[24] Conforti M., Cornu6jols 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.

[25] 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.

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

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

[28] Grôtschel M., Lovâsz L. Combinatorial optimization. In: Handbook of Combinatorics. Graham R.O., Grôtschel M., Lovâsz L., eds. Amsterdam: Elsevier Science B.V. 1995. V. 2. P. 1341-1598.

[29] 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.

[30] 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.

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

[32] 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.

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

[34] Korte B., Lovâsz L. Mathematical structures underlying greedy algorithm // Lecture Notes in Comput. Sci. Berlin: Springer-Verlag. 1981. V. 177. P. 205-209.

[35] Korte B., Lovâsz L. Greedoids and linear objective functions // SIAM J. Alg. Discrete Meth. 1984. V. 5, N 2. P. 229-238.

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

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

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

[39] 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.

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

[41] Welsh D. J. A. Matroid theory. London: Academic Press. 1976.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[66] Il'ev V.P., Ofenbakh I.V. Optimization models and algorithms of constructing reliable networks // Proc. 18th IFIP TC7 Conf. "System Modelling and Optimization". Detroit. 1997. Research Notes in Mathematics. Chapman & Hall/CRC. 1999. V. 396. P. 237-244.

[67] 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.

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

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

[70] 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.

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

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

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

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

Подписано в печать 10.02.2010. Формат 60 x 84 1/16. Печ. л. 2,0. Уч.-изд. л. 2,0. Тираж 100 экз. Заказ № 39.

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

Введение

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

Заключение

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

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.