Структурные и алгоритмические свойства мультипотоков и расширений конечных метрик

• Автор: Карзанов, Александр Викторович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 93 с.; 20х15 см

Ъ564 X о £

Оффициальные оптженты:

академик РАН, профессор

Журавлев Юрий Иванович

доктор физ.-мат

Гришухин Вячеслав Петрович

доктор физ.-мат

Кузюрин Николай Николаевич

Ведущая организация: Институт Проблем

Передачи Информации (ИППН) РАН

Защита состоится “2.^ 2001 г. в Ц часов

на заседании Специализированного Совета Д.002.013.02 Центрального Экономико-Математического Института РАН (117418, Москва, Нахимовский п~с-т ~ ,<,:7Х Телефон Совета: (095) З.Т Л Ь' '
С диссертацией в виде научного докладе в библиотеке ЦЭМИ V
Диссертация в виде науччоу /г? ■•ад
і -'41 V;' ■
Ученый секретарь Специализированного Совета
к.ф.-м.н. В.А. Скоков
Общая характеристика работы
Актуальность темы. Диссертация основывается на большой цикле взаимосвязанных работ, объединенных предметной областью и в совокупности развивающих комбинаторную теорию и эффективные методы точного решения задач о неориентированных мультипотоках (многопродуктовых потоках в неориентированных сетях) и объектах двойственной природы — разрезах и метрических расширениях (расширениях конечных метрических пространств), а также исследующих смежные теоретические и алгоритмические проблемы.
Потоки и мультипотоки в графах и сетях моделируют многие реальные процессы и находят широкие приложения при исследовании и решении задач в сферах экономики, транспортных перевозок, электротехники, связи и др. Изучение таких объектов и задач на них составляет важное направление в математическом программированиии в целом и комбинаторной оптимизации в частности. Мулътипоток может определяться двумя способами: как совокупность потоковых (внутренне сбалансированных) функций на ребрах сети, подчиняющихся общим ящичным ограничениям, и как взвешенная упаковка множества путей, соединяющих выделенные пары вершин. Теория упаковок объектов, имеющих содержательный комбинаторный смысл, таких как пути, циклы, разрезы, паросочетания и др., занимает одно из центральных мест в комбинаторной оптимизации — дисциплине, выделившейся и самостоятельную ветвь математического программирования и дискретной математики и интенсивно развивающейся в течении последних 30 лет. Выработаные в комбинаторной оптимизации методы оказываются во многих случаях более эффективными и теоретически и практически по сравнению с общими и даже проблемно-ориентированными методами математического программирования.
Теории, методам решения и приложениям однопродуктовых потоковых задач посвящено огромное число работ; эта область стала классической с выходом в свет монографии Форда и Фалкерсопа в 60-е годы. Многопродуктовые потоки оказались существенно более трудными для комбинаторного исследования. Первый нетривиальный результат в этом направлении был получен Ху, установившим комбинаторный критерий разрешимости и существование полуцелочисленного решения неориентированной двухпродуктовой задачи. Последующий вклад внесли работы Папернова, Ломоносова, Черкасского, Ловас.а, Сеймура, Скрайвера, Франка и др. авторов, в которых были получены важные структурные, алгоритмические и лр. результаты для ряда других случаев мультипотоковых и родственных задач. Однако область в целом оставалась недостаточно исследованной, и многие поставленные вопросы оставались открытыми. Диссертация значительно сокращает этот пробел.
Расширения конечных метрик появляются как двойственные объекты к мультипотокам, и соответствующие оптимизационные и структурные задачи часто исследуются параллельно. Задачи на метрических расширениях возникают и в других ветвях комбинаторной оптимизации, а также в общей теории конечных метрических пространств, и находят теоретические и практические приложения. Важное направление в теории упаковок, начатое роботами Эдмондса, Джонсона и Сеймура, рассматривает в качестве пакуемых объектов разрезы графов, метрическим эквивалентом которых являются разрезные полуметрики — ^-расширения метрики графа К2- Одна из задач этого направления — о реализации расстояний на заданных парах путем упаковки разрезных полу метрик — обобщает классическую

задачу о кратчайшем пути, и с вей тесно связана известная проблема вложимости метрики в метрическое пространство . Пример другого рода дает известная задача “о размещении оборудования”, допускающая переформулировку как задача минимизации неотрицательной линейной функции над О-расширениями заданной метрики (задача о минимальном О-расширении). Диссертация содержит целую серию структурных, алгоритмических, полиэдральных и др. результатов о конечных метриках, их расширениях и связанных с ними оптимизационных и иных задачах.
Цель работы. Диссертационная работа охватывает известные и новые задачи о мультипотоках и метрических расширениях и имеет целью существенное развитие комбинаторной теории и методов в данной области.
Значительная часть рассматриваемых задач допускает представление в виде задач линейного программирования с целыми коэффициентами, имеющих, быть может, экспоненциально большое число переменных. Разрабатываемая для них теория и методы направлены прежде всего на решение трех основных вопросов: (а) при каких условиях задача данного класса имеет решение (допустимое или оптимальное) со знаменателями, ограниченными константой, в частности, целочисленное или полуцелочисленное решение (проблема дробности)-, (б) можно ли найти решение соответствующей дробности эффективно, т.е. посредством алгоритма полиномиальной временной сложности (проблема эффективной алгоритмической разрешимости)-, (в) существуют ли специальные (комбинаторные) критерии разрешимости или оптимальности, усиливающие двойственность линейного программирования для данного класса задач (проблема специальной двойственности). Проблемы специальной двойственности и эффективной разрешимости являются центральными и при рассмотрении нелинейных задач.
Наиболее существенные результаты и их новизна:
— Для задач о допустимом мультипотоке и о максимальном мультипотоке в произ-польных и плоских сетях получены описания множеств неизбегаемых двойственных препятствий, установлены комбинаторные критерии разрешимости и оптимальности и разработаны эффективные алгоритмы построения полу- или четвертьцелочисленных решений. Полностью охарактеризованы потоковые схемы, обеспечивающие дробность 2 (полуцело-числснность). Для двойственной задачи о максимальном мультипотоке определены точные значения дробности для всех потоковых схем;
— В задаче о максимальном мультипотоке минимальной стоимости установлены точные значения дробности для всех потоковых схем. Для класса схем, обеспечивающих ограниченную дробность, разработаны эффективные алгоритмы решения. Для этого же класса эффективно решена более сильная задача о целочисленном максимальном мультилотоке минимальной стоимости, и для нее найдено комбинаторное минимаксное соотношение (обобщение формулы Мадера для максимальной упаковкиТ-путей). Установлен сложностной статус (в терминах полиномиальной разрешимости или NP-тpyднocти) целочисленной задачи для всех потоковых схем. Получено описание доминанта (Т,«^-соединений графа (обобщение теоремы Эдмондса и Джонсона о блокере Г-соединений);
— Исследованы задачи об упаковках разрезных и (2,3)-полуметрик, связанные отношениями полярной двойственности с мультипотоками. Для этих задач получены результаты о дробности, установлены комбинаторные критерии разрешимости и оптимальности и най-

эффективности.] Для р = 0 минимаксную тройку образуют Р = 0, /3 = 0, 7 = 0. Показывается, что минимаксные тройки существуют для всех р, если возможен “сдвиг” из каждой минимаксной тройки. Более строго, теорема 3.9 выводится из следующей “локальной” теоремы.
Теорема ЗЛО Пусть для р £ К.+ имеется минимаксная тройка (Р,/3, у). Тогда либо (1) существует упаковка V' такая, что [Р' — |Р|+1, и (Р',/3,7) — минимаксная тройка для р, либо (и) существуют (У: Г—и 7' : Е —> Н.+ такие, что (Р, /3', у') — минимаксная тройка дм некоторого р' > р.
Теорема 3.10 доказывается конструктивно. Для текущих р, Р, /3, 7 сперва пытаемся построить соответствующую упаковку большей мощности, т.е. реализовать случай (1). Если это невозможно (Р максимально для данных р, /3,7), то имеют место дополнительные структурные свойства, которые позволяют преобразовать (/3,7), реализуя случай (и). Показывается, что в обоих случаях преобразования осуществимы за полиномиальное от |У| число действий (здесь учитывается компактное задание /3). Кроме того, преобразования организуются так, что в порождаемом ими процессе ситуации (1) и (11) чередуются. Учитывая |Р| < |Г|, мы получаем эффективный алгоритм решения (3.9) для всего спектра значений параметра (ср. теорему 3.4).
Теорема 3.11 Существуют числа 0 = р0 < р1 < ... < рк, упаковки Т-путей 0 = Ра, Ръ---,Рк, функции 0 = До, А, - •• ,Рк,0ш на Т и функции 0 = 70, Ты - • •, 7*. 7Ь+1 на Е такие, что: (а) к < Е и |Ро| < [Р | < .. . < [Рк; (Ь) для г = 0, 1 и 0 < с < 1 упаковка
Р; и пара (1 - «)(А* ТО + е(/?г+ г, Тг'ы) образуют минимаксную тройку для р — (1 -€)р;+е?;г+!; (с) для любого X > 0 упаковка Р% м пара (Вк,Ук) + А(А+ьТ*ы) образуют минимаксную тройку для р = рк + А. Указанные объекты строятся в сильнополиномиальное время.
В частности, последняя упаковка Г* дает оптимальное решение для (3.8). Версия алгоритма для ЦЗМС с полной многодольной схемой строит максимальный целочисленный мультипоток минимальной стоимости в псевдополиномиальное время 0(с(£7)<2(|1/|)), где <д(п) — полином.
$ 4 (Т,с1)-соединения минимального веса
Для графа (7 = (V, Е) и четного множества Т С V полюсов подмножество ребер ВСЕ называют Т-соединеншм (Т-]от), если оно реализуется упаковкой V (простых) Т-путей и циклов в С (т.е. В = и(Р : Р £ Р) такой, что каждый полюс является концом ровно одного пути. Это эквивалентно тому, что степень с^в(ц) вершины и £ V в подграфе (У,В) — нечетная т. и т. т., когда и £ Т. Задача о нахождении Т-соединения В минимального веса ю(В) для заданной функции гю : Е -4 Ъц весов ребер весьма популярна в комбинаторной оптимизации и имеет важные применения (в частности, к ней сводится известная задача “о китайском почтальоне”: найти замкнутый маршрут минимальной длины, проходящий через все ребра графа). Эдмондс и Джонсон [Ш] нашли эффективный алгоритм ее решения (с временной оценкой 0(|^|4)) и показали, что блокером множества Г-соединений является