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

Введение

Глава 1. Группа симметрии многогранника системы независимости

1.1. Основные понятия.

1.2. Линейные симметрии и автоморфизмы.

1.3. Аффинные симметрии и //"-отображения.

1.4. Критерий существования //"-отображения.

1.5. Симметрии с единичным сдвигом.

1.6. Аффинные симметрии специальных систем независимости

Глава 2. Понижение размерности задачи на системе независимости

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

2.2. Задача об упаковке множества.

2.3. Полиэдральная схема понижения размерности.

2.4. Комбинаторная схема.

2.5. Процедура ветвления и задача об упаковке

Глава 3. Приближенные алгоритмы решения задачи об упаковке

3.1. Приближенная схема понижения размерности.

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

3.3. Приближенный алгоритм для некоторых специальных систем независимости.

3.4. Задача о наибольшем независимом множестве вершин и алгоритм ПР.

3.5. Вычислительный эксперимент.

Экстремальные задачи на системах независимости образуют большой раздел комбинаторной оптимизации. Многие известные задачи (задачи о рюкзаке, об упаковке множества, о наибольшем независимом множестве вершин графа и др.) являются частными случаями обшей экстремальной задачи на системе независимости. Данные задачи актуальны как модели большого числа прикладных проблем, связанных с функционированием промышленных предприятий и сферы обслуживания, формированием бюджетов различных уровней, составлением расписаний, распределением ресурсов, инвестиционной политикой и многими другими областями [1,2,21.24,34].

Помимо прикладного значения, задачи на системах независимости представляют значительный теоретический интерес. Многие из них относятся к числу Л'ЛР-трудных [8]. Проблематика задач на системах независимости охватывает исследование их структуры и сложности, разработку точных и приближенных алгоритмов решения, построение теоретических оценок точности алгоритмов и другие направления [6,8,14,15,20,22,24,45,50.78]. Особенно актуальным является разработка новых подходов к анализу структуры задач и построению эффективных алгоритмов их решения.

В настоящей работе проведено исследование обшей экстремальной задачи на системе независимости с использованием аффинных преобразований евклидова пространства, оставляющих многогранник, ассоциированный с задачей, на месте (симметрии). Этот подход, лежащий в русле полиэдральных методов анализа комбинаторных экстремальных задач, в последнее время получил развитие в [3,25,29,30,35.39,41,43,57].

Применение симметрий оказалось наиболее продуктивным для исследования и построения алгоритмов решения задачи об упаковке множества [18,76,78]. Эта задача возникает при моделировании процессов с независимыми элементами, в частности, при распределении ресурсов. проектировании операционных систем ЭВМ, составлении расписаний [18,49,55,56,69,85,86,89].

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

Значительное число точных алгоритмов решения задачи об упаковке множества предложено на основе метода ветвей и границ [50,51,83], в котором используется комбинаторная структура задачи, и аппарата целочисленного линейного программирования (ЦЛП) [12,15-17]. Основной проблемой разработки алгоритмов ветвей и границ является достижение компромисса между точностью получаемой верхней границы целевой функции и временем ее вычисления в каждой возникающей подзадаче. В алгоритме Балаша [50], например, для получения более качественной верхней границы тратится больше времени на ее вычисление, чем в алгоритме Гаррахана и Пардалоса [71], в котором время вычисления верхней границы незначительно. Из методов ЦЛП для решения задачи об упаковке применяются метод отсечения [15,17], Лэнд и Дойг [17,22]. перебора L-классов [1-3,16,23] и др.

Так как задача об упаковке множества является А^Р-трудной [8], то с точки зрения решения прикладных проблем особый интерес представляет разработка эффективных приближенных алгоритмов [48,76-79]. В многих из них используются комбинаторная структура и графовая модель задачи. Описание основных алгоритмов этого типа содержится в [78]. Некоторые последние результаты приведены также в [76].

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

Достаточно эффективным для решения задачи об упаковке множества является жадный (greedy) алгоритм [65,77]. В случае невзвешенной задачи (все веса элементов равны единице) он имеет линейную зависимость трудоемкости от количества элементов и характеризуется хорошей точностью получаемых решений на некоторых специальных задачах [74]. На взвешенной задаче его трудоемкость равна 0(п2) (п - количество переменных), а оценка точности - (к — 1), где к - максимальное количество вершин, индуцирующих звезду [77].

Из имеющихся оценок для взвешенных задач можно также отметить следующие. Метод Немхаузера-Троттера [77,82], основанный на поиске минимального разреза в сети, в зависимости от используемого в нем вспомогательного алгоритма, имеет оценку Д/2 или (А + 2)/3, где Л - максимальная степень вершин соответствующего графа. Для метода удаления подграфа (его трудоемкость равна 0(п2)) построена оценка G(n(loglog п/ log п)2), где п - количество вершин в соответствующем задаче графе [58]. -Лучшей на сегодняшний день считается оценка 0(п/ log2 п) Боппана-Халлдорссона [75].

Кроме того, для решения задачи об упаковке множества разрабатываются алгоритмы локального поиска, генетические алгоритмы, алгоритмы с запретами и др. [46.47,52,68,88]. Широкое распространение получили гибридные методы, в которых сочетаются различные алгоритмы решения этой задачи.

Хастад в [7-3] показал, что при условии неразрешимости Л"Г-тру.лных задач рандомизированным полиномиальным алгоритмом для задачи об упаковке не существует приближенного полиномиального алгоритма с оценкой п1~€ при любом б > 0. Усиление этой оценки до n1//2-f, как показано там же, означаю бы, что SV = V.

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

Системой независимости на конечном n-элементном множестве Е называется непустое семейство J подмножеств множества Е, удовлетворяющее аксиоме: если J Е J и / С <7, то / Е Пусть М - евклидово пространство, ассоциированное с Е посредством взаимнооднозначного соответствия между координатными осями пространства ИИЕ и множеством Е. Всякому S С Е сопоставим его вектор инциденций xs Е по правилу: х^ = 1 при е G S , Zg = О при е 0 5. Многогранник системы независимости J определим, как P(J) = Convex1 | I £ J) [4,62].

Предлагаемый подход к исследованию системы независимости ¿7" основан на невырожденных аффинных преобразованиях евклидова пространства, оставляющих на месте многогранник, ассоциированный с J. Он находится в русле полиэдрального подхода к решению экстремальных комбинаторных задач [26-28,57.60,62.66.67,70,87]. который в последние годы позволил получить заметный эффект при решении практических задач [72 и др.].

Основными результатами главы являются: доказательство изоморф-ности подгруппы линейных симметрий многогранника системы независимости группе ее автоморфизмов (теорема 1.1), свойства которой рассматривались в работах [5,35 и др.]; представление нелинейной симметрии в виде суперпозиции преобразования и так называемого Н-отображения, Н Е J, где 1 - 2х\ О cpi{x)

1 - 2х% ° 1-2^/ а ^-отображение - любое линейное невырожденное преобразование, переводящее многогранник системы независимости Р(^) в многогранник ж + Хн.

Сош(х<1АН \ 1 £ где .] АН- симметрическая разность множеств ./ и Н (теорема 1.2).

Этот результат позволяет описывать аффинные преобразования многогранника в терминах Я-отображений. На этом пути получены критерии существования нелинейной симметрии для априори заданного Н в обшем случае и для одноэлементных Н (теоремы 1.3 и 1.4). Доказано, что порождающими группы симметрий многогранника системы независимости являются подгруппа линейных симметрий и симметрии с единичными сдвигами (теорема 1.5).

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

В настоящее время одной из особенностей реальных экстремальных задач является их высокая размерность [8]. Результаты первой главы могут служить основой для построения процедур понижения размерности таких задач.

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

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

Значительное внимание уделяется задаче об упаковке множества и ее приложениям. Построена модель функционирования операционной системы ЭВМ (ОС) с учетом возможности автоматического изменения приоритетов выполняемых процессов. Это позволяет во многих случаях устранить такие трудности в работе ОС, как появление тупиков и "зависание" процесса или всей ОС.

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

4') если элементы а и Ь зависимы, а и с зависимы, то Ъ и с зависимы;

В1) добавление элемента а к любому независимому множеству элементов, попарно независимых с а, дает независимое множество.

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

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

В третьей главе описаны приближенные алгоритмы решения общей задачи на системе независимости. Показано, что данные алгоритмы наиболее применимы к задаче об упаковке множества (теорема 3.1). Для этой задачи разработан ряд приближенных алгоритмов решения, построены оценки точности (теоремы 3.2 pi 3.3) в терминах зависимости элементов. Кроме того, исследовано поведение предложенных алгоритмов на частных случаях задачи об упаковке, в том числе на задаче о наибольшем независимом множестве вершин графа. Для анализа разработанных алгоритмов проведен вычислительный эксперимент. Основные цели эксперимента:

1) анализ эффективности вложения процедуры понижения размерности в метод ветвей и границ;

2) сравнение разработанных приближенных алгоритмов между собой и с известными алгоритмами:

3) выработка рекомендаций по применению алгоритмов для решения задачи об упаковке.

Эксперименты проводились на задаче об упаковке множества (первая и вторая серии экспериментов) и задаче о наибольшем независимом множестве вершин (третья и четвертая серии). В общей сложности было решено 185 задач об упаковке множества и 196 задач' о наибольшем независимом множестве вершин графа. Из полученных результатов вытекает, что предложенные в работе приближенные алгоритмы имеют хорошую экспериментальную оценку точности как на случайных, так и на специально сгенерированных задачах и в среднем лучше известного жадного алгоритма, алгоритмов Хватала и Кларксона [78].

12

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

Результаты работы докладывались на Втором Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996), Х-ой Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1997), Международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997). Международной Сибирской конференции по исследованию операций (Новосибирск, 1998). Х1-ой Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999), а также на семинарах кафедры математического моделирования Омского государственного университета. Института информационных технологий и прикладной математики СО РАН и Института математики им. С.Л. Соболева СО РАН.

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

Автор выражает искреннюю признательность научному руководителю Р.Ю.С'иманчёву за постоянное внимание и всестороннюю поддержку при выполнении данной работы.

Основные результаты диссертации:

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

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

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

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

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

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

Заключение

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

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

1. Ашманов С.А. Введение в математическую экономику. М.: Наука, 1984.

2. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

3. Болоташвили Г.Г., Ковалев М.М. Частично упорядоченный многогранник. Тез. докл. VII конференции "Проблемы теоретической кибернетики". Горький. 1988.

4. Брёнстед А. Введение в теорию выпуклых многогранников. -М.: Мир. 1988.

5. Вьялицпн A.A., Панченко К.А. Применение теории групп для решения комбинаторных задач. Петропавловск: Северо-Казахстанский университет, 199-5.

6. Глебов Н.И. Базисные системы и задача минимизации на пересечении базисных систем. // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1984. Вып. 25. С. 58-67.

7. Гранже М., Менсьё Ф. OS/2. Принципы построения и установка. -М.: Мир. 1991.

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

9. Дейтл Г. Введение в операционные системы (в 2-х томах). ~ М.: Мир, 1987.

10. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981.

11. Емеличев В.А. и др. Лекции по теории графов. М.: Наука, 1990.

12. Заблоцкая O.A., Колоколов A.A. Вполне регулярные отсечения в булевом программировании. // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1983. Вып. 23. С. 55-63.

13. Заозерская ЛА. Некоторые гибридные алгоритмы для задачи о покрытии. // Тез. докл. Х-ой Всероссийской конференции "Математическое программирование и приложения". Екатеринбург: УрО РАН, 1997. С. 100.

14. Ильев В.П. Оценка погрешности градиентного алгоритма для систем, независим,ости. // Дискретный анализ и исследование операций. 1996. Т.З. No.l. С. 9-22.

15. Колоколов A.A. Методы дискретной оптимизации. Учебное пособие. Омск: ОмГУ, 1984.

16. Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании. // Сиб. журнал, исследования операций. 1994. N.2. С. 18-39.

17. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование.- М: Наука. 1969.

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

19. Коэн Л.Дж. Анализ и разработка операционных систем. М.: Наука, 197-5.

20. Кузюрин H.H. Полиномиальный в среднем алгоритм в целочисленном линейном программировании. // Сибирский журнал: исследования операций. Новосибирск: ИМ СО РАН, 1994. Том 1, N.3. С. 38-48.

21. Лотов A.B. Введение в экономико-математическое моделирование.- М.: Наука, 1984.

22. Пападпмитриу X., Стайнглиц К. Комбинаторная оптимизация. -М.: Мир, 1985.

23. Сайко И.В. Исследование мощности L-накрытий некоторых задач о покрытии. // Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. С. 76-97.

24. Сергиенко И.В. Математические модели и методы решения задач, дискретной оптимизации. Киев: Наук.думка, 1988.

25. Симанчёв Р.Ю. Линейные симметрии многогранника паросочета-ний и автоморфизмы графа. // Вестник Омского университета. 1996. N.1. С. 18-20.

26. Симанчёв Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных k-факторов. // Дискретный анализ и исследование операций. Новосибирск: ИМ СО РАН, 1996. Т.З, N.3. С. 84110.

27. Симанчёв Р.Ю. Структура нецелочисленных вершин релаксации многогранника к-факторов. // Математические структуры и моделирование. Омск: ОмГУ, 1998. Вып.1. С. 20-26.

28. Симанчёв Р.Ю. Смежность вершин многогранника к-факторов. // Математические структуры и моделирование. Омск: ОмГУ, 1998. Вып.2. С. 39-50.

29. Симанчёв Р.Ю. Линейные симметрии многогранника паросочета-ний. // Тез. Второго сибирского Конгресса по индустриальной и прикладной математике. Новосибирск: ИМ СО РАН, 1996. С. 125.

30. Симанчёв Р.Ю. Группа линейных симметрии многогранника Ъ-факторов. // Тез. межд. конф. "Проблемы оптимизации и экономический приложения"'. Омск, июль, 1997. С. 143.

31. С'хрейвер А. Теория линейного и целочисленного программирования (в 2-х томах). М.: Мир, 1991.

32. Харари Ф. Теория графов. М.: Мир. 1973.

33. Хоар Ч. Взаимодействующие последовательные процессы. -М.: Мир, 1989.

34. Хорошевский В.Г. Инж:енерный анализ функционирования вычислительных машин и систем. М.: Радио и связь, 1987.•35. Червяков О.В. Линейные симметрии, и автоморфизмы матроида. // Фундаментальная и прикладная математика. Омск: ОмГУ, 1994. С. 81-89.

35. Червяков О.В. Аффинные преобразования матроида. // Тез. докл. Второго Сибирского конгресса по прикладной и индустриальной математике. Новосибирск: ИМ СО РАН, 1996. С. 127.

36. Червяков О.В. Понижение размерности оптимизационной задачи на системе независимости. // Тез. докл. Х-ой Всероссийской конференции "Математическое программирование и приложения". Екатеринбург: УрО РАН, 1997. С. 229.

37. Червяков О.В. Алгоритм нахождения симметрии многогранника системы независимости. // Тез. докл. Международной конференции "Проблемы оптимизации и экономические приложения". Омск: ОмГУ, 1997. С. 166.

38. Червяков О.В. Симметрии многогранника системы независим,ости. // Вестник Омского университета. Омск, 1997. N.-3. С. 18-20.

39. Червяков О.В. Симметрии многогранника системы независимости со сдвигом единичной мощности. // Материалы Международной Сибирской конференции по исследованию операций. Новосибирск: ИМ СО РАН, 1998. С. 70.

40. Червяков О.В. Аффинные симметрии многогранника системы независимости. // Математические структуры и моделирование. Омск: ОмГУ, 1998. Вып.1. С. 27-32.

41. Червяков О.В. Понижение размерности задачи об упаковке множества. // Тез. докл. XI-ой Всероссийской конференции "Математическое программирование и приложения". Екатеринбург: УрО РАН, 1999. С. 279.

42. Червяков О.В. Аффинные симметрии многогранника системы независимости с единичным сдвигом. // Дискретный анализ и исследование операций. Новосибирск, 1999. Серия 1, Том 6. N.2. С. 82-96.

43. Червяков О.В. Алгоритмы решения задачи об упаковке множества с использованием симметрии многогранника. Препринт №1. Омск: Омский госуниверситет, кафедра мат. моделирования. 2000.

44. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Наука. 1995.

45. Arkin Е.М., Hassin R. On local search for weighting k-.set packing. // ESA'97, LNCS 1284. 1997. P. 13-22.

46. Bafna V., Narayanan B.O., Ravi R. Non-overlapmg local alignments (weighted independent sets of axis parallel rectangles). // WADS'95, LNCS 955, 1995. P. 506-517.

47. Baker B.S. Approximation algorithms for NP-comphte problems on planar graphs. // J. ACM, 41, 1994. P. 153-180.

48. Balas E. Project scheduling with resource contramts. Applications of mathematical programming techniques. Beale Ed.,. English Universities Press. London, 1970.

49. Balas E., Yu C.S. Finding a Maximum Clique in an Arbitrary Graph. // SIAM J. Comput. 15(4). 1986. P. 1054-1068.

50. Balas E., Xue J. Weighted and Unweighted Maximum Clique Algorithms with Upper Boud.s from, Fractional Coloring. // Algorithmica, 15. 1996. P. 397-412.

51. Balas E., Niehaus W. Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems. // Journal of Heuristics, 4. 1998. P. 107-122.

52. Bar-Yehuda R. One for the Price Two: A Unified Approach for Approximating Covering Problems. Technion. Computer Science Depatment. Technion Report CSS0920, 1997.

53. Beineke LAV., Pippert R.E.Prorerties and characterizations of k-trees. // Mathematica, 18. 1971. P. 141-151.

54. Bellmore M. Greenberg H., Jarviss J.Multi-commodity disconnecting sets. // Man. Sei. 16. 1970. P. 427.

55. Bellmore M. Ratliff B.D. Optimal defense of multi-commodity networks. // Man. Sei. 18. 1971. P. 174.

56. Bolotashvili G., Girlich E., Kovalev M. New Facets of the Linear Ordering Polytope. Preprint Nr. 15. Otto-von-Guericke-Universität Magdeburg. Fakultät für Mathematik, 1995.

57. Boppana R.B. Halldörsson M.M. Approximating maximum independen-dent sets by excluding subgraphs. // BIT, 32(2), June 1992. P. 180-196.

58. Chvatal V. A greedy heuristic for the set-covering problem,. // Math, of Oper. Res., 4(3), 1979. P. 233-235.

59. Chvatal V. On Certain Polytopes Associated with Graphs. // .Journal of Combinatorial Theory (B). 18, 1975. P. 138-154.

60. Clarkson K. ,4 modification of the greedy algorithm for the vertex cover. // Info. Proc. Lett., 16, 1983. P. 23-25.

61. Conforti M., Laurent M.On the facial structure of independence system polyhedra. // Math, of Operations Research. 1988, V.13, N.4. P. 543-555.

62. Cook W., Pulleyblank W.R. Linear systems for constrained matching problems. // Math, of Operations Research. 1987. ¥.12, N.l. P. 97-120.

63. Dijkstra E.W. Cooperating Sequential Processes. Technological University. Eindhoven, The Netherlandss, 1965.

64. Edmonds J. Matroids and the greedy algorithm. // Math. Programming, 1971. V.13. N.2. P. 127-136.

65. Edmonds J. Maximum mathching and a polyhedron with 0.1-vertices. // Journal of Reserch of the National Bureau of Standarts B. 1965. P. 125130.

66. Edmonds J. Johnson E.L. Mathching: a well-solved class of integer liner programs. // Ed. by R.Gay, H.Hanani, N.Sauer and J.Sohonheim, Combinatorial sstructures and their applications. Gordon and Beach. New York, 1970. P. 89-92.

67. Eremeev A.V. Some Approximate Algorithms for the Vertex Cover Problem. // Book of Abstr. of SOR'99. Otto-von-Guerike-Universität Magdeburg, 1999. P. 46.

68. Freeman D.R., Jucker The line balancing problem. // J. of Industrial Engineering. 18. 1967. P. 361.

69. Gamble A.B., Pulleyblank W.R. Forest Covers and a Polyhedral Intersection Theorem,. // Mathimatical Programming, 1989. P. 49-58.

70. Garraghan R., Parclalos P.M. An exact algorithm for the maximum clique problem. // Operation Research Letters, 9, 1990. P. 375-382.

71. Grötshel M., Holland 0. Solution of lage-scale symmetric travelling salesman problem,. // Math, of Operation Reserch, 1986. V.ll, N.4. P. 537-569.7.3. Hastacl .J. Clique is hard to approximation within n1^6. // FOCS'96, 1996. P. 627-636.

72. Halldorsson M.M., Radhakrishnan J. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. // Algorithmica, 18, 1997. P. 145-163.

73. Halldorsson M.M. Approximation via partitioning. Res. Report ISS-RR-95-0003F, Japan Adv. Inst, of Sei. and Tech., Mar. 1995.

74. Halldorsson M.M. Approximation of independents sets in graphs. A survey paper, from APPROX. 1998.

75. Hochbaum D.S. Efficient bounds for the stable set, vertex cover, and set packing problems. // Disc. Applied Math., 6, 1983. P. 243-254.

76. Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. Chapter 3 in Approximation Algorithms for NP-Hard Problems. PWS Publishing Company. 1996. P. 94-143.

77. Johnson D.S. Approximation algorithms for combinatorial problems. // J. of Comput. Syst. Sei., 9, 1974. P. 256-278.

78. Johnson D.S., Trick M.A. Introduction to the Second DIM ACS Challenge: Clique, Colloring, and Satisfiability. // DIMACS Series in Discrete Math, and Theoretical Comp. Sei., Vol.26, 1995. P. 1-10.

79. Karpinski M., Zelikovsky A. Approximating dense cases of covering problems ECCC Technical report TR 97-001, 1997.82. iNemhauser G., Trotter L.E. Vertex packings: structural properties and algorithm,s. // Mathematical Programming, 8, 1975. P. 232-248.

80. Pardalos P., Xue J. The maximum clique problem. // J. of Global Optimization, 4, 1994. P. 301-328.

81. Paschos V.T. A survey of approximately optimal solutions to some covering and packing problemss. // ACM Computing Surveys, 29(2), June 1997. P. 171-209'.

82. Rutman R.A. An Althorithm for placement of inter-connected elements based on minimum wire length. // Proc. of AFIPS Conf. 20, 1964. P. 477.

83. Salveson M.E. The assembly line balancing problem,. // J. of Industrial Engineering. 6, 1955. P. 18.106

84. Simanchev R.Yu. The Sup-port inequalities and facets of combinatorial polytopes. // Intern, conf. "Optimal Discrete Structures and Algorithms", Rostock, Sept., 1997. P. 62.

85. Soriano P., Gendreau M. Solving the Maximum Clique Problem. Using a Tabu-Search Approach. // Annals of Operations Research, 41, 1993. P. 385-403.

86. Steinberg L. The background wiring problem; a placement algorithm. // J. of SIAM (Review). 3. 1961. P. 37.