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

¡'16 ОД

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

КУЗЮРИН НИКОЛАЙ НИКОЛАЕВИЧ

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

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1997

Работа выполнена в Институте системного программирования Российской академии наук

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

Официальные оппоненты: доктор физико-математических наук профессор АЛЕКСЕЕВ В.Б.; доктор физико-математических наук ГРИШУХИН В.П.; доктор физико-математических наук профессор ЛЕОНТЬЕВ В.К.

Ведущая организация - Институт математики Сибирского отделения РАН.

Зашита состоится " С^Ич -^-цр^ 1997 г. в " часов на заседании диссертационного совета Д002.32.06 при Вычислительном центре РАН. Адрес: 117967, ГСП-1, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра РАН.

Автореферат разослан "Ь " 1997 г.

Ученый секретарь диссертационного совета Д002.32.06 кандидат физико-математических наук — ШВАРТИН С.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Покрытия (упаковки) называются асимптотически точными, если с ростом

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

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

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

Классическим примером задач о покрытии и упаковке являются задачи о покрытии и упаковке i-подмножеств n-элементного множества его ¿-подмножествами. Совершенные покрытия (упаковки) в этом случае называются системами Штейнера S(n, к, I). Проблема описания необходимых и достаточных условий существования систем Штейнера очень трудна и далека от своего разрешения.

Поэтому проблема существования асимптотически точных покрытий и упаковок привлекает внимание многих исследователей. Впервые существование асимптотически точных покрытий и упаковок i-подмножеств ¿-подмножествами п-элементного множества для всех фиксированных I < к было доказано В. Редлем в 1985 г. (Rod! V., On a packing and covering problem. Europ. J. Combinatorics 5 (1985) 69 - 78). Тем самым, была доказана известная гипотеза Эрдеща-Ханапи. Затем появился ряд работ, в которых обобщались эти результаты. Однако, описания условий на рост функций к = к(п) и I = 1(п), обеспечивающих существование асимптотически точных покрытий и упаковок, известно не было. Одним из основных результатов главы 1 диссертации является нахождение величины "пороговой функции" к(п) для существования асимптотически точных упаковок и покрытий.

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

1КаС.панский Г.А., Панченко В.Н., Упаковки.и сокрытия пространства Хэммиига единичными шарами, Проблемы передачи информ., 1988, т. 24, вып. 3, С. 3 - 16

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

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

Значительные усилия в последнее время были направлены на нахождение явных конструкций асимптотически точных покрытий я упаковок. На зтом пути в работах Spencer J., Asymptotic packing via a branching process, Random Structures and Algorithms 7 (1995) N 1 и Rodl V., Thorna L., Asymptotic packing and the random greedy algorithm, Random Structures and Algorithms 8 (1996) 161-177 независимо был предложен вероятностный алгоритм построения асимптотически точных упакозох, имеющий сложность 0(п*). В работе Gordon D.M., Patashnik О., Kuperberg G., Spencer J.H., Asymptotically optimal covering designs, J. Comb. Theory A75 (1996) 270-280 был предложен вероятностпый алгоритм построения асимптотически точных покрытий, имеющий сложность О(п'). Наконец совсем недавно Д. Грабле построил детерминированный алгоритм нахождения асимптотически точных покрытий и упаковок с временем ограниченным полиномом от размера покрытия (упаковки) (т.е. от О(п'))). Отметим, что во всех этих результатах сложность алгоритма построения зависят от параметров покрытий и упаковок к и 1 (причем в показателе), и они не являютсмя явными в сильном смысле.

Нахождение явных в сильном смысле конструкций асимптотически точных покрытий и упаковок было открытой проблемой. Ее решение, найденное автором, приводится в главе 2 диссертации.

Задача о покрытии часто формулируется на языке (0,1)-матрин как задача о глубине таких матриц. Более общая задача об а-глубине (0,1)-матриц заключается в нахождении для заданной (0,1)-матрицы А минимального числа строк (обозначаемого обычно Еа(А)), образующих подматрицу, содержащую в каждом столбце не менее а-единиц. Рассмотрение задач о глубине и а-глубине (0,1)-матриц исторически тесно связало с классами Райзера. В каноническом случае это классы Л(и,тп, к,s), состоящие из яхт (0,1)-матриц, удовлетворя-

ющих условиям сбалансированности по строкам и столбцам, то есть имеющих в каждом столбце ровно к ив каждой строке ровно s единиц. Эти классы изучались Г. Райзером, Д. Фалкерсоном, В.Е.Таракаповым и другими авторами. Однако, многие задачи, связанно с этими классами, остаются нерешенными. Даже асимптотика числа матриц в классах A(n,m, fc, я) известна только при сильных ограничениях иа рост параметров к и s. Наиболее известная трудная задача, связанная с покрытиями (0.1)-матриц, это задача о нахождении максимальной а-глубины классов Райзера A(n,m, k,s).

Еще Райзер заметил, что нахождение точного значения максимальной глубины позволяет дать критерий существования проективных плоскостей. Имеет место и более общее утверждение о том, что нахождение точного значения максимальной глубины классов A(n,m,k,s) позволяет дать критерий существования систем Щтейнера 5(11, к, I). Поскольку эти проблемы на современном уровне представляются весьма далекими от своего решения, соответственно трудной является л задача нахождения точных значений максимальной глубины соответствующих классов Райзера.

Поэтому основное внимание уделяется получению оценок этих величин. Отметим, что ряд точных значений максимальной глубины классов A(n, т, к, s ) при небольших значениях к, s и верхняя оценка были получены в работах В.Е.Тараканова. Этой задачей занимались также А.О.Гельфонд, В.К.Леонтьев, Г. Райзер, Д. Фалкерсон и другие авторы.

Общая верхняя оценка а-глубины (0,1)-матрици с к, единицами в г-м столбце была получена В.К.Леонтьевым. Однако, как показали дальнейшие исследования, асимптотическое исследование поведения этой оценки является нетривиальным. Кроме того, она основана на подсчете средних значений параметров и, поэтому, является неконструктивной. Основной открытой проблемой здесь было получение асимптотики максимальной а-глубины классов Л(п, m, к, s). Определенный интерес представляло также построение эффективного алгоритма нахождения а-похрытм произвольной (ОД)-матрицы, удовлетворяющего верхней оценке В.К.Леонтьева. Эти задачи решаются в гладах 1 и 2 соответственно.

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

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

с непрерывными задачами оптимизации. Несмотря на некоторые продвижения нет полной ясности в вопросе о связи целочисленных и рациональных оптиму-мов задач ЛП. Естественной аппроксимацией ЦЛП-задачи является ее линейная релаксация, получающаяся из исходной задачи отбрасыванием требования целочисленпости перемепних. Основной вопрос заключается в том, чтобы оценить как влияет требование пелочисленности на величину оптимумов, т.е. оценить максимальное отношение целочисленных и рациональных оптимумов. На этом пути Л. Ловас, а также П. Эрдеш, Н. Лини ал и А. Ахарони получили оцепки, связывающие величины целочисленного и рационального оптимумов для задач ЦЛП с 0-1 коэффициентами. Однако, их распространение на общие задачи ЦЛП встретило определенные комбинаторные и теоретико-числовые трудности. Мнение об этом было высказано в работе Aharoni R., Erdos P., Linial N. Dual integer linear programs and the relationship between their optima, Proc. 17th Annual Symp. on the Theory of Computing, 1985, C. 476-483 (C. 476: "Это чрезвычайно трудный вопрос, на который не ожидается простого ответа"; С. 477: "Очень естественная вещь - пытаться аппроксимировать целочисленный оптимум рациональным. После некоторого рассмотрения становится ясно, что проблема содержит трудности как комбинаторного, так и теоретико-числового характера. Чтобы исключить последние мы ограничиваем наше внимание (0-^-матрицами." ). Решение этой задачи, полученное в диссертации для общего случая, приводится в главе 3. Там же найдены достаточные условия асимптотического совпадения целочисленных и рациональных оптимумов.

Цель работы. Осдавпая цель - разработать методы доказательства существования и алгоритмы построения асимптотически точных упаковок и покрытий. Более конкретно:

Найти условия существования асимптотически точных покрытий и упаковок /-подмножеств к подмножествами n-элементного множества и получить асимптотику максимальной а-глубииы классов Райзера.

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

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

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

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

основные результаты:

1) найдены условия существования асимптотически точных покрытий и упаковок /-подмножеств к-подмножествами n-элементного множества;

2) найдена асимптотика максимальной а-глубины классов Райзера и доказано существование асимптотически точных а-покрытий;

3) найдены достаточные условия, гарантирующие асимптотическое совпадение значений целочисленных и рациональных оптимумов в задачах ЦЛП типа покрытия и упаковки;

4) предложен полиномиальный (от log га) алгоритм построения асимптотически точных покрытий и упаковок /-подмножеств ¿-подмножествами п-эле-ментного множества;

5) построен полиномиальный алгоритм нахождения асимптотически точных целочисленных решений в задаче об а-глубине (0,1)-матриц и общих задачах ЦЛП типа покрытия и упаковки;

6) для задач ЦЛП типа упаковки предложен полиномиальный в среднем алгоритм ее решения;

7) решена проблема Эрдеша-Линиала-Ахарони о максимуме отношения величин целочисленных и рациональных оптимумов для задач ЦЛП типа покрытия и упаковки;

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

Апробация работы. Результаты диссертации докладывались и обсуждались на международной конференции по основам теории вычислений (Казань, 1987), на I Всемирном конгрессе общества математической статистики и теории вероятностей им. Бернулли (Ташкент, 1986), на международном симпозиуме по оптимальным алгоритмам (Варна, 1989), 7 Fishland-Colloquium, Вустров (ГДР, 1988), в центре им. С. Банаха (Варшава, 1985 и 1987), на Всесоюзной конференции по теоретической кибернетике (Новосибирск, 1980; Горький, 1988; Волгоград, 1990, Ульяновск 1996), на республиканском семинаре по дискретной оптимизации (Ужгррод, 1985), Всесоюзных и межгосударственных семинарах по дискретной математике и ее приложениям (Москва, 1987, 1995), Международной школе-семинаре "Дискретные модели в теории управляющих систем" (Москва, 1994), ряде советско-германских рабочих семинаров по дискретной математике, на научных семинарах в Институте ма-

тематики Венгерской АН (Будапешт, 1994), Университете им. Гумбольдта (Берлин, 1982), Университете им. Комеяского (Братислава, 1990), Университете им. В.Пик (Росток, 1982), Высшей технической школы (Ильменау, 1982), на международном коллоквиуме по комбинаторике и теории графов (Венгрия, 1996), на конгрессе по индустриальной и прикладной математике ИНПРИМ-96 (Новосибирск, 1996), в центре С.Бапаха на миписеместре по избранным темам дискретной математики (Варшава, 1996), на семинарах в Московском государственном университете им. М.В. Ломоносова, ВЦ РАН, Математическом институте РАН, Институте проблем передачи информации РАН и на ряде других семинаров и конференций.

Публикации. Основные результаты дисертации опубликованы в работах [1 - 29].

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Каждая глава разбита на несколько параграфов. Объем работы 200 страниц. Список, литературы состоит из 181 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Для конечного множества X и семейства его подмножеств F = ..., ,?„.} требуется найти минимальное по числу, подмпожеств подсемейство Р ~ {Sj | j € J}, обладающее свойством покрытия, то есть

х = u,eJs, (1)

Число \ J\ называется размером минимального покрытия.

Задача об упаковке заключается в нахождении максимального по числу подмножеств подсемейства попарно непересекающихся подмножеств PCF. Число \Р\ при этом называется размером максимальной упаковки.

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

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

Рассмотрение задач о покрытии тесно связано с так называемыми классами Райзера. Пусть то, п - натуральные числа, A(o¡j) - п X тп (0,1)-матрица, удовлетворяющая условиям сбалансированности по строкам и столбцам

m

= ¿ = l,...,n ■ (2)

¿=i

П

= 3 = 1,(3)

1=1

Класс всех таких (0,1)-матриц называется классом Райзера и обозначается A(n,m,ki,...,km,si,...,sn). Эти классы изучались Г. Райзером и другими авторами. Классы Райзера с ¿i = ... = ¿m = к и íi = ... = зп = s обозначаются через Л(п,т, к,s).

Эти классы естественно возникают при исследовании задач о покрытии и упаковке /-подмножеств ¿-подмножествами n-элементного множества.

Определение. Семейство F, состоящее из fc-подмножеств «-элементного множества, называется покрытием /-подмножеств ¿-подмножествами, если каждое í-подмножество содержится по крайней мере в одном д 6 F.

Функция М(п, к, 1) определяется как минимальное число ¿-подмножеств в покрытии / подмножеств п-элементного множества.

Определение. Семейство F, состоящее из ¿-подмножеств «-элементного множества, называется упаковкой /-подмножеств ¿-подмножествами, если каждое /-подмножество содержится не более, чем в одном д € F.

Функция ra(n, ¿,/) определяется как максимальное число ¿-подмножеств в упаковке /-подмножеств «-элементного множества ¿-подмножествами.

Покрытия и упаковки /-подмножеств ¿-подмножествами n-элементного множества часто называются (п, к, /)-покрытиями (соответственно (n, ¿, /^упаковками).

Определение. Семейство ¿-подмножеств n-элементного множества называется системой Штейнера S(n, к, /), если каждое /-подмножество содержится ровно в одном ¿-подмножестве этого семейства.

Вторым основным результатом главьг 1 является нахождение (при некоторых условиях) асимптотики еа(п,т,£,л) - максимальной а-глубины класса Райзера Л(п, т, к, s). Из этих результатов вытекает, что при определенных условиях в рассмотренной задаче существуют асимптотически точные а-покрытия.

Остановимся на этих результатах подробнее.

Определение. Максимальной а-глубиной класса Райзера /4(n,m,fc,s) называется число

£a(n,w, fc, s)— max e0(A)

Основным результатом параграфа 1.5 является получение асимптотики максимальной а-глубины ca(n,rn,k,s) 'класса Райзера A(n,m,k,s).

Теорема 1.3. Пусть А —► со при п —> оо, где 0 < со < 1. Пусть также выполнены условия: при п —♦ оо

а „ Inlnn „ lnm „ ,„.

0, ---»0, —--► 0. 6)

к lnm fc

Тогда при п—*оо

еа(п, m,k,s)

— lnm g v л.

ЩГ^) при taíí

1-У0а при fep - с;

где уа - корень уравнения

(у - Со) In - - - со lay = соси

1 -Со

такой что у о > 1.

Случай, когда выполнено условие £ —>.0 при п —> оо рассмотрен в теореме 1.4, где найдена асимптотика и для этого случая.

Исследования, проводимые в последние десятилетия, продемонстрировали исключительную важность вероятностных методов. Успешно применяются они и в теории частично упорядоченных множеств [8], [7], а также для построения эффективных вероятностных алгоритмов. Проблема их дерандомизации (то есть построения детерминированных алгоритмов) является одной из центральных (см. Alón N, Spencer J.H., The probabilistic method, Wiley, New York,

oo

1991). Кроме того, в связи с широким применением вероятностных методов в настоящее время многие результаты в комбинаторике носят характер теорем существования. Именно такими являются результат Редля о существовании асимптотически точных (п, к, /)-покрытий и упаковок при всех фиксированных I < к и верхняя оценка В.К.Леонтьева для а-глубины классов Райзера. Имеется много причин, по которым вероятностное доказательство существования некоторого объекта или построение вероятностного алгоритма являются недостаточными и требуется явная конструкция объекта или эффективный детерминированный алгоритм его построения. Поэтому работы, связанные с нахождением явных конструкций и техникой дерандомизации вероятностных алгоритмов, находятся в центре внимания многих современных исследований.

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

В параграфе 2.1 предложен почти оптимальный детерминированный алгоритм построения асимптотически тачных покрытий и упаковок 1-подмножеств к-подмножествами п-элементного множества. Время и память этого алгоритма ограничены полиномом от log п, что дераядомизирует результат Редля и дает явную в сильном смысле конструкцию асимптотически точных покрытий и упаковок. Доказана следующая

Теорема 2.1. Для произвольных натуральных чисел i и к (1 < к) существует последовательность Рп(к, I) асимптотически точных (п, к, /)-упаковок и нумерация fc-подмножеств в каждой упаковке Рп(к, I) такие, что

1) существует алгоритм, который по данному натуральному г находит г-е ¿-подмножество из Рп(к, I) используя o(logn) арифметических операций и операций сравнения с O(log побитовыми числами;

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

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

Проблемы, связанные с дерапдомизацией вероятностных алгоритмов при построении целочисленных решений, привлекают внимание многих исследователей. После работы Raghavaa P., Probabilistic constructions of deterministic algorithms: approximating packing integer programs, J. Comput. and Syst. Sci., 1988, v. 37, N 4, 130-143, в которой вероятностным методом было доказано существование достаточно хороших целочисленных решений в задаче аппроксимации на решетке, появилось много работ, в которых та же техника использовалась дла других задач. Эта техника получила название метода условных вероятностей.

Метод проекций квазивыпуклого функционала (частной формой которого является метод условных вероятностей) и его использование для дерандомиза-ции вероятностного алгоритма нахождения а-глубины (0,1)-матриц был впервые предложен автором в 1985 году на Межреспубликанской конференции по дискретной оптимизации [6] и Семестре по теории вычислений в Международном центре С.Банаха (Варшава), а также изложен на ряде семинаров в ВЦ РАН, МИ РАН, МГУ. Основные отличия работы автора [12] от близкой по духу работы П. Рагхавана заключаются в рассмотрении более общей задачи ЦЛП и получении в явном виде достаточных условий близости целочисленных и рациональных оптимумов. Кроме того, ключевая операция - эффективное вычисление проекций функционала (вычисление условных вероятностей выполнения линейных неравенств), осуществляется в работе [12] другим способом. В ней использована техника округления и масштабирования для системы неравенств, а также техника динамического программирования. При этом важную роль играют утверждения об аппроксимации решения "усеченной" задачи через решение исходной. Это, на наш взгляд, более общий подход по сравнению с техникой "пессимистических оцепок", разработанной П. Рагха-вапом и позволяющей получать детерминированные алгоритмы для задач с 0-1 коэффициентами.

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

тически точные целочисленные решения). При доказательстве существенно используются оценки для вероятностей больших уклонений сумм независимых случайных величии. Сформулируем один из полученных результатов. Рассмотрим задачу ЦЛП типа покрытия:

miicx .

Ах. > Ь, х > 0 — целые, где А целочисленная т х п матрица с неотрицательными элементами, Ь > О, с > 0 - векторы с целочисленными компонентами.

Обозначим через Z - величину ее оптимума, через q - величину оптимума линейной релаксации (т.е. задачи (7) без требования целочисленности переменных), положим Cm« = тах; Cj, dj = maxj a,j. Одним из результатов главы 3 является следующий.

Пусть при п —> оо выполнены условия:

.. 1) mía—р--» оо; 2) —---оо.

• Ojlnm с„ог

Тогда

limZ/?=l.

П-+О0

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

В главе 3 исследован также вопрос о том сколь сильно может отличаться оптимум в задачах целочисленного линейного программирования типа покрытия и упаковки от оптимума в тех же задачах без ограничения целочисленности переменных (линейных релаксациях). Оценки для максимума отношения целочисленных и рациональных одтимумов линейных программ типа покрытия и упаковки получены в параграфе 3.3. Полученные результаты дают ответ на вопрос, поставленный Эрдешем, Ланиаяом и Ахароии на ежегодном симпозиуме по теории вычислений (STOC) в 1985 г. В параграфе 3.4 описан один из вариантов метода динамического программирования и доказано, что он является полиномиальным в среднем, алгоритмом для задачи ЦЛП типа упаковки. В параграфе 3.5 показано, что при наличии отрицательных данных в задаче ЦЛП типа упаковки ее оптимум нельзя аппроксимировать даже с экспоненциальной мультипликативной точностью в предположении, что Р ф NP.

Работы по теме диссертации

1. Кузюрип Н.Н., О минимальных покрытиях и максимальных упаковках (к — 1)-подмножеств ¿-подмножествами, Матем. заметки, 1977, т. 21, N 4, С. 565-571.

2. Кузюрин Н.Н., Некоторые рекуррентные и асимптотические оценки в проблеме покрытий, Матем. заметки, 1979, т. 26, N 4, С. 603-611.

3. Кузюрип Н.Н., К задаче об о-глубине (0,1)-матриц, V Всесоюзная конф. по проблемам теоретической кибернетики. Тезисы докладов, Новосибирск, 1980, С. 146-147.

4. Кузюрин Н.Н., Асимптотическое исследование задачи о покрытии, Сб. Проблемы кибернетики, вып. 37, М., Наука, 1980, С. 19-56.

5. Кузюрин Н.Н., О сложности приближенных алгоритмов решения задачи целочисленного линейного программирования, ЖВМиМФ, 1984, N 1.

6. Кузюрип Н.Н., Значения целевой функции, мажорируемые средним значением, и задача об а-глубине (0,1)-матриц, Республиканский семинар по дискретной оптимизации. Тезисы докладов, Киев, Институт кибернетики АН УССР, 1985, С. 73-74.

7. Engel К., Kuzjurin N.N. An asymptotic formula for the maximum size of ал h-family in products of partially ordered sets. - J. Comb. Theory, Ser. A., 1984, v. 37, N 3, P. 337-347.

8. Kuzjurin N.N., On the automorphism conjecture for products of ordered sets. -Order, 1992, v. 9, P. 205-208.

9. Kuzjurin N.N., One limit theorem in combinatorial analysis, I Всемирный конгресс общества Бернулли по теории вероятностей и статистике. Ташкент, 1986, Тезисы докладов, т. II, М., Наука, 1986, С. 495.

10. Кузюрип Н.Н., Асимптотически точные полиномиальные алгоритмы в целочисленном линейном программировании, VIII Всесоюзная конф. по проблемам теоретической кибернетики. Тезисы докладов, ч. 1, Горький, 1988.

11. Kuzjurin N.N.,On one approximate algorithm for linear boolean programming, Int. Conf. FCT'87, Springer-Ferlag, Lect. Notes, 1987, 278, P. 272.

12. Кузюрин H.H. Асимптотически точные полиномиальные алгоритмы в целочисленном линейном программировании // Дискрет, мат., 1989, т. 1, N 2, С. 78-85.

13. Kuzjurin N.N., Asymptotically exact polynomial algorithms for integer linear programming, Proc. Int. Symp. on Optimal Algorithms, May 29-June 2, 1989, Varna, Bulgaria, P. 125-126.

14. Кузюрин H.H. О соотношении оптимумов в задачах линейного и целочи-

еденного линейного программирования // Дискрет, мат., 1991, т. 3, N 1, С. 98-104.

15. Кузюрин Н.Н., Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций, 1994, N 1, С. 38-48.

~ 16. Kuzjurin N.N., On asymptotically good packings and coverings // Proc. Fourth Int. Workshop Algebraic and Combinatorial Coding Theory (ACCT 4' 94), Novgorod, Russia, 1994, P. 136-138.

17. Kuzjurin N.N., Multiprocessor scheduling and expanders //Information Process. Letters, 1994, v. 51, N 6, P. 315-319.

18. Кузюрин H.H!, Метрические аспекты теории целочисленного линейного программирования // Дискретная матем., 1994, т. 6, N 4, С. 87-106.

19. Кузюрин Н.Н., Метрические соотношения в целочисленном линейном программировании // Доклады РАН, 1995, т. 340, N 3, С. 308-310.

20. Кузюрин Н.Н., Многопроцессорные расписания и комбинаторные конфигурация // Дискретная матем., 1995, т. 7, N 2, С. 77-87.

21. Кузюрин Н.Н., Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Доклады РАН, 1995, т. 343, N 1.

22. Kuzjurin N.N., On the difference between asymptotically good packings and coverings // Europ. J. Comb., 1995, v. 16, P. 35-40.

23. Cohen S.D., Kuzjurin N.N., On (n,k,i,A)-systems // Proc. of Edinburgh Math. Soc., 1995, v. 38, P. 53-62.

24. Кузюрин H.H., Оценки онтимумов задач ЦДЛ типа покрытия // Тезисы XI Международной конференции по проблемам теоретической кибернетики, Москва, 1996, С. 114.

25. Кузюрин Н.Н., О максимальной а-глубине (ОД)-матриц из классов Райзе-ра // Доклады РАН, 1996, т. 350, N 1, С. 12-13.

26. Кузюрин Н.Н., Об одной гипотезе Кирстеда // Тезисы XI Международной конференции по проблемам теоретической кибернетики, Москва, 1996, С. 113-114.

27. Кузюрин Н.Н., Оценки оптимумов задач ЦЛП типа покрытия // Сб. "Комбинаторные модели и методы", Вып. 2, М., ВЦ РАН, 1997, С. 57-72.

28. Кузюрин Н.Н., Об одной комбинаторной проблеме, связанной с оценками размерности частично упорядоченных множеств // Сб. "Комбинаторные модели и методы", Вып. 2, М., ВЦ РАН, 1997, С. 10-14.

29. Кузюрин Н.Н., Почти оптимальные нумерации асимптотически хороших покрытий и упаковок // Сб. "Методы комбинаторной оптимизации", М., ВЦ РАН, 1997, С. 12-29.