Целочисленное сбалансирование трехмерной матрицы тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Смирнов, Александр Валерьевич

• Смирнов, Александр Валерьевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Смирнов, Александр Валерьевич

Содержание.

Введение.

1 Постановка задачи.

2 Кратные сети и кратные потоки: обобщение теории потоков Форда-Фалкерсона.

2.1 Кратная сеть целочисленного сбалансирования.

2.2 Полный поток и обобщенный путь прорыва.

3 Алгоритм нахождения максимального кратного потока для решения задачи сбалансирования.

3.1 Предварительные замечания.

3.2 Описание алгоритма.

3.3 Примеры работы алгоритма.

3.4 Обоснование алгоритма.

4 А^Р-полиота задачи целочисленного сбалансирования трехмерной матрицы.

5 Сравнительный анализ алгоритмов целочисленного сбалансирования

5.1 Результаты вычислительных экспериментов для произвольных тестов.

5.2 Результаты вычислительных экспериментов для задач ЦСЗ

6 Минимизация ошибок округления в задаче целочисленного сбалансирования матрицы.

6.1 Задача минимизации ошибок округления и алгоритм ее решения

6.2 Пример работы алгоритма минимизации ошибок округления

Введение диссертации (часть автореферата) на тему «Целочисленное сбалансирование трехмерной матрицы»

Многие задачи дискретной оптимизации могут быть решены при помощи моделей и методов теории графов. Примеры приложений теории графов приведены, например, в [2, 7, 8, 16, 17, 18, 25, 34, 56, 57, 60]. Важным разделом теории графов является теория потоков Форда-Фалкерсона (см. [1, 31, 50, 59, 62]). Потоковые алгоритмы применяются для решения различных задач (см., например, [6, 9, 13, 26, 30, 33, 65, 72, 77, 80, 81]).

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

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

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

Также задачи целочисленного сбалансирования возникают в банковской сфере, например, в задаче оптимального округления плана валютных счетов (постановка такой задачи дана в [47]). Имеется некий план валютных счетов, которые группируются по нескольким показателям (например, вид валюты, клиент, дата). Такой план при к показателях может быть представлен в виде /¿-мерной сбалансированной матрицы, внутренними элементами которой являются величины счетов, а на боковых гранях стоят суммы по соответствующим показателям. При переводе одной валюты в другую возникает проблема округления величин счетов до целых чисел. Округление до ближайшего целого может привести к значительному расхождению в итоговой сумме, что ведет к определенным финансовым потерям. Поэтому необходим такой алгоритм целочисленного сбалансирования матрицы плана, чтобы расхождение в общей сумме было минимальным.

В работах [21, 24] была рассмотрена задача целочисленного сбалансирования двумерной матрицы. Пусть имеется матрица А размерности (п + 1) х (т+ 1) с вещественными элементами аг7-, для которой выполняются следующие условия баланса: п т гп п г € 1 ,п);

Ищется такая целочисленная матрица Б, что выполняются условия: dij G { [aij\, foyl} (íGO, n, j G 0, m); d00 = [а00 + 0.5J; n m тп n doo = 11, dl° = YL dij ^ e doj = dii Ü e ' i=1 J=1 j-1 г=1

Эта целочисленная матрица D называется сбалансированной для матрицы А. Без ограничения общности можно считать, что элементы исходной нецелочисленной матрицы А принадлежат полуинтервалу [0,1).

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

1) Каждому элементу а^ матрицы А поставим в соответствие вершину сети Xij, а элементу аоо поставим в соответствие еще дополнительную вершину zoo

2) Соединим вход ж0 сети с каждой вершиной х¿o (i G 1,п) дугами пропускной способности [a¿oJ, а также с вершиной жоо дугой пропускной способности d00 - XXi KoJ •

3) Соединим вершину жоо с каждой из вершин Xíq (г G 1,п) дугами пропускной способности [a¿o] — |a¿oJ

4) Соединим со стоком z каждую из вершин xqj (j G 1, m) дугами пропускной способности [a0jj, а вершину z0о - дугой пропускной способности doo - Ej"Li LaoiJ •

5) Соединим с вершиной z00 каждую из вершин xqj (j G l,m) дугами пропускной способности faoj] — \aoj\

6) Соединим каждую из вершин Xíq (i G 1 ,п) со всеми вершинами х^ (i G 1, п, j G 1, га) дугами пропускной способности

7) Соединим с каждой вершиной xqj (j G 1 ,т) все вершины хц (i G l,n, j'E 1,т) дугами пропускной способности fa¿j].

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

Л*11

Рис. 1. Сеть целочисленного сбалансирования двумерной матрицы

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

4>г < ^00

Покажем, что величина ¿оо определяет наименьшую пропускную способность разреза в сети. Каждый разрез делит все вершины транспортной сети на левую 01 и правую части и его можно описать двумя множествами вершин: = | г е 1,П, ХгО Е ОД, Т = {щ I 3 € 1дтг, Ху £ С/}.

Пропускная способность такого разреза R(S,T) = ^foiol + ЕК1 + \S\ ■ \Т\ > ies зет m п ЕгЕ+ ЕгЕ+ ЕЕ^ es 3=1 з&т i=i ies m п п тп ti m

ЕЕа^+ЕЕ а^+Е Е= Е Е ^+Е Е^ ЕЕ ies ¿=i ier ¿=i ¿es i=i ¿es J'eT ¿=i j=i и, так как R(S, T) - целое чис'ло, то n m r(S,T) > rEEayi = i=i j=i

Таким образом, минимальная пропускная способность разреза равна (¿сю и по теореме Форда-Фалкерсона (см. [59]) величина наибольшего потока в сети равна c¿oo

Пусть <р - наибольший поток в сети и f(x(j) (i G 0, п, j G 0,m) - величина потока, проходящего через вершину xij . Образуем матрицу D, для которой doo = Vz= Гаоо + 0.5], dij = f(xij) (i G 0~ñ, j G 0,ra).

Из условий неразрывности потока следует выполнение условий баланса и условий dij G {La¿jJ) ra¿jl} ^ 0,n, j G 0, m). Таким образом, задача сбалансирования двумерной матрицы всегда имеет решение и его можно получить, построив алгоритм на основе алгоритма пометок для решения задачи о наибольшем потоке.

В случае, когда задача целочисленного сбалансирования имеет несколько решений, возникает вопрос о нахождении сбалансированной матрицы D, наименее отклоняющейся от исходной (см. [24]). В качестве меры отклонения здесь естественно взять либо сумму абсолютных величин отклонений; либо сумму квадратов отклонений. Покажем, что эту задачу можно свести к решению некоторой задачи о наибольшем потоке минимальной стоимости для описанной выше транспортной сети со следующей функцией стоимости С, определенной на дугах сети: с(хго.Жу) = 1 - <2у (г е 1,71, 3 € 1,т)\ с = 0 для всех остальных дуг сети.

Покажем, что сбалансированная матрица I)0, соответствующая наибольшему потоку минимальной стоимости обращает в минимум функционалы

I п т

ЕЕ г=1 ,7 = 1

1п т

Е^--^)2- (2)

1=1 1=1

Пусть Б1 - сбалансированная целочисленная матрица, доставляющая минимум функционалу (1) и предположим противное: г=1 ]—1 ¿=1 j=l

Тогда

Ее1-ау) + Е < Е ^ ~ + Е аУ ■■

Разобьем каждую сумму на две:

4=1 4=0 4=0

1 - + Е ^ ~+ Е + Е <

4=1=4 4=^4 4=0=4 4=0^4 Е (1ау)+ Е (1ау)+ Е Е

4=1=4. 4=1^4 4=°=4

После приведения получим:

Е Е Е (!-%)+ Е

4=^4 4=0^4 откуда следует

1-2 а13)< 22 (1-2ау).

Так как обе матрицы сбалансированы, то число их нулевых элементов одинаково (как и единичных), а потому одинаково число элементов, которые для одной матрицы равны 0, а для другой равны 1, с числом элементов, которые для одной матрицы равны 1, а для другой равны 0. Поэтому из последнего неравенства получаем

22 аг? > Е

4=1*4 4=1 Так как матрица минимальна по стоимости, то

4=1 4=1 откуда получаем

Х-а>1])< Е С1"^) и далее агз < аV

4=1*4 4=1^Ч

Последнее неравенство противоречит неравенству (3), что и требовалось для доказательства минимальности функционала (1) для матрицы В0

Из минимальности стоимости г аго

22(1 - агз) = N0 + 0.5] -4=1 4=о следует максимальность Но значение функционала (2) п тп

22 Е^у -= I] ^ -+ Е 4 =

1=1 7 = 1 4=1 4=0 1 - 2 22 аг3 + 22 < + Е аЪ =соп^ -2 Е

4=1 4=1 4=1 4=0 4=1 агЗ при этом минимально, что и требовалось доказать.

Аналогичная задача сбалансирования может быть поставлена и в трехмерном случае (см., например, [41, 42, 45]). Имеется трехмерная вещественная матрица А с неотрицательными элементами (г £ 0, п, ] 6 0,ш, р € 0, £), для которых выполнены условия баланса: каждый элемент с некоторыми 7гулевыми индексами равен сумме всех элементов, для которых ненулевые индексы оставлены неизменными, а нулевые индексы заменены всеми возможными ненулевыми значениями диапазонов соответствующих индексов.

Требуется так округлить элементы матрицы до целых значений сверху или снизу (элемент аооо округляется до ближайшего целого), чтобы остались неизменными условия баланса. |

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

1) возможность простого сведения к потоковой задаче;

2) существование решения'в задаче сбалансирования;

3) построение алгоритма, который мог бы находить решение возможно боI лее эффективным методом, чем общий метод решения задач целочисленного линейного программирования;

4) решение задачи минимизации ошибок округления при целочисленном сбалансировании;

5) сложность задачи сбалансирования.

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

Задано множество А = {ai,. ., ап} основных значений, некоторое множество А его подмножеств Aj С А (j б 0, т) (назовем их подмножествами связей), включая исходное множество (А = {Aj \ А3 С А (j Е 1, т), Л о = А}), и множество D — {dj (j £ 0,m)} дополнительных значений, связывающих элементы каждого из соответствующих подмножеств: clj = Yla^A, (jGÜ~m).

Округление для (¿о считается 'заданным. Требуется округлить основные и дополнительные вещественные значения так, чтобы для множества X округленных основных значений, множества Y округленных дополнитель

I ных значений и подмножеств Х3 С X (j £ 0, га), состоящих из округленных элементов соответствующих подмножеств Aj выполнялись те же связи У] — Yhx%€XjXl (з ^ 0, ттг). В качестве критерия оптимальности берется минимизация суммы ошибок основных элементов при условии определенной близости I округлений дополнительных элементов: тг у3 - dj| < I {I G IN, j б 0,т) \xi ~ ai\ min •

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

Х{ — а;! < 1 (г € 1,п) ^^ \Уз — dj| —> min i=l рассматривается в задачах округления значительно реже.

Нетрудно заметить, что задача целочисленного сбалансирования ^-мерной матрицы при произвольном натуральном к является задачей оптимального округления. В работе [37] приведен еще один пример подобной задачи.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Смирнов, Александр Валерьевич

Заключение

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

Также в работе показана А^Р-полнота задачи целочисленного сбалансирования трехмерной матрицы.

Кроме того, рассмотрена задача минимизации ошибок округления в задаче целочисленного сбалансирования, приведен и обоснован алгоритм ее решения.

Таким образом, получены ответы на все основные вопросы, интересовавшие нас в ходе исследования.

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

1. Адельсон-Вельский, Г. М. Потоковые алгоритмы / Г. М. Адельсон-Вельский, Е. А. Диниц, А. В. Карзанов. - М.: Наука, 1975. - 120 с.

2. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Баранский, В. В. Расин. Ижевск: НИЦ «РХД», 2001. - 288 с.

3. Афраймович, Л. Г. Многоиндексные задачи распределения ресурсов в иерархических системах / Л. Г. Афраймович, М. X. Прилуцкий // Автоматика и телемеханика. 2006. - №6. - С. 194-205.

4. Афраймович, Л. Г. Многопродуктовые потоки в древовидных сетях / Л. Г. Афраймович, М. X. Прилуцкий // Известия РАН. Теория и системы управления. 2008. - №2. - С. 57-63.

5. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. - 536 с.

6. Вабенко, М. А. Быстрый алгоритм построения декомпозиции многополюсных потоков / М. А. Бабенко // Вестник Московского университета. Серия 1: Математика. Механика. 2006. - №2. - С. 52-53.

7. Басакер, Р. Конечные графы и сети / Р. Басакер, Т. Саати. М.: Наука, 1974. - 368 с.

8. Берж, К. Теория графов и ее приложения / К. Берж. М.: Изд-во ИЛ, 1962. - 320 с.

9. Водолазов, Н. Н. Об особенностях потока в сетях с барьерной достижимостью / Н. Н. Водолазов // Вестник ДГТУ. 2008. - Т. 8, №2. -С. 127-136.

10. Гасс, С. Линейное программирование (методы и приложения) / С. Гасс. М.: Физматгиз, 1961. - 304 с.

11. Голынтейн, Е. Г. Новые направления в линейном программировании / Е. Г. Голыптейн, Д. Б. Юдин. М.: Сов. радио, 1966. - 524 с.

12. Гофман, А. Д. Целочисленные граничные точки выпуклых многогранников / А. Д. Гофман, Д. Б. Краскал // Линейные неравенства и смежные вопросы. М.: Изд-во ИЛ, 1959. - 472 с.

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

14. Данциг, Д. Линейное программирование, его обобщения и применения / Д. Данциг. М.: Прогресс, 1966. - 600 с.

15. Евстигнеев, В. А. Применение теории, графов в программировании / В. А. Евстигнеев. М.: Наука, 1985. - 352 с.

16. Зыков, А. А. Основы теории графов / А. А. Зыков. М.: Наука, 1987.- 384 с.

17. Камерон, П. Теория графов, теория кодирования и блок-схемы / П. Камерон, Дж. ван Линт. М.: Наука, 1980. - 144 с.

18. Кнут, Д. Э. Искусство программирования, тт. 1,2,3 / Д. Э. Кнут. М.: Вильяме, 2000.

19. Ковалев, М. М. Дискретная оптимизация (целочисленное программирование) / М. М. Ковалев. Мн.: Изд-во БГУ, 1977. - 192 с.

20. Кондаков, А. С. Задача сбалансирования матрицы плана / А. С. Кондаков, В. С. Рублев // Доклады Одесского семинара по дискретной математике. / Южный научный центр HAH и МОН Украины. Одесса: Астропринт, 2005. - Вып. 2. - С. 24-26.

21. Корбут, А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкелынтейн. М.: Наука, 1969. - 368 с.

22. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзёрсон, Р. Ривест, К. Штайн. М.: Вильяме, 2005. - 1296 с.

23. Коршунова, Н. М. Задача целочисленного сбалансирования матрицы / Н. М. Коршунова, В. С. Рублев // Современные проблемы математики и информатики. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. - Вып. 3.- С. 145-150.

24. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кри-стофидес. М.: Мир, 1978. - 432 с.

25. Кузьминова, M. В. Периодические динамические графы. Задача о максимальном потоке / М. В. Кузьминова // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки. -2008. №1. - С. 14-19.

26. Кук, Д. Компьютерная математика / Д. Кук, Г. Бейз. М.: Наука, 1990.- 384 с.

27. Кук, С. А. Сложность процедур вывода теорем / С. А. Кук // Кибернетический сборник, новая серия. М.: Мир, 1975. - Вып. 12 - С. 5-15.

28. Литвак, Б. Г. Задачи линейного программирования, допускающие сетевую постановку / Б. Г. Литвак, А. М. Раппопорт // Экономика и мат. методы. 1970. - Т. 6, вып. 4. - С. 594-604.

29. Лютаев, Д. А. Моделирование транспортной сети Владивостока на основе теории потокового равновесия / Д. А. Лютаев // Информатика и системы управления. 2006. - №2(12). - С. 17-28.

30. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника.- М.: Мир, 1981. 324 с.

31. Макконнелл, Дж. Основы современных алгоритмов / Дж. Макконнелл.- 2-е доп. изд. М.: Техносфера, 2004. - 368 с.

32. Миронов, А. А. Взвешенные графы с фиксированными степенями вершин и потоки в сетях / А. А. Миронов // Известия РАН. Теория и системы управления. 2007. - №3. - С. 81-84.

33. Ope, О. Теория графов / О. Ope. M.: Наука, 1980. - 336 с.

34. Пападимитриу, X. Комбинаторная оптимизация / X. Пападимитриу, К. Стайглиц. М.: Мир, 1984. - 512 с. .

35. Раскин, Л. Г. Многоиндексные задачи линейного программирования / Л. Г. Раскин, И. О. Кириченко. М.: Радио и связь, 1982. - 240 с.

36. Рублев, В. С. Минимизация ошибок округления плана / В. С. Рублев // Математика, кибернетика, информатика. Труды Международной конференции, посвященной памяти профессора А. Ю. Левина, 25-26 июня 2008 г. Ярославль: ЯрГУ, 2008. - С. 145-150.

37. Рублев, В. С. Потоковый алгоритм целочисленного сбалансирования матрицы / В. С. Рублев // Материалы VII Международного семинара «Дискретная математика и ее приложения» (29 января 2 февраля 2001 г.). Часть II. - М.: МГУ, 2001. - С. 185-187.

38. Рублев, В. С. TVP-полнота задачи целочисленного сбалансирования трехмерной матрицы / В. С. Рублев, А. В. Смирнов // ДАН. 2010. -Т. 435, №3. - С. 301-303.

39. Рублев, В. С. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения / В. С. Рублев, А. В. Смирнов // Моделирование и анализ информационных систем. 2010. - Т. 17, №2. -С. 72-98.172 I

40. Рублев, В. С. Целочисленное сбалансирование 3-мерной матрицы плана /' В. С. Рублев, А. В. Смирнов // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское 4-6 марта 2006 г.). М.: МГУ, 2006. - С. 302-308.

41. Рублев, В. С. Задача оптимального округления плана валютных счетов / В. С. Рублев, А. В. Смирнов // Кибернетика и высокие технологии XXI века. Воронеж: НПФ «Саквоее», 2008. - Т. 1. - С. 112-123.

42. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. -М.: Мир, 1984. 456 с.

43. Смирнов, А. В. Задача целочисленного сбалансирования трехмернойматрицы и сетевая модель / А. В. Смирнов // Моделирование и анализинформационных систем. 2009. - Т. 16, №3. - С. 70-76.

44. Смирнов, А. В. Сравнительный анализ алгоритмов целочисленного сбалансирования матрицы / А. В. Смирнов // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.). М.: МГУ, 2010. - С. 430-432.

45. Смирнов, А. В. Целочисленное сбалансирование 3-мерной матрицы /

46. Татт, У. Теория графов / У. Татт. М.: Мир, 1988. - 424 с.

47. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.: Мир, 1977. -208 с.

48. Феллер, В. Введение в теорию вероятностей и ее приложения, тт. 1,2 /1. B. Феллер. М.: Мир, 1967.

49. Форд, Л. Р. Потоки в сетях / Л. Р. Форд, Д. Р. Фалкерсон. М.: Мир, 1966. - 276 с.

50. Харари, Ф. Теория графов / Ф. Харари. М.: Мир, 1973. - 304 с.

51. Хачиян, Jl. Г. Полиномиальный алгоритм в линейном программировании / Л. Г. Хачиян // ДАН СССР. 1979. - Т. 244, №5. - С. 1093-1096.

52. Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху. М.: Мир, 1974. - 520 с.

53. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. М.: Наука, 1986. - 384 с.

54. Bazaraa, M. Linear programming and network flows / M. Bazaraa, J. J. Jarvis. 2nd ed. - New York: John Wiley к Sons, 1990. - 684 p.

55. Bondy, J. A. Graph theory with applications / J. A. Bondy, U. S R. Murty. New York: American Elsevier, 1977. - 272 p.

56. Dantzig, G. B. Note on solving linear programs in integers / G. B. Dantzig // Naval Research Logistics Quarterly. 1959. - V.6, №1. - P. 75-76.

57. Dantzig, G. B. Application of the simplex method to a transportation problem / G. B. Dantzig // Activity Analysis of Production and Allocation / Editor: Т. C. Koopmans. New York: Wiley, 1951. - P. 359-373.

58. Edmonds, J. Theoretical improvements in algorithmic efficiency for network flow problems / J. Edmonds, R. Karp // Journal of the Association for Computing Machinery. 1972. - V. 19, №2. - P. 248-264.

59. Ford, L. R. Maximal flow through a network / L. R. Ford, D. R. Fulkerson // Canadian Journal of Math. 1956. - №8. - P. 399-404.

60. Garey, M. R. Strong NP-completeness results: motivation, examples and implications / M. R. Garey, D. S. Johnson // Journal of the Association for Computing Machinery. 1978. - V. 25, №3. - P. 499-508.

61. Goldberg, A. V. Finding minimum-cost circulations by canceling negative cycles / A. V. Goldberg,' R. E. Tarjan // Journal of the Association for Computing Machinery. 1989. - V. 36, №4. - P. 388-397.

62. Gomory, R. E. An algorithm for integer solutions to linear programs / R. E. Gomory // Recent Advances Math. Program. New York, San Francisco, Toronto, London: McGraw-Hill Book Co., Inc., 1963. - P. 269302.

63. Gomory, R. E. Outline of an algorithm for integer solutions to linear programs / R. E. Gomory // Bull. Amer. Math. Soc. 1958. - V. 64, №5. - P. 275-278.

64. Gomory, R. E. Solving linear programming problems in integers / R. E. Gomory // Proc. Sympos. Appl. Math. 1960. - V. X. - P. 211215.

65. Gomory, R. E. An application of generalized linear programming to network flows / R. E. Gomory, T. C. Hu // Journal of the Society for Industrial and Applied Mathematics. 1962. - V. 10, №2. - P. 260-283.

66. Imai, H. On the practical efficiency of various maximum flow algorithms / H. Imai // Journal of the Operations Research Society of Japan. 1983. -V. 26, №1. - P. 61-83.

67. Karp, R. Reducibility among' combinatorial problems / R. Karp // Complexity of Computer Computations / Editors: R. E. Miller, J. W. Thatcher. New York: Plenum, 1972. - P. 85-103.

68. Lawler, E. Combinatorial optimization: networks and matroids / E. Lawler. Holt, Rinehart and Winston, 1976. - 384 p.

69. Lempitsky, V. Global optimization for shape fitting / V. Lempitsky, Y. Boykov // Proc. IEEE CVRP'07. IEEE Computer Soc, 2007 - P. 1-8.

70. Lombaert, H. A multilevel banded graph cuts method for fast image segmentation / H. Lombaert, Y. Sun, L. Grady, C. Xu // Proc. IEEE ICCV'05 IEEE Computer Soc., 2005. - V. 1. - P. 259-265.

71. Papadimitriou, C. H. On the complexity of integer programming / C. H. Papadimitriou // Journal of the Association for Computing Machinery. 1981. - V. 28, №4. - P. 765-768.

72. Picard, J. C. Minimum cuts and related problems / J. C. Picard, H. D. Ratliff // Networks 1975. - V. 5, №4. - P. 357-370.