Анализ алгоритма покоординатного подъема для задач дискретной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Условия точности алгоритма в случае линейного целевого функционала

1.1 Постановки задач и описание алгоритма

1.2 Новые обобщения теоремы Радо-Эдмондса.

1.3 Условия точности в терминах, доминирования

1.4 Сильное обменное свойство

1.5 Достаточные условия точности

2 Условия точности алгоритма в случае сепарабельного целевого функционала

2.1 Постановка задачи и описание алгоритма.

2.2 Известные результаты

2.3 Критерий точности в общем случае.

2.4 Достаточные условия точности

2.5 Одно обобщение матроидов и целочисленных полиматроидов.

3 Оценки погрешности алгоритма

3.1 Постановки задач и описание алгоритма.

3.2 Известные результаты

3.3 Обобщенные ранговые функции.

3.4 Оценки относительной точности алгоритма

3.5 Субмодулярность и монотонность обобщенных ранговых функций.

3.6 Два примера: задача коммивояжера и обобщенная задача коммивояжера.

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

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

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

Идея алгоритма настолько проста и естественна, что невозможно проследить, кто первым ее придумал. Исследования алгоритма проводились еще в 1920-е годы [17]. В последние десятилетия интерес к теме алгоритмов типа покоординатного подъема во многом обусловлен следующими факторами.

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

Во-вторых, несмотря на свою простоту, во многих случаях жадные алгоритмы имеют максимальную точность в классе полиномиальных алгоритмов [31] либо являются асимптотически точными алгоритмами [2, 12].

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

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

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

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

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

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

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

Максимизация аддитивного функционала. Наиболее известные результаты относятся к задаче максимизации аддитивного функционала на семействе множеств. Пусть I — конечное множество, ю — вещественная функция на множестве 1 ж Т — некоторое семейство подмножеств множества I. Требуется максимизировать функционал w(F) = £ w(i) ieF при условии F £ Т. В другой постановке вместо условия F £ Т рассматривается условие F £ где В(Т) — семейство максимальных по включению множеств из Т (такие множества называются базами семейства Т).

Алгоритм покоординатного подъема в данном случае имеет следующий вид: алгоритм начинает работу с пустого множества А и на каждом шаге добавляет к множеству А элемент г £ / — А такой, что A U г £ Т и w(г) = max{w(j)| j £ I - A, A U j £ j27}; если A U j ^ Т при всех j £ / — А, то алгоритм заканчивает работу.

Теорема Радо-Эдмондса. Семейство множеств J- называется системой независимости, если выполнено условие монотонности вниз: из того, что А С В и В Е Т, следует А £ Т. Система независимости Т называется матроидом, если при любом А С I базы семейства Та — {F £ Т\ F С Л} имеют одинаковую мощность, Радо [43, 44] установил следующий факт.

Задача максимизации аддитивного функционала на множестве баз матроида разрешима алгоритмом покоординатного подъема.

Эдмондс [24] усилил данный результат до следующего вида.

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

Теорема Радо-Эдмондса является обобщением следующего известного результата об остовном дереве максимального веса [39].

Остовное дерево с максимальным суммарным весом ребер может быть найдено с помощью алгоритма Краскала.

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

Отметим, что связь между свойством точности алгоритма покоординатного подъема и матроидными свойствами множества допустимых решений впервые была установлена Борувкой [17], но получила широкую известность только после работ Радо и Эдмондса (см. также [26]).

Погрешность алгорима в случае систем независимости.

Относительной точностью алгоритма покоординатного подъема наги* зывается величина inf-, где w0T1T — оптимальное значение целевого о it>onT функционала и w* — значение, полученное с помощью алгоритма покоординатного подъема. Дженкинс, Кортэ и Хаусманн [31, 32, 33, 35] доказали следующее утверждение.

В случае произвольной системы независимости Т относительная точность алгоритма покоординатного подъема равна минимуму отношения функций нижнего и верхнего ранга системы Т, т.е. inf — = min{ М С 7, г(А) > 0}, w>0wonT г (А) ~ где г'(А) и г{А) — минимальная и максимальная мощности баз семейства Та

Данный результат является обобщением теоремы Радо-Эдмондса, поскольку в случае матроидов ранговые функции совпадают. Отметим также, что аналогичная оценка справедлива и в случае двойственного жадного алгоритма в минимизационной задаче [6].

Другим интересным и важным результатом в теории жадных алгоритмов является следующая фундаментальная теорема [31].

Пусть некоторый алгоритм А имеет, относительную точность, более высокую, чем алгоритм покоординатного подъема (для всех систем независимости, не являющихся матроидами). Тогда трудоемкость алгоритма А оценивается снизу как 2п~°(п\ где п = |/|.

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

Гридоиды и системы достижимых множеств. В 80-е годы начали появляться результаты о поведении алгоритмов типа покоординатного подъема в случае семейств множеств, не монотонных вниз. В частности, было проведено очень интенсивное исследование гридоидов [15, 25, 27, 28, 36, 37, 38]. Само их название говорит о том, что данное понятие связано с темой жадных алгоритмов. Семейство множеств Т называется гридоидом, если выполнены следующие условия: если А £ Т и А не пусто, то А — i £ Т при некотором i £ А; если А, В £ Т и |А| + 1 = |В|, то AUi £ при некотором i £ В — А. Отметим, что матроиды — это в точности монотонные вниз гридои-ды. Кортэ и Ловас [36] установили, что если семейство Т является гридоидом, то алгоритм покоординатного подъема позволяет максимизировать целевые функционалы, в определенном смысле совместимые с гридоидом Т. Гоэтчел [29, 30] показал, что алгоритм покоординатного подъема позволяет максимизировать аддитивный целевой функционал на множестве баз гридоида тогда и только тогда, когда выполнено сильное обменное свойство. Вскоре было доказано [28], что данное свойство является критерием точности алгоритма и в случае произвольных систем достижимых множеств, т.е. семейств множеств Т таких, что если А £ Т и А не пусто, то А — г £ Т при некотором г £ А; если А £ Т и А не максимально в то A U г £ Т при некотором г £ / - А.

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

Другим интересным примером гридоидов являются гауссовские гри-доиды. Семейство множеств Т называется гауссовским гридоидом,, если выполнены следующие условия: если А £ Т и А не пусто, то A — i при некотором % £ А; если А, В £ Т и |А| + 1 = то AUi £ Т и В —г £ Т при некотором i £ В - А.

В [13, 19] был установлен следующий результат.

Произвольная система достижимых множеств J- является гаус-совским гридоидом тогда и только тогда, когда при любом аддитивном целевом функционале и при любом к = 1,2,. на к-м шаге работы алгоритма покоординатного подъема получается множество, имеющее максимальный вес среди множеств вида А £ Т, \А\ = к.

Дельта-матроиды. После появления теоремы Радо-Эдмондса было придумано множество обобщений матроидов, так или иначе сохраняющих их оптимизационные свойства. Значительные результаты в этом направлении связаны с дельта-матроидами. Семейство Т подмножеств множества I называется дельта-матроидом, если выполнена следующая симметрическая обменная аксиома: если € ^ и a G А Д В, то А Д {a, b} Е Т при некотором b 6 А Д Б, где Л — симметрическая разность множеств.

Отметим, что матроиды — это в точности монотонные вниз дельта-матроиды, базы которых имеют одинаковую мощность. Справедлива следующая теорема [18, 20, 21].

Семейство Т является делъта-матроидом тогда и только тогда, когда задача максимизации аддитивного функционала на семействе Т разрешима симметрическим жадным алгоритмом.

Слабым местом данного алгоритма является то, что он использует довольно громоздкие оракулы, проверяющие условия существования или несуществования множества F Е Т такого, что А С F С В.

G-матроиды Тардош. Частным случаем дельта-матроидов являются g-матроиды, рассмотренные Тардош [45]. Дадим одно из эквивалентных определений. Непустое семейство множеств Т называется g-матроидом, если выполнены следующие два условия: если А, В £ Т т а £ А — В, то А - а е Т либо A U Ь - а Е Т при некотором Ь £ В — А; если A, BeJFnaeA-B, то В U a G J либо В U а — Ь £ Т при некотором Ь £ В — А.

В [45] был предложен жадный алгоритм, позволяющий максимизировать аддитивный функционал на семействе множеств g-матроида. Данный алгоритм использует простой оракул, проверяющий условие принадлежности множества семейству Т.

Максимизация линейного функционала. Задача максимизации аддитивного функционала является частным случаем задачи целочисленного программирования с линейным целевым функционалом. Пусть I — конечное множество, w — вещественная функция на множестве I, N = {0,1,2,.} и ^ — конечное семейство целочисленных неотрицательных векторов С N1). Требуется максимизировать функционал ier при условии I g $5. В другой постановке вместо условия IeS рассматривается условие X £ где — семейство максимальных векторов из

Результаты Эдмондса о полиматроидах. Рассмотрим еще более общую задачу: максимизировать линейный функционал ги(Х) при условии X е U, где Ы — произвольное подмножество R1. Для решения данной задачи Эдмондс [23] предложил использовать следующий жадный алгоритм: пусть е; — такой вектор, что ег-(г) = 1 и e;(j) = 0 при j £ I — г, I = {1,. ,п} и w(l) > . > w(m) > 0 > w(m + 1) > . > w(n); при к = 1,. ,т алгоритм полагает Х(к) = тах{ у \X{l)ei + . + Х(к - l)efci + уек £ Щ\ при к = т + 1,. ,п алгоритм полагает Х(к) = 0.

Семейство векторов U называется расширенным полиматроидом) если оно не пусто и выполнены следующие условия: из того, что X <Y и У £U, следует X £ U\ при любом А С I максимальные векторы семейства U П RA имеют одинаковую сумму компонент.

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

Справедливы следующие два утверждения [14, 23].

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

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

Алгоритм Дунстана-Вэлша. Дунстан и Вэлш [22] модифицировали жадный алгоритм Эдмондса, предложив использовать в нем более сложный оракул, связанный с множеством допустимых решений. Данный оракул для произвольного вектора X определяет, существует ли вектор Y £Ы такой, что X < Y (в этом случае пишем X £ li). Алгоритм Дунстана-Вэлша работает следующим образом: пусть / = {1,. ,п} и Щ1)| > . > Щтг)|; при к — 1,. , п алгоритм полагает Х(к) = тах{ у |X(l)ei + ••• + Х(к - l)ek-\ + уек £ U}, если w(k) > О, min{ у \X(l)ei + ••• + Х(к - 1)ек-\ + уек £ U}, если w{k) < 0.

Справедлива следующая теорема [14, 22].

Жадный алгоритм Дунстана-Вэлша позволяет максимизировать любой неотрицательный линейный функционал на компактном множестве U тогда и только тогда, когда выпуклая оболочка множества {X £ R11 X £ U} является расширенным полиматроидом.

Другие условия точности алгоритма Дунстана-Вэлша получены в более поздних работах [20, 34, 40, 42]. Данные условия связаны с би-субмодулярными полиэдрами (см. также [14]).

Максимизация сепарабельного функционала. Другой основной задачей, исследуемой в диссертации, является задача целочисленного программирования с вогнутым сепарабельным целевым функционалом. Пусть I — конечное множество, N = {0,1,2,.}, /г- — вогнутые вещественные функции на JV (г £ I) и ^ — конечное семейство целочисленных неотрицательных векторов (3s С N1). Требуется максимизировать функционал г£/ при условии X £ В другой постановке вместо условия I £ 3 рассматривается условие X £ где B($s) — семейство максимальных векторов из ^s.

Функционалы вида Y,ieifiX(i) называются сепарабелъными. Примером сепарабельного функционала является линейный функционал. В случае булевых векторов сепарабельный функционал с точностью до аддитивной константы совпадает с линейным функционалом. Алгоритм покоординатного подъема имеет следующий вид: алгоритм начинает работу с нулевого вектора X и на каждом шаге добавляет к вектору X вектор ег- такой, что X + ег £ Q и f(X + ег) = max{f(X + е,-) \ X + ej Е Щ; если X + e.j (£ Q при всех j £ /, то алгоритм заканчивает работу.

Справедлива следующая теорема [3, 11].

Пусть S — непустое конечное семейство векторов, монотонное вниз, т.е. из того, что X<Y,Ye^suXe N1, следует X Е Q. Тогда задача целочисленного программирования с вогнутым сепарабель-ным целевым функционалом разрешима алгоритмом покоординатного подъема в том и только том случае, если семейство З5 является целочисленным полиматроидом.

Данный результат является обобщением теоремы Радо-Эдмондса. По аналогии со случаем систем независимости может быть доказана и следующая более сильная теорема [8].

В случае произвольной конечной монотонной вниз системы векторов S относительная точность алгоритма покоординатного подъема равна минимуму отношения ранговых функций системы т.е. inf-f- = min{ | X G N\ q(X) > 0}, f>0 four I q(X) 1 J' где q'(X) и q(X) — минимальная и максимальная суммы компонент максимальных векторов системы не превосходящих X.

Отметим, что аналогичные теоремы справедливы также в случае, когда множество допустимых решений является производным конечным частично-упорядоченным множеством с соответствующими ограничениями типа монотонности вниз [7, 8].

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

Пусть G = (V, Е) — полный ориентированный граф и каждой дуге графа G приписан неотрицательный вес. Требуется найти гамильто-нов контур максимального или минимального суммарного веса.

Первый результат относится к максимизационной задаче. Для ее решения предлагается использовать следующий жадный алгоритм: алгоритм начинает работу с пустого множества А и на каждом шаге добавляет к множеству А одну дугу е £ Е — А максимального веса такую, что A U е образует подмножество некоторого гамильтонова контура; если \А\ = |V|, то алгоритм заканчивает работу.

В работах [9, 32, 35] показано, что относительная точность данного алгоритма имеет достижимую нижнюю оценку 1/3, причем в симметрическом случае справедлива оценка 1/2.

Другой результат относится к минимизационной задаче коммивояжера. Для ее решения предлагается использовать следующий очень простой жадный алгоритм: алгоритм начинает работу в произвольной вершине г>о £ V и на каждом шаге достраивает имеющийся путь по правилу "иди в ближайшую еще не пройденную вершину"; если все вершины пройдены, то путь замыкается в вершине vq.

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

Результаты диссертации. В настоящей диссертации рассматриваются две основные задачи: задача целочисленного программирования с линейным целевым функционалом и задача целочисленного программирования с вогнутым сепарабельным целевым функционалом. Для их решения предлагается использовать следующий алгоритм покоординатного подъема: алгоритм начинает работу с нулевого вектора X и на каждом шаге добавляет к вектору X вектор ег- такой, что получающийся вектор X + ег- принадлежит семейству S и имеет среди всех таких векторов максимальное значение целевого функционала; если X + еj £ ^s при всех j Е I, то алгоритм заканчивает работу.

Среди известных эвристик данный алгоритм является одним из самых быстрых методов. По сравнению с такими подходами, как генетические алгоритмы или алгоритмы поиска с запретами (tabu search), он лучше поддается строгому теоретическому анализу. С другой стороны, в отличие от аналогичных алгоритмов Эдмондса и Дунстана-Вэлша предлагаемый алгоритм не использует каких-либо сложных оракулов, связанных с множеством допустимых решений. (Напомним, что жадные алгоритмы Эдмондса и Дунстана-Вэлша используют оракулы, вычисляющие величины тах{ у \Х + увг 6 5} и тах{ у \Х + уег- Е соответственно. К сожалению, не всегда существуют эффективные реализации данных оракулов.)

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

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

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

В третьей главе определяются достижимые оценки относительной точности алгоритма покоординатного подъема в случае целевых функционалов обоих рассматриваемых типов. Показано, что относительная точность алгоритма равна минимуму отношения обобщенных ранговых функций. Данные результаты являются обобщениями аналогичных результатов для систем независимости и монотонных вниз систем векторов [8, 33, 35]. Установлена связь между свойством точности алгоритма и свойствами субмодулярности и монотонности обобщенных ранговых функций. В качестве приложения показано, что обобщенная максимизационная задача коммивояжера разрешима жадным алгоритмом с относительной точностью 1/2.

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

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

Международная Конференция "Проблемы оптимизации и экономические приложения", Омск, 1997;

XXXVI, XXXVII и XXXVIII Международная Научная Студенческая Конференция "Студент и научно-технический прогресс", Новосибирский Государственный Университет, 1998-2000;

III Молодежная Школа по Дискретной Математике, Институт Математики СО РАН, Новосибирск, 1999;

Международная Научная Конференция по Дискретному Анализу и Исследованию Операций "DAOR'2000" (два доклада), Институт Математики СО РАН, Новосибирск, 2000;

Международный Симпозиум по Комбинаторной Оптимизации "СО'2000", Университет Гринвича, Лондон, 2000.

Заключение

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

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

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

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

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

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

6. Получены некоторые примеры задач дискретной оптимизации, разрешимые алгоритмом покоординатного подъема с константной точностью.

1. Берж К., Теория графов и ее применение. М.: Издательство иностранной литературы. i962.

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

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

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

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

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

7. Ковалев М. М., Метод частичных порядков // Докл. АН БССР. 1980. Т 24, N 2. С.113-116.

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

9. Ковалев М. М., Котов В. М., Анализ градиентного решения задачи коммивояжера // Журн. вычисл. математики и мат. физики. 1981. Т 21, N 4. С.1035-1038.

10. Колмычевская Н. В., Некоторые обобщения алгоритма покоординатного спуска для матроида // Управляемые системы: Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1981. Вып. 21. С. 13-17.

11. Овчинников В. Г., Об одной задаче целочисленного прогаммиро-вания // Кибернетика. 1976. N 1. С.131-135.

12. Перепелица В. А., Гимади Э. X., К задаче нахождения гамиль-тонова контура на графе со взвешенными дугами // Дискретный анализ: Сб. науч. тр. Новосибирск: Институт Математики СО АН СССР. 1969. Вып. 15. С. 57-65.

13. Серганова В. В., Багоцкая Н. В., Левит В. Е., Лосев И. С., Гридо-иды и жадный алгоритм // в сб.: Системы передачи и обработки информации. Москва: Институт Проблем Передачи Информации АН СССР. 1988. Часть 2. С. 49-52.

14. Bixbi R. Е., Cunningham W. Н., Matroid optimization and algorithms // in: Handbook of combinatorics. Eds. R. Graham, M. Grotchel, and L. Lovasz. Amsterdam: Elsevier. 1995. P. 551-609.

15. Bjorner A., On matroids, groups, and exchange languages // in: Matroid Theory. Eds. L. Lovasz and A. Recski. Amsterdam and

16. Budapest: North Holland. 1985. P. 25-60. (Colloq. Math. Soc. J. Bolyai. Vol. 40).

17. Bjorner A., Ziegler G. M., Introduction to greedoids // in: Matroid application. Ed. N. White. Cambridge: Cambridge Univ. Press. 1992. P. 284-357. (Encyclopedia of Mathematics and its Applications Vol. 40).

18. Boruvka О., О jistem problemu minimalnim (On a minimal problem) // Prace Moravske Prirodovedecke Spolecnosti v Brne (Acta Societ. Scient. Natur. Moravicae). 1926. Vol. 3. P. 37-58.

19. Bouchet A., Greedy algorithm and symmetric matroids // Math. Programming. 1987. Vol. 38. P. 147-159.

20. Brylawski Т., Greedy families for linear objective functions // Studies in Appl. Math. 1991. Vol. 84, N 3. P. 221-229.

21. Chandrasekaran R., Kabadi S. N., Pseudomatroids // Discrete Math. 1988. Vol 71. P. 205-217.

22. Dress A., Havel Т., Some combinatorial properties of discriminants in metric vector spaces // Adv. in Math. 1986. Vol. 62. P. 285-312.

23. Dunstan F.D.J., Welsh D.J.A., A greedy algorithm for solving a certain class of linear programmes // Math. Programming. 1973. Vol. 5, N 3. P. 338-353.

24. Edmonds J., Submodular functions, matroids and certain polyhedra // in: Combinatorial Structures and their Applications. Eds. R. K. Guy, H. Hanani, N. Sauer, and J. Schonheim. New York: Gordon and Breach. 1970. P. 69-87.

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

26. Faigle U., On ordered languages and the optimization of linear functions by greedy algorithm // J. Assoc. Computing Machinery. 1985. Vol. 32, N 4. P. 861-871.

27. Gale D., Optimal assignments in ordered set: An application of matroid theory // J. Combinatorial Theory. 1968. Vol. 4, N 2. P. 176180.

28. Goecke O., A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids // Discrete Appl. Math. 1988. Vol. 20. P. 39-49.

29. Goecke 0., Korte В., Lovasz L., Examples and algorithmic properties of greedoids // in: Combinatorial Optimization. Ed. B. Simeone. Berlin: Springer-Verlag. 1989. P. 113-161. (Lecture Notes in Math. Vol. 1403).

30. Goetchel R., Linear objective functions on certain classes of greedoids // Preprint. Moscow: Univ. Idaho. 1983.

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

32. Hausmann D., Korte В., Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Math. 1978. Vol. 24, N. 3. P. 261276.

33. Hausmann D., Korte В., Jenkyns T.A., Worst case analysis of greedy type algorithms for independence systems // Math. Programming Study. 1980. Vol. 12. P. 120-131.

34. Jenkyns Т. A., The efficacy of the "greedy" algorithm j j in: Proc. 7th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Eds. F. Hoffman, L. Lesniak L, R. Mullin, К. B. Reid, and R. Stanton. Winnipeg: Utilitas Math. 1976. P. 341-350.

35. Kabadi S. N., Chandrasekaran R., On totally dual integral systems // Discrete Appl. Math. 1990. Vol. 26. P. 87-104.

36. Korte В., Hausmann D., An analysis of the greedy heuristic for independence systems // Annals of Discrete Math. 1978. Vol. 2. P. 6574.

37. Korte В., Lovasz L., Mathematical structures underlying greedy algorithm //in: Fundamentals of Computation Theory. Ed. F. Gesceg. Berlin and New York: Springer. 1981. P. 205-209. (Lecture Notes in Computer Sciences. Vol. 117).

38. Korte В., Lovasz L., Greedoids and linear objective functions // SIAM J. Algebraic and Discrete Math. 1984. Vol. 5, N. 2. P. 229-238.

39. Korte В., Lovasz L., Schrader, R., Greedoids. Algorithms and Combinatorics. Berlin: 4. Springer-Verlag. 1991.

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

41. Nakamura M., A characterization of those polytopes in which the greedy algorithm works // Abstract. 13th Int. Symp. on Mathematical Programming. Tokyo. 1988.

42. Prim R. C., Shortest connection networks and some generalizations // Bell System Tehn. J. 1957. P. 1389-1401.

43. Qi L., Directed submodularity, ditroids, and directed submodular flows // Math. Programming. 1988. Vol. 42. P. 579-599.

44. Rado R., A theorem on independence relations // Quart. J. Math. Oxford. 1942. Vol. 13. P. 83-89.

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

46. Tardos E., Generalized matroids and supermodular colourings // in: Matroid Theory. Eds. L. Lovasz and A. Recski. Amsterdam and Budapest: North Holland. 1985. P. 359-382. (Colloq. Math. Soc. J. Bolyai. Vol. 40).

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

48. Публикации в реферируемых изданиях

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

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

51. Шенмайер В. В., Обобщение понятия ранговой функции матроида // Дискрет, анализ и исслед. операций. 2000. Сер. 1, Т. 7, N 4. С. 111-125.

52. Публикации в материалах конференций

53. Глебов Н. И., Шенмайер В. В., Жадный алгоритм в задаче о длиннейшем пути // Материалы Международной Конференции "Проблемы оптимизации и экономические приложения", Омск, 1997.

54. Шенмайер В. В., Жадный алгоритм и задача о длиннейшем пути в графе // Материалы XXXVI Международной Научной Студенческой

55. Конференции "Студент и научно-технический прогресс", Новосибирский госуниверситет, 1998.

56. Шенмайер В. В., Обобщение теоремы Радо-Эдмондса для случая небулевых систем векторов // Материалы XXXVII Международной Научной Студенческой Конференции "Студент и научно-технический прогресс", Новосибирский госуниверситет, 1999.

57. Шенмайер В. В., Обобщение понятия ранговой функции матроида // Материалы XXXVIII Международной Научной Студенческой Конференции "Студент и научно-технический прогресс", Новосибирский госуниверситет, 2000.

58. Глебов Н. И., Шенмайер В. В., О применимости алгоритма покоординатного подъема к задачам целочисленного программирования // Материалы Международной Научной Конференции "DAOR'2000", Институт Математики СО РАН, Новосибирск, 2000.

59. Шенмайер В. В., Обобщение понятия ранговой функции матроида // Материалы Международной Научной Конференции "DAOR'2000", Институт Математики СО РАН, Новосибирск, 2000.

60. Shenmaier V. V., A greedy algorithm for one class of integer programs

61. Abstracts for the International Symposium on Combinatorial Optimization "CO'2000", University of Greenwich, London, 2000.