Наследственные структуры и оптимизационные задачи в булевых и геометрических решётках тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Выплов, Михаил Юрьевич

• Выплов, Михаил Юрьевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Выплов, Михаил Юрьевич

Оглавление

Введение

1. Аналог теоремы Биркгофа-Уитни для наследственных

систем

1.1. Теорема Биркгофа-Уитни

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

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

2. Представление наследственных систем в терминах замыкания и в терминах циклов

2.1. Эквивалентные определения матроида

2.2. Обобщение соответствия между матроидами и операторами замыкания

2.3. Эквивалентные определения наследственной системы

3. Задачи оптимизации модулярных и супермодулярных

функций на порядковых идеалах

3.1. Задача максимизации модулярной функции на Ь-матроиде

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

3.3. Задача минимизации супермодулярной функции на 1/-матроиде

Заключение

Литература

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

Введение

Наследственные структуры — объекты, наделённые свойствами наследственности — чрезвычайно широко распространены в дискретной математике. К ним относятся, в первую очередь, наследственные системы — универсальные комбинаторные объекты, сочетающие черты систем независимости (систем подмножеств некоторого, как правило, конечного множества V, обладающих свойством наследственности) и систем множеств с аналогичным свойством наследственности "вверх". Подмножества множества V, входящие в его систему независимости, называют независимыми, а все остальные множества — зависимыми. Свойство наследственности для независимых множеств формулируется так: любое подмножество независимого множества само независимо. Очевидно, что семейство всех зависимых множеств обладает свойством наследственности "вверх": любое надмножество зависимого множества является зависимым.

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

Семейство независимых множеств любой наследственной системы или матроида можно рассматривать как порядковый идеал булевой решётки всех подмножеств конечного множества V. Тогда семейство всех за-

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

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

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

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

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

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

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

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

(А еА,А'сА)^А'е А.

Множества семейства А называются независимыми, а само семейство А в литературе обычно называют системой независимости или наследственным семейством [51].

Наследственная система Н на множестве У определяется как разбиение семейства 2У всех подмножеств У на два непересекающихся семейства А и V. где А — система независимости, а V = 2У \ А [29,54]. Множества семейства V называются зависимыми . Очевидно, что V обладает свойством наследственности "вверх"-.

(£> е V, И' Э £>) V (Е V.

Через В обозначается семейство всех баз, т. е. максимальных по включению независимых множеств, через С — семейство циклов, т. е. минимальных по включению зависимых множеств.

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

Примером наследственной системы является наследственная система графа Не = (У, Ас)-, где Ав — семейство всех независимых множеств вершин произвольного графа С = (V, £). Циклы этой системы взаимно однозначно соответствуют рёбрам графа С.

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

тахЦ(Х) : X е В} или тт{/(1) : X е В}, (1)

где / : 2У —>■ Я+ — монотонная неотрицательная функция множеств, а В — семейство всех баз наследственной системы.

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

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

тах{/(Х) :ХеС} или тт{/(Х) : X е С}, (2)

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

Наследственные системы и их частные случаи — матроиды и кома-троиды — естественным образом возникают в различных областях математики, таких как линейная алгебра, теория графов, теория трансвер-салей (см. [3,21,70]) и других разделах комбинаторного анализа, например, при изучении свойств комбинаторных геометрий [45] или комитет-ной разрешимости систем ограничений [61].

Матроиды

Понятие матроида было введено в 1935 г. Уитни [73]. При исследовании комбинаторных характеристик графов Уитни заметил, что некоторые алгебраические свойства графов имеют аналоги в линейных пространствах. Результатом обобщения этих свойств стали аксиоматические определения матроида в терминах баз, циклов, независимых множеств, ранга и др. Практически одновременно Биркгоф выявил подобные свойства в решётках [43]. Годом позже Маклейн обнаружил связь матрои-

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

Матроид на множестве V может быть определён как наследственная система М = {V, Л), в которой все базы любого множества X С V имеют одинаковую мощность (базой множества X называется любое его максимальное по включению независимое подмножество). Рангом матроида называется мощность любой базы множества V.

Примером матроида является р-однородный матроид Мр = (У,ЛР), где Лр = {А С У : |А| ^ р}, р € М, р <: |У|.

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

Работы Дилуорса [47,48], Радо [63,64] и Татта [67-69] вызвали увеличение интереса к матроидам, исследование которых наиболее активно велось в 70-80-х гг. XX в. и продолжается в наше время. Как постепенно выяснилось, матроиды сочетают в себе черты многих объектов из различных областей математики (линейная алгебра, геометрия, теория графов, теория трансверсалей и т. д.). В процессе развития теории матроидов было предложено значительное количество их обобщений, таких как полиматроиды [50], целочисленные полиматроиды [17], суперматро-иды [49] (см. также [30]), базисные системы [19], матроиды Кокстера [44].

Наиболее полно теория матроидов изложена в книгах [70. 71]. Теоретико-множественный подход, базирующийся на определении матроида в терминах замыкания, достаточно подробно представлен в монографии Айгнера [2], где также приводятся некоторые геометрические аспекты теории матроидов. В книге Асанова, Баранского и Расина [3] содержится введение в теорию матроидов, основанное на этом же подходе. Изложение элементарных основ теории матроидов можно найти в

учебнике Емеличева, Мельникова, Сарванова и Тышкевич [21].

Приведём определение матроида в терминах замыкания. Отображение (/9 : 2У —» 2У называется оператором замыкания, если для всех X. У С V выполняются условия: (</?1) X С X (направленность), (</?2) X С У => X С У (монотонность), (</?3) X = X (идемпотентность), где X = ч>(Х). Множество 1 С 1/ называется замкнутым, если X = X. Пара (У, </?) называется пространством замыкания.

Пусть V — непустое конечное множество, а (р — оператор замыкания. Пара М = (У,ф) называется матроидом (или комбинаторной предгео-метрией) на V, если для всех X С V и для любых и,у Е.У выполняется аксиома замены:

((£>4) (и £ X, и € хиН) =Ф- V е X и {и}.

Можно дать определение и для случая бесконечного V, при этом требуется также выполнение аксиомы конечного базиса: (ср5) VI С У 35 С I (\В\ <оои В = Х).

Матроид называется обыкновенным (или комбинаторной геометрией), если 0 = 0 и {г>} = {и} для любого элемента V € V.

С каждой наследственной системой Н = (V, А) тесно связана дополнительная система или косистема Н') семейство зависимых множеств которой определяется как V = {V \ А : А € А}. Нетрудно проверить, что семейства независимых множеств, баз и циклов системы Н' могут быть заданы как А! = {V \ В : В е V), В' = {V \ С : Се С}, С — {V \ В : В е В). Ясно, что (Н')' = Н. так что наследственные системы Н и Н' взаимно дополнительны.

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

Решётки

Тонной верхней гранью УХ подмножества X частично упорядоченного множества Ь называется наименьший из элементов множества {а Е Ь \ х < а Ух Е X}, а точной нижней гранью /\Х — наибольший из элементов множества {а Е Ь : х > а Ух Е X}. Решёткой называется частично упорядоченное множество Ь, в котором любое двухэлементное подмножество {х, у} имеет точную нижнюю грань х Л у и точную верхнюю грань х V у.

Наименьший элемент решётки, если он существует, называется нулём решётки и обозначается 0; аналогично, наибольший элемент, если он существует, называется единицей решётки и обозначается 1. В частности, любая конечная решётка содержит нуль и единицу.

Говорят, что элемент решётки у покрывает элемент х (обозначается х < ■у), если х < у и из соотношения х < г < у следует у = г. Атомами (или точками) решётки называются элементы, покрывающие 0. Решётка называется атомарной (точечной), если каждый её элемент является точной верхней гранью атомов. Решётка называется полу модулярной, если для любых её элементов х,у выполняется соотношение х А у < -х у < -х V у. Решётка называется геометрической. если она является атомарной, полу модулярной и не содержит бесконечных цепей. Решётка называется дистрибутивной, если для любых её элементов ж, у, г выполняется соотношение х Л (у V г) = (х Л у) V (х Л г). Известно, что класс конечных булевых алгебр совпадает с классом дистрибутивных геометрических решёток [2].

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

Матроиду М = (V, <р) сопоставим решётку Ь(У) замкнутых подмножеств V, упорядоченных по включению. Операции определяются следующим образом: ХЛУ = ХГ)У, ХУУ = X и У для любых Х.УеЬ(У). Имеет место следующее утверждение (теорема Биркгофа-Уитни, [2]).

Решётка Ь(У) замкнутых множеств матроида — геометрическая. Обратно, если Ь — геометрическая решётка с непустым множеством атомов V, то пара М = (V, (р), где (р(X) = {у € V : V < УХ}, является обыкновенным матроидом, а / : Ь Ь(У),/(х) = {и 6 У : V < х} — изоморфизм решёток.

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

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

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

Проблема вложения алгебраических систем в другие алгебраические системы, обладающие теми или иными свойствами, является классической в алгебре и теории моделей и имеет долгую историю. Одним из первых значительных результатов является теорема Уитмена 1946 г. [72] о представлении решёток решётками полугрупп, утверждающая (в эквивалентной формулировке), что класс всех групп является решёточно универсальным. Тума уточнил [66] результат Уитмена, показав, что интервалы в решётках подгрупп исчерпывают все алгебраические решётки. Другое доказательство этого результата Ту мы содержится в работе Репницкого [65]. Исследования строения решёток, вложимых в решёт-

ки подалгебр различных конкретных классов алгебр ведутся в работах Репницкого [31-33], Семёновой [34-36].

Множество I С Ь называется порядковым идеалом решётки Ь, если оно обладает следующим свойством: (х Е /, у < х) => у £ /.

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

Дунстан, Инглтон и Уэлш [49] ввели понятие суперматроида как обобщение понятия матроида в частично упорядоченном множестве с нулём. Для конечной решётки Ь это определение приобретает следующий вид. Пусть 7— порядковый идеал в Ь. Он называется суперматроидом или Ь-матроидом. если для любого х € Ь все максимальные элементы из / П [0, х] имеют одинаковую высоту /¿.

В [49] доказано, что идеал I в конечной модулярной решётке Ь является Ь-матроидом, если и только если выполнена одна из следующих эквивалентных аксиом, в некотором смысле обобщающих аксиому пополнения для независимых множеств матроида: 1° (я, у е /, к(х) > Н(у)) Зг е I (у < г < х V у. К(г) = Н{х))\ 2° (я, у ¡Е I, Н(х) > 1г(у)) =>• Зги £ I (ъи < х, ад V у Е I. V у) = к(х)).

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

Функция / : Ь —» М+ называется супермодулярной на решётке Ь, если для любых х,у Е Ь выполняется неравенство

/(х V у) + /(х А у) ^ /(ж) + /(у).

В случае равенства функция / называется модулярной на решетке.

В последние десятилетия наблюдается устойчивый рост интереса к жадному алгоритму (см., например, [25-27,40,41,46,52]). Этот метод традиционно используется, в частности, для приближённого решения задач типа (1) с модулярными и супермодулярными целевыми функциями.

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

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

Шаг i (i ^ 1). Выбрать такой хг ф Хг_1, что для задачи (1) максимизации /(X,_i U {хг}) = тах /(Хг_1 U {ж}),

Xt-iU{x}eA

а для задачи (1) минимизации

/(Хг_1 U {жг}) = min /(Xt_! U {ж}).

xgX^u Xt-xU^eA

Хг <— Хг_1 U {жг}, перейти на шаг г + 1. Если такого хг ^ нет, то Scr Хг-\. Конец.

Жадный алгоритм Gr представляет собой эффективный метод решения целого ряда дискретных оптимизационных задач, а в ряде случаев является асимптотически точным [16].

Следующая теорема является одной из центральных в теории ма-троидов (теорема Радо-Эдмондса [50,64]):

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

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

Известны обобщения теоремы Радо-Эдмондса, как правило сопровождающиеся расширением допустимой области. В 1973 г. Глебов [17] независимо, не используя аппарат теории матроидов, доказал более общий, чем теорема Радо-Эдмондса, результат для задачи максимизации вогнутой сепарабельной функции на системе целочисленных векторов, обладающей свойством наследственности. Этот результат получил дальнейшее развитие в работах Глебова и Шенмайера [18,20].

Как следует из теоремы Радо-Эдмондса, алгоритм Gr является точным алгоритмом решения задачи (1) с аддитивной целевой функцией на

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

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

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

f(SGr) > c(A)f(S0), (3)

где So — оптимальное решение задачи (1), Scr — решение, полученное алгоритмом Gr, а с(А) — кривизна наследственной системы. Она определяется как

• 1г(Х)

с{А) = min

xcv, иг(Х)

Хф%

где 1г(Х) и иг(Х) — минимальная и максимальная мощности баз множества X, соответственно, и характеризует близость наследственной системы Н = (V,A) к матроиду. Очевидно, что с(А) ^ 1 для любой наследственной системы, причем с(А) = 1 тогда и только тогда, когда система Н является матроидом.

Рассмотрим теперь минимизационный вариант задачи (1), в которой В — семейство баз матроида М = (V}B). f : 2V —>■ R+ — неубывающая супермодулярная функция множеств, /(0) = 0. К этой постановке сводится известная задача о р-медиане на минимум.

Задача о р-медиа.не на минимум NP-трудна [57]. Известно, что существование для неё полиномиального алгоритма с константной оценкой точности (см. Немхаузер и Уолси [62]) и, более того, даже с полиномиальной относительно размерности задачи оценкой точности (см. обзор Агеева [1]) означало бы, что Р = NP. Как следствие, подобные отри-

цательные результаты имеют место и для более общих задач (1) и (2) минимизации супермодулярных функций на матроидах и коматроидах.

В работах Ильева и Линкера [22-24,29] рассматривается подход, основанный на привлечении информации о свойствах целевой функции что даёт возможность получения оценок точности приближённых алгоритмов в терминах параметров допустимой области и кривизны функции.

Кривизна неубывающей супермодулярной функции / характеризует ускорение возрастания функции и определяется следующим образом:

Справедлива следующая гарантированная оценка точности алгоритма вг (см. [28,29]).

Для любого матроида М = (V, Л) и любой неубывающей супермодулярной целевой функции задачи минимизации (1) имеет место оценка

где So — оптимальное рет,ение задачи (1), a Sqt — решение, найденное алгоритмом Gr.

Оценки в терминах кривизны целевой функции были получены и для невозрастающей супермодулярной функции задачи (2) [55].

К задаче (1) минимизации супермодулярной функции на матроиде сводится также известная NP-трудная задача аппроксимации графа [27,

Задачи оптимизации супермодулярных функций возникают в различных областях дискретной математики и изучались в течение ряда лет многими авторами. Так, задача минимизации супермодулярной функции на булевой решётке рассматривалась Черениным [39]. Хачатуров впервые сформулировал и исследовал задачи оптимизации супермодулярных функций на произвольных решётках [37]. Хачатуровым вместе с соавторами предложено большое количество теоретических результатов

Cf = max xev, f(V)>f(V\{x})

(ЯП-ЯП{*}))-(/({*})-/№)

f(V)-f(V\{x})

^-cf)f(SGr)<f(S0)

29].

и методов решения задач оптимизации супермодулярных функций на решётках различных типов, что позволяет говорить об открытии нового направления в математическом программировании — супермодулярного программирования (см. [38,58]).

Исследование жадного алгоритма на наследственных структурах в решётках преследует несколько целей. Помимо непосредственного обобщения известных результатов путём расширения допустимой области (аналогичное направление имеет место в работах Глебова, Шенмайера, Илье-ва и других), интерес представляет вопрос связи точности алгоритма с комбинаторными свойствами порядковых идеалов и решёток. В диссертации рассматриваются границы применимости жадного алгоритма как инструмента точного или приближённого решения оптимизационных задач. Кроме того, исследуется чувствительность алгоритма к характеристикам допустимой области, в частности, к отсутствию свойства дистрибутивности при переходе от булевых к геометрическим решёткам, а также к наличию свойств, определяющих в них матроидную структуру. Оказывается, что не во всех случаях утверждения о разрешимости задач жадным алгоритмом имеют обобщения. Например, в геометрической решётке становится неверной теорема Радо-Эдмондса в части, доказанной Эдмондсом. В то же время, некоторые оценки точности (например, оценка Дженкинса-Корте-Хаусмана) остаются верными, но требуют более сложной техники обоснования. "Приподнимаясь" над булевой решёткой подмножеств конечного множества, мы имеем возможность взглянуть под другим углом на особенности процесса решения и приблизиться к более полному пониманию причин успешного использования жадного алгоритма на наследственных структурах. Эту возможность дают геометрические решётки, которые достаточно близки к булевым (в частности, свойством атомарности), но представляют собой более широкий класс объектов.

Содержание диссертации

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Выплов, Михаил Юрьевич, 2015 год

Литература

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

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

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

[4] Баранский В.А., Выплов М.Ю., Ильев В.П. Минимизация модулярных и супермодулярных функций на L-матроидах // Известия Иркутского государственного университета, Серия "Математика". 2011. Т. 4, № 3. С. 42-53.

[5] Баранский В .А., Выплов М.Ю., Ильев В. П. Минимизация модулярных и супермодулярных функций на L-матроидах // Информационный бюллетень Ассоциации математического программирования. Екатеринбург: УрО РАН. 2011. № 12. XIV Всероссийская конференция "Математическое программирование и приложения" (тезисы докладов). С. 148-149.

[6] Баранский В.А., Выплов М.Ю., Ильев В.П. О задаче максимизации модулярной функции в геометрической решётке // Известия Иркутского государственного университета. Серия "Математика". 2013. Т. 6, № 1. С. 2-13.

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

[8] Ван дер Варден Б. Л. Алгебра. М.: Наука. 1976.

[9] Выплов М.Ю. Решётки замкнутых множеств наследственных систем // Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодёжной конференции. Екатеринбург: УрО РАН. 2009. С. 10-15.

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

[11] Выплов М.Ю., Ильев В.П. Системы множеств и операторы слабого замыкания // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск. 2009. С. 119.

[12] Выплов М.Ю., Ильев В.П. Решётки замкнутых множеств систем независимости // Материалы X Международного семинара "Дискретная математика и ее приложения". Москва: Издательство Механико-математического факультета МГУ. 2010. С. 224-227.

[13] Выплов М.Ю. Обобщение теоремы Биркгофа-Уитни для наследственных систем // Труды Института математики и механики УрО РАН. Екатеринбург. 2011. Т. 17, № 4. С. 66-75.

[14] Выплов М.Ю., Ильев В.П. Приближенное решение задачи максимизации модулярной функции в геометрической решётке // Статистика-Моделирование. Оптимизация: Сборник трудов Всероссийской конференции (Челябинск, 28 ноября - 2 декабря 2011 г.). Челябинск: Издательский центр ЮУрГУ. 2011. С. 108-112.

[15] Выплов М.Ю. О представлении систем множеств в терминах замыкания // Тезисы докладов и лекций Международной школы-конференции "Математические проблемы информатики", Омск, 20-27 сентября 2013 г. Омск: Издательство ОмГТУ. 2013. С. 13-14.

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

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

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

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

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

[21] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. Изд. 3. M.: URSS. 2013.

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

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

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

[25] Ильев В.П. О задачах на матроидах, разрешимых жадным алгоритмом // Тез. докл. 13-й Всероссийской конф. "Математическое программирование и приложения". Екатеринбург. 2007. Информ. бюлл. Ассоциации математического программирования. № 11. Научное издание. Екатеринбург: УрО РАН. 2007. С. 176-177.

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

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

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

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

[30] Ковалев M. M. Матроиды в дискретной оптимизации. Изд. 3. М.: URSS. 2011.

[31] Попович А.Л., Репницкий В.Б. О представлении решеток решетками конгруэнций полугрупп // Труды ИММ УрО РАН. 2010. Т. 16, № 2 С. 199-208.

[32] Репницкий В.Б. О представлении решеток решетками подполугрупп // Изв. вузов. Матем. 1996. № 1. С. 60-70.

[33] Репницкий В.Б. О решеточно универсальных многообразиях алгебр // Изв. вузов. Матем. 1997. № 5. С. 53-59.

[34] Семёнова M.B. О решетках, вложимых в решетки подпорядков // Алгебра и логика. 2005. Т. 44, № 4. С. 483-511.

[35] Семёнова М.В. Вложение решеток в производные решетки // Современные проблемы математики. 2011. Вып. 15. С. 67-82.

[36] Семёнова М.В., Замойска-Дженио А. О решетках подклассов // Сибирский математический журнал. 2012, Т. 53, № 5. С. 1111-1132.

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

[38] Хачатуров В. Р., Хачатуров Роман В., Хачатуров Рубен В. Оптимизация супермодулярных функций (супермодулярное программирование) // Журнал вычислительной математики и математической физики. 2012. Т. 52, № 6. С. 999-1000.

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

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

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

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

[43] Birkhof! G. Abstract linear dependence in lattices // Amer. J. Math. 1935. V. 57. P. 800-804.

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

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

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

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

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

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

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

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

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

[53] Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Math. 1978. V. 24, № 3. P. 261-276.

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

[55] II'ev V.; Linker N. Performance guarantees of a greedy algorithm for minimizing a supermodular set function // European J. Oper. Res. 2006. V. 171, № 2. P. 648-660.

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

[57] Kariv 0., Hakimi S.L. An algorithmic approach to network location problems. II. The p-medians // SIAM J. Appl. Math. 1979. V. 37, № 3. P. 539-560.

[58] Khachaturov Vladimir R., Khachaturov Roman V., Khachaturov Ruben V. Supermodular programming on lattices // Computer Science J. of Moldova. 2003. V. 11, № 1 (31). P. 43-66.

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

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

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

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

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

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

[65] Repnitskii V.B. A new proof of Tuma's theorem on intervals in subgroup lattices // Contributions to General Algebra. 2005. V. 16. P. 213-230.

[66] Tuma J. Intervals in subgroup lattices of infinite groups //J. Algebra. 1989. V. 125, № 2. P. 367-399.

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

[68] Tutte W. T. Matroids and graphs // Trans. Amer. Math. Soc. 1959. V. 90. P. 527-553.

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

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

[71] White N., ed. Theory of matroids. Cambrige: Cambrige Univ. Press. 1986.

[72] Whitman Ph.M. Lattices, equivalence relations, and subgroups // Bull. Amer. Math. Soc. 1946. V. 52. P. 507-522.

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