Введение к работе
Актуальность темы исследований. Широкое внедрение вычислительной техники во многие области жизни стимулировало интенсивное развитие дискретной математики и такой ее важной части как комбинаторика. Многие задачи возникающие в областях, связанных с компьютерными приложениями, являются комбинаторными задачами о покрытии и упаковке. Они часто встречаются в исследовании операций, математической экономике, при построении сетей связи. К классу задач о покрытиях и упаковках относится большое число задач из теории графов, комбинаторики, мивимизалии булевых функций, теории кодирования, дискретной геометрии.
Задача о покрытии заключается в нахождении для данного семейства подмножеств конечного множества X минимального по числу членов подсемейства, дающего в объединении X. Задача об упаковке заключается в нахождении максимального по числу членов подсемейства попарно непересекающихся подмножеств.
Важной характеристикой качества покрытий и упаковок является понятие плотности. Плотностью покрытий (упаковок) называется среднее число подмножеств, покрывающих элементы базового множества. По определению, плотность любого покрытия не меньше 1 и плотность любой упаковки не превосходит 1. Идеальной является ситуация, когда плотность равна 1. В этом случае покрытие является одновременно и упаковкой и такие объекты обычно называются совершенными. Ряд классических комбинаторных объектов являются совершенными покрытиями и упаковками: совершенные коды, системы Штейнера, проективные плоскости, тактические конфигурации. Они обладают многими замечательными свойствами, однако, редко существуют. Поэтому изучаются близкие по свойствам к совершенным покрытия и упаковки, которые существуют в более широком диапазоне. Они и являются основным предметом рассмотрения в диссертации.
Покрытия (упаковки) называются асимптотически точными, если с ростом
размерности их плотность стремится к 1. Иногда их называют также асимптотически хорошими.
Основная проблема, рассматриваемая в диссертации - это нахождение условий существования и способов построения асимптотически точных покрытий и упаковок. Рассматривается и более общая проблема: для задач целочисленного линейного программирования (ЦЛП) типа покрытия и упаковки найти условия совпадения асимптотик целочисленных и рациональных оптимумов.
О ее трудности говорит тот факт, что для задачи о покрытии и упаковке единичного п-меряого куба шарами единичного радиуса только сравнительно недавно было доказано существование асимптотически точных покрытий и упаковок *. Для шаров большего радиуса эта проблема по прежнему остается открытой.
Классическим примером задач о покрытии и упаковке являются задачи о покрытии и упаковке /-подмножеств n-элементного множества его fc-подмно-жествами. Совершенные покрытия (упаковки) в этом случае называются системами Штейнера 5(га, к, ї). Проблема описания необходимых и достаточных условий существования систем Штейнера очень трудна и далека от своего разрешения.
Поэтому проблема существования асимптотически точных покрытий и упаковок привлекает внимание многих исследователей. Впервые существование асимптотически точных покрытий и упаковок /-подмножеств Ж-подмножесг-вами п-элементного множества для всех фиксированных I < к было доказано В. Редлем в 1985 г. (Rodl V., On a packing and covering problem. Europ. J. Combinatorics 5 (1985) 69 - 78). Тем самым, была доказана известная гипотеза Эрдеща-Ханаии. Затем появился ряд работ, в которых обобщались эти результаты. Однако, описания условий на рост функций к = А:(п) и I = /(п), обеспечивающих существование асимптотически точных покрытий и упаковок, известно не было. Одним из основных результатов главы 1 диссертации является нахождение величины "пороговой функции" к(п) для существования асимптотически точных упаковок и покрытий.
Вопросы, связанные со сложностью алгоритмов решения задач о покрытии и упаковке и проблемой устранения перебора, имеют аспект, актуальность которого была осознана в последние годы. Многочисленные исследования продемонстрировали исключительную важность вероятностных методов и вероятностных алгоритмов. В связи с широким применением вероятностных методов
Кабатянский Г.А., Нанченко В.Н., Упаковки.и сокрытия пространства Хэммиига единичными шарами, Проблемы передачи информ., 1988, т. 24, вып. 3, С. 3 - 16
в комбинаторике в настоящее время многие результаты носят характер теорем существования. Именно таким является результат Редля о существовании асимптотически точных [п, к, 1)-похрытий и упаковок при всех фиксированных / < к. Поэтому работы, связанные с нахождением явных конструкций, привлекают внимание многих исследователей.
Встречается два понятия явной конструкции - в слабом и сильпом смыслах. Явная конструкция в слабом смысле требует наличия детерминированного алгоритма, который строит все подмножества семейства за время, ограниченное полиномом от размера семейства. Явная конструкция в сильном смысле требует наличия алгоритма, который по померу подмпожества (в семействе) вы-давает это подмножество за время, ограниченное полиномом от длины входа, т.е. от логарифма размера семейства.
Значительные усилия в последнее время были направлены на нахождение явных конструкций асимптотически точных покрытий я упаковок. На зтом пути в работах Spencer J., Asymptotic packing via a branching process, Random Structures and Algorithms 7 (1995) N 1 и Rodl V., Thoraa 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 был предложен вероятностпый алгоритм построения асимптотически точных покрытий, имеющий сложность 0(п1). Наконец совсем недавно Д. Грабле построил детерминированный алгоритм нахождения асимптотически точных покрытий и упаковок с временем ограниченным полипомом от размера покрытия (упаковки) (т.е. от 0(п'))). Отметим, что во всех этих результатах сложность алгоритма построения зависит от параметров покрытий и упаковок киї (причем в показателе), и они не являютсмя явными в сильном смысле.
Нахождение явных в сильном смысле конструкций асимптотически точных покрытий и упаковок было открытой проблемой. Ее решение, найденное автором, приводится в главе 2 диссертации.
Задача о покрытии часто формулируется на языке (0,1)-матрип как задача о глубине таких матриц. Более общая задача об а-глубине (0,1)-матриц заключается в нахождении для заданной (0,1)-матрицы А минимального числа строк (обозначаемого обычно єа(А)), образующих подматрицу, содержащую в каждом столбце не менее а-единиц. Рассмотрение задач о глубине и а-глубине (0,1)-матриц исторически тесно связало с классами Райзера. В каноническом случае это классы Л(и, тп, к, s), состоящие юяхт (0,1)-матриц, удовлетворя-
ющих условиям сбалансированности по строкам и столбцам, то есть имеющих в каждом столбце ровно к и в каждой строке ровно s единиц. Эти классы изучались Г. Райзером, Д. Фалкерсоном, В.Е.Таракановым и другими авторами. Однако, многие задачи, связаные с этими классами, остаются нерешенными. Даже асимптотика числа матриц в классах A(n,m,k,s) известна только при сильных ограничениях иа рост параметров hi. Наиболее известная трудная задача, связанная с покрытиями (О.І)-матриц, это задача о нахождении максимальной а-глубины классов Райзера A(n,m,k,s).
Еще Райзер заметил, что нахождение точного значения максимальной глубины позволяет дать критерий существования проективных плоскостей. Имеет место и более общее утверждение о том, что нахождение точного значения максимальной глубины классов A(n,m,k,s) позволяет дать критерий существования систем Штейнера S(n, к, I). Поскольку эти проблемы на современном уровне представляются весьма далекими от своего решения, соответственно трудной является л задача нахождения точных значений максимальной глубины соответствующих классов Райзера.
Поэтому основное внимание уделяется получению оценок этих величин. Отметим, что ряд точных значений максимальной глубины классов А(п, т, к, s) при небольших значениях к, s и верхняя оценка были получены в работах В.Е.Тараканова. Этой задачей занимались также А.О.Гельфонд, В.К.Леонтьев, Г. Райзер, Д. Фалкерсон и другие авторы.
Общая верхняя оценка а-глубины (0,1)-матрицы с Ж, единицами в г'-м столбце была получена В.К.Леонтьевым. Однако, как показали дальнейшие исследования, асимптотическое исследование поведения этой оценки является нетривиальным. Кроме того, она основана на подсчете средних значений параметров и, поэтому, является неконструктивной. Основной открытой проблемой здесь было получение асимптотики максимальной а-гдубины классов Л(п, т, к, s). Определенный интерес представляло также построение эффективного алгоритма нахождения а-похрытия произвольной (0,1)-матрицы, удовлетворяющего верхней оценке В.К.Леонтьева. Эти задачи решаются в главах 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, С 476-483 (С. 476: "Это чрезвычайно трудный вопрос, на который не ожидается простого ответа"; С. 477: "Очень естественная вещь - пытаться аппроксимировать целочисленный оптимум рациональным. После некоторого рассмотрения становится ясно, что проблема содержит трудности как комбипаторного, так и теоретико-числового характера. Чтобы исключить последние мы ограничиваем наше внимание (О-І)-матряцами." ). Решение этой задачи, полученное в диссертации для общего случая, приводится в главе 3. Там же найдены достаточные условия асимптотического совпадения целочисленных и рациональных оптимумов.
Цель работы. Осдавпая цель - разработать методы доказательства существования и алгоритмы построения асимптотически точных упаковок и покрытий. Более конкретно:
Найти условия существования асимптотически точных покрытий и упаковок /-подмножеств ^-подмножествами n-элементного множества и получить асимптотику максимальной а-глубииы классов Райзера.
Найти условия асимптотического совпадения целочисленного и рационального оптимумов в задачах целочислепного линейного программирования.
Разработать эффективные алгоритмы построения асимптотически точных покрытий и упаковок и асимптотически точных целочисленных решений в задачах ЦЛП типа покрытия и упаковки.
Методы исследования. В работе используются методы комбинаторики, теории вероятностей, целочисленного программирования.
Научная новизиа. Все основные результаты дисертации являются новыми и опубликованы в работах автора. В диссертации получены следующие
основные результаты:
-
найдены условия существования асимптотически точных покрытий и упаковок /-подмножеств ^-подмножествами n-элементного множества;
-
найдена асимптотика максимальной а-глубины классов Райзера и доказано существование асимптотически точных а-покрытий;
-
найдены достаточные условия, гарантирующие асимптотическое совпадение значений целочисленных и рациональных оптимумов в задачах ЦЛП типа покрытия и упаковки;
-
предложен полиномиальный (от log га) алгоритм построения асимптотически точных покрытий и упаковок /-подмножеств fc-подмножествами п-эле-ментного множества;
-
построен полиномиальный алгоритм нахождения асимптотически точных целочисленных решений в задаче об а-глубине (0,1)-матрид и общих задачах ЦЛП типа покрытия и упаковки;
-
для задач ЦЛП типа упаковки предложен полиномиальный в среднем алгоритм ее решения;
-
решена проблема Эрдеша-Линиала-Ахарони о максимуме отношения величин целочисленных и рациональных оптимумов для задач ЦЛП типа покрытия и упаковки;
Практическая и теоретическая ценность. Диссертация имеет теоретический характер. Полученные результаты и разработанные методы могут найти применение при разработке и исследовании эффективности новых алгоритмов решения задач о покрытии и упаковке. Они могут оказаться полезными при исследовании задач целочисленного линейного программирования и других задач дискретной оптимизации.
Апробация работы. Результаты диссертации докладывались и обсуждались на международной конференции по основам теории вычислений (Казань, 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 наименований.
