Алгоритмы с оценками для дискретных задач размещения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Простейшая задача размещения на максимум

Введение

1.1 Двухстороннее сведение ПЗР на максимум в сдвинутой форме к задаче MAX SAT*.

1.2 Приближенный алгоритм для задачи MAX SAT*

1.3 Сложность аппроксимации.

1.4 Разрыв двойственности

2 Задача о р-медиане на максимум и ее обобщения

Введение.

2.1 Свойства функции f(S).

2.2 Оценки точности жадных алгоритмов.

2.3 Динамическая задача о р-медиане на максимум.

2.4 Эквивалентная формулировка динамической задачи о р-медиане на максимум.

2.5 Приближенный алгоритм и его анализ.

2.6 Дерандомизация алгоритма.

3 Новая техника округления для задач с ограничением мощность

Введение.

3.1 Задача о максимальном покрытии р множествами

3.2 Задача о максимальном разрезе с ограничением на мощность

3.3 Задача о максимальном к-разрезе с ограничениями на мощность.

3.4 Задача о максимальном покрытии с ранцевым ограничением

4 Задача выполнимости на максимум с ограничением на мощность

Введение.

4.1 Линейная релаксация и приближенный алгоритм

4.2 Анализ алгоритма.

4.2.1 Технические леммы.

4.2.2 Оценка математического ожидания.

4.3 Дерандомизация.

5 Квадратичная задача о назначениях

Введение

5.1 Алгоритм и его анализ.

6 Задача о р-центре

Введение.

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

6.2 Оценка относительной погрешности.

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

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

В дискретных задачах размещения множество допустимых решений конечно, поэтому заранее известно, что оптимальное решение существует. Более того существует универсальный способ отыскания такого решения посредством полного перебора всех допустимых решений. Однако такой алгоритм поиска применим только в тех исключительных случаях, когда мощность множества допустимых решений сравнительно невелика. В интересных с практической точки зрения задачах, как правило, мощность множества допустимых решений быстро ( например, экспоненциально) растет с увеличением размерности ( объема исходных данных ) задачи. Это приводит к тому, что в задачах реальной размерности количество допустимых решений становится величиной астрономического порядка, что делает перебор практически невозможным ни в настоящем времени, ни в обозримом будущем. Назначение теории дискретных задач размещения - создание работоспособных в практическом смысле алгоритмических инструментов решения задач. К сожалению, почти все естественные и интересные постановки задач размещения оказываются ]УР-трудными, поэтому попытки построения точных и эффективных ( быстрых ) алгоритмов для этих задач вероятней всего обречены на неудачу. В силу этого для дискретных задач размещения, как и для других УУР-трудных задач дискретной оптимизации, молено выделить следующие основные направления исследований:

- выделение эффективно решаемых подзадач и построение для них точных эффективых алгоритмов с рекордными оценками трудоемкости;

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

- построение эффективных приближенных алгоритмов с априорными оценками точности.

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

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

Приведем математические формулировки этих задач и дадим краткие обзоры основных известных результатов их исследования.

Пусть имеются конечные множества I = {1,.,ш} и .1 = {1,. . , п}, первое из которых задает множество возможных пунктов размещения предприятий для выпуска некоторого однородного продукта, а второе - множество потребителей этого продукта. В некоторых задачах множества I ж 3 могут совпадать. Пусть, кроме того, заданы величины сг-, г £ /, определяющие начальные затраты на размещение предприятия в пункте г и величины г £/,.?£ равные затратам на доставку продукта от предприятия, размещенного в пункте г, до потребителя Требуется выбрать из множества возможных пунктов размещения предприятий подмножество пунктов 5, в которых следует разместить предприятия, таким образом, чтобы сумма начальных затрат плюс сумма наименьших затрат на доставку продукта каждому потребителю была минимальной. Формально простейшая задача размещения (ПЗР) в комбинаторной постановке записывается следующим образом:

Наряду с комбинаторной постановкой часто рассматривается постановка ПЗР в виде задачи линейного целочисленного программирования:

Хц х^ ъ I) ] £ ^

Хц,Х1 £ {0,1}, г £/,;£/.

Используемые в этой задаче переменные имеют следующий смысл: Х{ — 1, если в пункте г размещается предприятие, жг- = 0, в противном

Ш г'е/

X/ - ^ 5 3£ случае; х^ = 1, если пункт потребления ] обслуживается предприятием, размещенном в пункте г, и х^ — 0, в противном случае.

Как уже отмечалось ПЗР является достаточно хорошо изученной задачей. Она относится к числу ТУР-трудных задач поскольку содержит в себе задачу о покрытии конечного множества системой конечных подмножеств. Исследования этой задачи велись по разным направлениям по каждому из которых были достигнуты значительные успехи. Так в работах Береснева [8], Береснева, Гимади, Деменьтева [11] и Ег1епкоиег [66] описаны алгоритмы решения ПЗР с помощью алгоритмов неявного перебора. Эти методы основаны на применении известной схемы метода ветвей и границ.

Целый ряд результатов связан с рассмотрением частных случаев задачи. Было обнаружено, что если матрица (с^) удовлетворяет различным специфическим требованиям, то ПЗР полиномиально разрешима. Известно, что ПЗР принадлежит классу Р если матрица односвязна (Береснев, Гимади, Дементьев[11]), двусвязна (Береснев [9]), квазивы-пукла или обобщенно-квазивыпукла (Гимади [20]). В работе Трубина [30] приводится полиномиальный алгоритм для ПЗР на дереве, с трудоемкостью 0(ш3) (см. также [31]). Гимади [16] предложил алгоритм с существенно лучшей трудоемкостью 0(т2). Агеев [34] установил, что для очень широкого класса задач (с матрицами порожденными частичными д-деревьями) существует полиномиальный алгоритм с трудоемкостью 0{пт<1+1). ПЗР и ее обобщения также изучались в работах [2, 10, 21, 15, 17, 19, 25, 18, 5, 6, 7, 14, 22, 26, 33] как с точки зрения полиномиально разрешимых подклассов так и с точки зрения других видов анализа NP-тpyдныx задач (см. также обзор по полиномиально разрешимым подклассам для ПЗР [27]). Кроме того, Береснев [9] установил эквивалентность ПЗР и задачи минимизации булевых полиномов, что позволило выделить новые классы эффективно решаемых задач [9, 2, 4, 3]. В работе [35] Агеевым был получен отрицательный результат: ПЗР оказалась МР-трудной, даже если матрица (сг;) порождена расстояниями на плоской решетке.

Близкой к ПЗР является так называемая простейшая задача размещения на максимум (ПЗРМ), которая в комбинаторной постановке записывается следующим образом:

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

Задачи ПЗР и ПЗРМ эквивалентны в том смысле, что любой точный алгоритм одной задачи применим и к другой. Однако с точки зрения приближенных алгоритмов эти задачи отличаются. Историческая справка и обзор по ПЗР и ПЗРМ могут быть найдены в [62].

Другой классической задачей размещения является задача о р-медиане комбинаторная формулировка которой имеет следующий вид:

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

Задача о р-медиане также как и ПЗР может быть записана в виде задачи линейного целочисленного программирования

И/ = 1? ] ^ -1 ч Ш г? ^ ^ I ч 3 £ J'•>

Е <

6/ е {о, 1}, I

Капу и НаЫгш [96] показали, что задача о р-медиане является ЛТР-трудной. В этой же работе показано, что если матрица (с^) есть матрица кратчайших расстояний на дереве, то задача полиномиально разрешима. В обзоре [110] можно найти список основных результатов для этой задачи.

Задача о р-медиане может рассматриваться и как задача на максимум. Комбинаторная формулировка такой задачи имеет вид

Эта задача эквивалентна задаче о р-медиане с точки зрения нахождения точного решения, но так же как и в случае ПЗР, постановки задач о р-медиане отличаются с точки зрения нахождения приближенных решений.

Третьей рассматриваемой в работе задачей является задача о р-центре. Комбинаторная формулировка этой задачи выглядит следующим образом:

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

Задача о р-центре ]УР-трудна [93]. Это следует из того, что известная задача о доминирующем множестве может быть сведена к задаче о р-центре. Эффективный алгоритм для задачи о р-центре существует ( см. [56] ) при тех же самых предположениях, что и для задачи о р-медиане, когда матрица (с^) есть матрица кратчайших расстояний на дереве. Исторические сведения, а также перечень результатов для задачи о р-центре приводится в обзорах [83], [129].

Одной из наиболее трудных для исследований задач размещения является квадратичная задача о назначении (КЗН). В виде задачи целочисленного программирования она записывается следующим обрашш < шах тш с 5с/ зом: min ЕЕ I Е Е dpqVjg Угр, ieipeJ \jei q<EJ /

E yip = 1i « e i, peJ

V € «7, iEl

Vip£{ 0,1}, iel,p£j.

Содержательно КЗН можно проинтерпретировать следующим образом. Пусть J = {1,., п} - множество возможных пунктов размеще-яия предприятий, а I = {1,. , т] (т < п) - множество размещаемых предприятий. Пусть величины dpq, р, q Е J, задают расстояние между пунктами р и д, а величины Wij i,j Е I, являются удельными ( на единицу расстояния ) затратами на перевозку грузов между предприятиями г и j. Определим переменные yip, г Е I,p Е J следующим образом:

1 если предприятие i размещается в пункте р, 0 иначе.

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

КЗН относится к числу iVP-трудных задач, так как задача коммивояжера и задача о максимальной клике являются частыми случаями КЗН [54]. Несмотря на то, что КЗН является одной из самых изученных задач комбинаторной оптимизации (см. обзор [54] и обзор по

Hip полиномиально разрешимым подклассам [55]) точные решения удается получить для задач размерности не более 30 х 30.

Как уже отмечалось выше интересующие нас задачи являются ЫР-трудными. Это означает, что построение точных эффективных (полиномиальных) алгоритмов скорее всего невозможно (подробную дискуссию по теории Л^Р-полноты см. в [28]). Одним из основных направлений исследования таких задач является построение приближенных эфективных алгоритмов с априорными оценками их точности. Такие алгоритмы не для всякой индивидуальной задачи находят точное решение, но всегда отыскивают допустимое решение задачи, которое удовлетворяет некоторым требованиям по точности, установленными еще до получения приближенного решения.

Идея построения приближенного алгоритма настолько естественна, что невозможно проследить, кто первым ее придумал и стал использовать. Считается, что первый приближенный алгоритм и его анализ был дан в очень известной работе [80] по теории расписаний. Другими фундаментальными работами в этой области являются работы [94, 23], в которых вводятся понятия приближенного алгоритма и его точности в худшем случае.

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

Существуют также и другие интересные подходы к вероятностной оценке точности алгоритма. Среди таких подходов следует выделить подход Перепелицы и Гимади [29]. В этой работе анализируется алгоритм " иди в ближайший еще не пройденный город" для задачи коммивояжера на различных вероятностных распределениях входных данных.

Настоящая работа посвящена построению приближенных алгоритмов для задач размещения и анализу их точности в худшем случае. Напомним определения основных понятий, используемых при таком анализе. Пусть имеется оптимизационная задача и приближенный алгоритм А для ее решения. Обозначим через / индивидуальную оптимизационную задачу, Р(1) значение целевой функции на приближенном решении, полученном алгоритмом, а через .Р*(/) значение целевой функции на оптимальном решении. Существует несколько способов измерения точности приближенного алгоритма. Наиболее распространенной и используемой величиной, характеризующей точность приближенного алгоритма, является так называемая относительная точность, под которой понимается функция тд(1) = Оценкой (априорной) относительной точности приближенного алгоритма А решения оптимизационной задачи на максимум (минимум) является величина КА такая, что для любой индивидуальной задачи I выполняется неравенство тА{1)>ЯА (тА(1)<ПА).

Такую оценку IIА, не зависящую от размерности индивидуальной задачи /, называют константной.

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

В конце семидесятых годов вышло много важных работ по приближенным алгоритмам и, как следствие этого, появилось несколько обзоров [72, 122, 123, 13] в которых суммируются результаты, полученные за эти годы. Затем наступило затишье и на протяжении более десяти лет количество опубликованных статей по приближенным алгоритмам было невелико. С конца восьмидесятых годов произошел взрыв популярности исследований в области приближенных алгоритмов. Очень важным открытием стало понимание того, что для получения оценок значений целевых функций исследуемых задач можно использовать различные полиномиально разрешимые релаксации этих задач. Первыми, кто использовал линейное програмирование при построении и анализе приближенных алгоритмов с относительной оценкой точности были Кл^Ьауап, Тотрэоп [120], а после работы [77] использование линейного програмирования стало основным методом построения приближенных алгоритмов. Одним из основных методов используемых в диссертации является метод округления линейных релаксаций. Суть метода заключается в следующем. Предположим, что исследуемую оптимизационную задачу можно сформулировать как задачу линейного булевого программирования. Рассмотрим линейную релаксацию этой задачу, получаемую заменой булевых переменных на непрерывные переменные из отрезка [0,1]. Эта задача является задачей линейного программирования, которая как известно полиномиально разрешима [32]. Понятно, что оптимальное значение целевой функции ре-лаксированной задачи является верхней оценкой (для задачи на максимум) оптимального значения целевой функции исходной задачи. В результате округления оптимального решения релаксированной задачи можно получить приближенное решение исходной задачи, а воспользовавшись верхней оценкой отимального значения ее целевой функции получить и оценку точности построенного приближенного решения. Важнейшей составной частью этого подхода является алгоритм округления оптимального решения релаксированной задачи. Существует широкий спектр техник, которые могут применятся при округлении. Особенно известной стала техника вероятностного округления [120]. В диссертационной работе используются некоторые из известных техник округления, в частности, вероятностное округление. Также предлагается новый метод округления для задач с ограничением на мощность.

В начале 90-х произошел другой прорыв в понимании приближенных алгоритмов, обусловленный появлением теоретических основ для доказательства отрицательных результатов. Бурное развитие в этой области было инициировано двумя работами [70, 117]. В первой работе впервые был получен отрицательный результат для задачи о клике, и предложена техника, которая в дальнейшем усовершенствовалась и оттачивалась в целом ряде работ. Во второй работе предложено синтаксическое определение некоторого класса сложности, который назвали MAXSNP, и введено понятие L-сводимости. Оказалось, что почти все естественные задачи комбинаторной оптимизации лежат в этом классе и многие из них оказались полными в этом классе относительно L-сводимости. Papadimitrou и Yannakakis предположили, что для задач полных в классе MAXSNP не существует аппроксимационной схемы. Эта гипотеза была доказана в работе [46] при условии, что Р ф. NP. Хорошими введениями в эту бурно развивающуюся область являются диссертация Агога [38] и обзор Агога и Lund [45], а также обзоры [126, 87] о последних достижениях в области приближенных алгоритмов.

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

Как уже отмечалось, настоящая диссертация посвящена построению и анализу приближенных алгоритмов для дискретных задач размещения. В первой главе рассматривается простейшая задача размещения на максимум. Для этой задачи строится приближенный алгоритм с оценкой точности 2(д/2 — 1) ~ 0.828, что лучше оценки точности жадного алгоритм [61]. Основу предложенного алгоритма составляет процедура вероятностного округления оптимального решения линейной релаксации задачи. Показано, что в случае использования такой релаксации, полученная оценка не может быть улучшена. Кроме того, доказано, что для простейшей задачи размещения на максимум не существует аппроксимационной схемы при условии, что Р ф МР.

Вторая глава посвящена исследованию обобщений задачи о р-медиане на максимум. Рассматривается обобщенная задача о р-медиане с двумя видами ограничений: с обычным мощностным ограничением |5| < рис более общим ограничением "ранцевого"вида < О. Целевая функция задачи определяется как оптимальное значение целевой функции некоторой оптимизационной задачи. Эта оптимизационная задача является более общей, чем, например, рассмотренная в [132], и имеет к дополнительных ресурсных ограничений. Для обеих задач о р-медиане (с двумя видами ограничений) получены оценки точности жадных алгоритмов. При к = 0 эти оценки совпадают с оценками из [61, 132]. В этой главе рассматривается также еще одно обобщение задачи о р-медиане на максимум так называемая динамическая задача о р-медиане. Динамическая задача описывает ситуацию, когда размещение предприятий производится в течение некоторого периода времени, состоящего из нескольких единичных отрезков (лет). Требуется в каждом году разместить ограниченное число предприятий так, чтобы максимизировать суммарную прибыль за весь рассматриваемый период времени. Для этой задачи предлагается приближенный алгоритм с оценкой точности (1 — е-1). При построении алгоритма используется техника вероятностного округления решения линейной релаксации задачи.

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

В четвертой главе исследуется задача выполнимости на максимум с мощностным ограничением. Для этой задачи предлагается алгоритм с оценкой точности равной 1-е-1. Алгоритм построен с использованием техники вероятностного округления решения линейной релаксации. Полученная оценка является неулучшаемой при условии, что Р ф NP [68].

В пятой главе рассматривается квадратичная задача о назначениях. Для этой задачи дается положительный ответ на поставленный в [118] вопрос о существовании приближенного алгоритма с константной оценкой точности для частного случая задачи, когда матрица (dpq) удовлетворяет неравенству треугольника, а все элементы матрицы равны единице. Для указанного частного случая задачи построен алгоритм с оценкой точности равной 2.

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

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

Основные результаты диссертации опубликованы и докладывались на 2-ом Сибирском конгрессе по индустриальной и прикладной математике (Новосибирск, 1996), Международной конференции " Проблемы оптимизации и экономические приложения" (Омск, 1997), 16-ом Симпозиуме по математическому программированию (Лозанна, Швейцария, 1997), Сибирской коференции по исследованию операций (Ново

Заключение

Сформулируем основные результаты проведенных исследований.

1. Для простейшей задачи размещения на максимум построен полиномиальный приближенный алгоритм с оценкой точности равной 2(у/2 — 1). Доказано, что для этой задачи не существует полиномиальной аппроксимационной схемы при условии, что Р ф NP.

2. Изучены различные обобщения задачи о р-медиане на максимум. Для задачи о р-медиане на максимум с дополнительными ресурсными ограничениями получена константная оценка точности жадного алгоритма. Для динамической задачи о р-медиане на максимум построен приближенный алгоритм с оценкой точности, совпадающей с неулуч-шаемой оценкой точности жадного алгоритма для задачи о р-медиане.

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

1. А. А. Агеев, О сложности задач минимизации полиномов от булевых переменных, Управляемые системы 23 (1983), стр.3-11.

2. А. А. Агеев, Полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сети, Управляемые системы 30 (1990), стр.3-16.

3. А. А. Агеев, В. Л. Береснев, Алгоритмы минимизации для некоторых классов полиномов от булевых переменных, Модели и методы оптимизации, Труды ИМ СО РАН 10 (1988), стр.5-17.

4. И. Г. Белинская, Об одном классе полиномов от булевых переменных, Управляемые системы 21 (1981), стр.6-12.

5. В. Л. Береснев, Об одном классе задач оптимизации параметров однородной технической системы, Управляемые системы 9 (1971), стр.65-74.

6. В. Л. Береснев, Об одной задаче математической теории стандартизации, Управляемые системы 11 (1973), стр.43-54.

7. В. Л. Береснев, Об одной задаче математической теории стандартизации, Управляемые системы 13 (1974), стр.3-9.

8. В. Л. Береснев, Алгоритм неявного перебора для задачи типа размещения и стандартизации, Управляемые системы 12 (1974), стр.24-34.

9. В. Л. Береснев, Алгоритмы минимизации полиномов от булевых переменных, Проблемы кибернетики 36 (1979), стр.225-246.

10. В. Л. Береснев, Эффективный алгоритм для задачи размещения производства с вполне уравновешенной матрицей, Дискретный анализ и исследование операций 5(1) серия 1 (1998), стр.20-31.

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

12. М. М. Беркович, Задачи стандартизации и некоторые методы их решения, Экономика и математические методы 5(2) (1969), стр.285-289.

13. Г. В. Гене, Е. В. Левнер, Приближенные алгоритмы для некоторых универсальных задач теории расписаний, Известия АН СССР, Техническая кибернетика 6 (1978), стр.38-43.

14. Э. X. Гимадутдинов, О свойствах решений одной задачи оптимального размещения точек на отрезке, Управляемые системы 2 (1969), стр.77-91.111

15. Э. X. Гимади, Выбор оптимальных шкал в одном классе задач типа размещения, унификации и стандартизации, Управляемые системы 6 (1970), стр.57-70.

16. Э. X. Гимади, Эффективный алгоритм решения задачи размещения с областями обслуживания связными относительно ациклической сети, Управлямые системы 23 (1983), стр. 12-23.

17. Э. X. Гимади, Задача размещения на цепи с центрально-связными областями обслуживания, Управлямые системы 25 (1984), стр.3847.

18. Э. X. Гимади, Обоснование априорных оценок качества приближенного решения задачи стандартизации, Управляемые системы 27 (1987), стр.3-11.

19. Э. X. Гимади, О некоторых математических моделях и методах планирования крупномасшабных проектов, Модели и Методы Оптимизации, Труды ИМ СО АН СССР 10 (1988), стр.89-115.

20. Э. X. Гимади, Задача стандартизации с данными произвольного знака и связными, квазивыпуклыми и почти квазивыпуклыми матрицами, Управляемые системы 30 (1990), стр.12-23.

21. Э. X. Гимади, Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи, Дискретный анализ и исследование операций 2(4) (1995), стр.13-31.112

22. Э. X. Гимади, Н. И. Глебов, В. Т. Дементьев, Об одном методе построения нижней оценки и приближенного решения с апостериорной оценкой точности для задачи стандартизации, Управляемые системы 13 (1974), стр.26-31.

23. Э. X. Гимади, Н. И. Глебов, В. А. Перепелица, Алгоритмы с оценками для задач дискретной оптимизации, Проблемы кибернетики 31 (1975), стр.35-42.

24. Э. X. Гимади, В. Т. Дементьев, О методах решения некоторых задач оптимизации параметрических рядов, Стандарты и качество 12 (1971), стр.10-12.

25. Э. X. Гимади, В. Т. Дементьев, Некоторые задачи выбора оптимальных параметрических рядов и методы их решения (задачи стандартизации), Проблемы кибернетики 27 (1973), стр.19-32.

26. В. Т. Дементьев, Задача выбора типажа оборудования, Методы управления большими системами, (1970), стр.60-62, Иркутск: СЭИ СО АН СССР.

27. В. П. Гришухин, Полиномиальность в простейшей задаче размещения, препринт ЦЭМИ.

28. М. Гэри, Д. Джонсон, Вычислительные машины и труднорешае-мые задачи, Москва, Мир, 1979.

29. В. А. Перепелица, Э. X. Гимади, К задаче нахождения минимального гамильтонова контура на графе со взвешенными дугами, Дискретный анализ 15 (1969), стр.57-65.

30. В. А. Трубин, Эффективный алгоритм размещения на сети в форме дерева, Доклады АН СССР 231(3) (1976), стр.547-550.

31. В. А. Трубин, Два класса задач размещения на древовидных сетях, Кибернетика 4 (1983), стр.84-87.

32. JI. Г. Хачиян, Полиномиальный алгоритм в линейном програми-ровании, Доклады АН СССР т.244 (1979), стр.1093-1096.

33. В. П. Черенин, В. Р. Хачатуров, Решение методом последовательных расчетов одного класса задач о размещении производства, Экономика и математические методы 2 (1965), стр.279-290.

34. A. A. Ageev, A Criterion of Polynomial-Time Solvability for the Network Location Problem, Integer Programming and Combinatorial Optimization (1992), Carnegie-Mellon University, pp.237-245.

35. A. A. Ageev, Complexity of the Network Median Problem on Planar Grids, Siberian Advances in Mathematics 5 (1995), pp.1-9.

36. S. Ahn, C. Cooper, G. Cornuejols and A. M. Frieze, Probabilistic Analysis of a Relaxation for the /¿-Median Problem, Mathematics of Operation Research 13 (1988), pp.1-31.

37. N. Alon and J. N. Spencer, The Probabilistic Method, John Wiley and Sons, 1992.

38. S. Arora, Probabilistic Checking of Proofs and the Hardness of Approximation Problems, PhD thesis, U.C. Berkeley, 1994.

39. S. Arora, Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems, In Proceedings of the 37th IEEE FOCS (1996), pp.2-11.

40. S. Arora, Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems, In Proceedings of the 38th IEEE FOCS (1997), pp.554-563.

41. S. Arora, A. M. Frieze and H. Kaplan, A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems, In Proceedings of the 37th IEEE FOCS (1996),

42. S. Arora, D. Karger and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of A^P-Hard Problems, In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (1995), pp.21-30.

43. S. Arora, M. Grigni, D. Karger, P. Klein and A. Woloszyn, Polynomial Time Approximation Scheme for Weighted Planar Graph TSP, In Proceedings of the SODA97.

44. S. Arora, P. Raghavan and S. Rao, Approximation Schemes for Euclidean fc-medians and related problems, In Proceedings of the 30th STOC (1998).

45. S. Arora and C. Lund, Hardness of Approximation, in the book "Approximation Algorithms for NP-hard Problems", PWS Publishing (1996).

46. S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof Verification and Intractability of Approximation Problems, In Proceedings of the 33rd IEEE Symp. on Foundations of Computer Science (1992), pp.13-22.

47. T. Asano, Approximation Algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson, In Proceedings of the 5nd Israel Symposium on Theory and Computing Systems (1997), pp.182-189.

48. Y. Bartal, Probabilistic Approximation of Metric Spaces and Its Algorithmc Applications, In Proceedings of the 37th IEE FOCS (1996), pp.184-193.

49. Y. Bartal, On Approximating Arbitrary Metric by Tree Metric, In Proceedings of the 30th STOC (1998).

50. B. S. Baker, Approximation algorithms for A^P-complete problems on planar graphs, Jouranl of ACM 41(1),1994, Preliminary version in Proceedings of the 24th Annual Symposium on Foundations of Computer Science (1983), pp.265-273.

51. J. Bar-Ilan, G. Kortsarz and D. Peleg, How to Allocate Network Centers, Journal of Algorithms 15 (1993), pp.385-415.

52. R. Bar-Yehuda, One for the Price of Two: a Unified Approach for Approximating Covering Problems, In Proceedings of APPROX98.

53. R. Bhatia, S. Guha, S. Khuller and Y. J. Sussman, Facility Location with Dynamic Distance Function, In Proceeding of 6th Scandinavian Workshop on Algorithmic Theory (SWAT) (1998).

54. R. E. Burkard, E. Cela, P. M. Pardalos and L.S. Pitsoulis, Quadratic Assignment Problem, technical report of Graz University of Technology, SFB-Report 126, (1998).

55. R. E. Burkard, E. Cela, V. Demidenko, N. Metelski and G. J. Woeginger, Perpespectives of Easy and Hard Cases of Quadratic Assignment Problem, technical report of Graz University of Technology, SFB-Report 104, (1997).

56. R. Chandrasekaran and A. Tamir, A Polynomially Bounded Algorithms for Locating p-Centers on a Tree, Mathematical Programming 22 (1982), pp.304-315.

57. M. Charikar, C. Chekuri, A. Goel and S. Guha, Rounding via Trees: Determenistic Approximation Algorithms for Group Steiner Trees and fc-Median, In Proceedings of 30th STOC.

58. V. Chvatal, A Greedy Heuristic for the Set Covering Problem, Mathematics of Operation Research 4 (1979), pp.233-235.

59. F. Chudak and D. Shmoys, Improved Approximation Algorithm for Uncapacitated Facility Location, unpublished manuscript.

60. M. Conforti and G. Cornuejols, Submodular Set Function, Matroids and the Greedy Algorithm: Worst-Case Bounds and Some Generalizations of the Rado-Edmonds Theorem, Discrete Applied Mathematics 7 (1984), pp.251-274.

61. G. Cornuejols, M. L. Fisher and G. L. Nemhauser, Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms, Management Science 22 (1977), pp.789810.

62. G. Cornuejols, G. L. Nemhauser and L. A. Wolsey The Uncapacitated Facility Location Problem, In book edited by P. B. Mirchandani and R. L. Francis, Wiley&Sons, 1990.

63. G. Cornuejols, G. L. Nemhauser and L. A. Wolsey Worst Case and Probalistic Analysis of Algorithms for Location Problems, Operation Research 28 (1980), pp.847-858.

64. M. E. Dyer, An 0(n) Algorithm for the Multiple Choice Knapsack Problem, Mathematical Programming 29 (1984), pp.57-63.

65. M. E. Dyer and A. M. Frieze, A Simple Heuristic for the p-Center Problem, Operation Research Letters 3 (1985), pp.285-288.

66. D. Erlenkotter, A Dual-Based Approach for Uncapacitated Facility Location, Operation Research 26 (1978), pp.992-1009.

67. T. Feder and D. H. Green, Optimal Algorithms for Approximate Clustering, In Proceedings of 20th ACM Symp. on Theory of Computing (1988), pp.434-444.

68. U. Feige, A Threshold of In n for Approximating Set Cover, Journal of ACM (to appear).

69. U. Feige and M. Goemans, Approximating the Value of Two-prover Proof Systems, with Applications to MAX 2-SAT and MAX-DICUT. In Proceedings of the 3nd Israel Symposium on Theory and Computing Systems (1995), pp.182-189.

70. U. Feige, S. Goldwasser, L. Lovasz, S. Safra and M. Szegedy, Approximating Clique is Almost A^P-Complete, In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (1991), pp.2-12.

71. W. Feller, An Introduction to Probability Theory and Its Applications, John Wiley h Sons New York, 1968.

72. M. L. Fisher, Worst-Case Analysis of Algorithms, Management Science 26 (1980), pp.1-18.

73. M. L. Fisher and D. Hochbaum, Probabilistic Analysis of the Planar A'-Median Problem, Mathematics of Operation Research 5 (1980), pp. 27-34.

74. M. L. Fisher , G. L. Nemhauser and L. A. Wolsey, An Analysis of Approximations for Maximizing Submodular Set Functions-II, Mathematical Programming Study 8 (1978), pp.73-88.

75. A. Frieze and M. Jerrum, Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION, Algorithmica 18 (1997), pp.6781.

76. A. Frieze and R. Kannan, The Regularity Lemma and Approximation Schemes for Dense Problems, In Proceedings of the 37th IEEE FOCS (1996), pp.12-30.

77. M. Goemans and D. Williamson, New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics 7 (1994), pp.656-666.

78. M. Goemans and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Journal of ACM 42 (1995), pp.1115-1145.

79. M. Goemans and D. Williamson, The Primal-dual Method for Approximation Algorithms and Its Application to Network Design Problems, in the book "Approximation algorithms for NP-hard problems", PWS Publishing, (1996).

80. R. L. Graham, Bounds for Certain Multiprocessing Anomalies, Bell System Technical Journal 45 (1966), pp.1563-1581.

81. M. Grigni, E. Koutsoupias and C. Papadimitron, An Approximation Scheme for Planar Graph TSP, In Proceedings of 36th FOCS (1995), pp.640-645.

82. S. Guha and S. Khuller, Greedy Strikes Back: Improved Facility Location Algorithms, In Proceedings of the 9th SODA (1998).

83. G. Y. Handler, p-Center Problems, in the book "Discrete Location Theory", edited by P. B. Mirchandani and R. L. Francis (1990).

84. J. Hastad, Some Optimal Inapproximability Results, In Proceedings of the 28 Annual ACM Symp. on Theory of Computing (1996), pp.l-10.

85. D. S. Hochbaum, Heuristics for the Fixed Cost Median Problems, Mathematical Programing 22 (1982), pp.148-162.

86. D. S. Hochbaum, Approximation Algorithms for the Set Covering and Vertex Cover Problems, SIAM Journal of Computing 11 (1982), pp.555-556.

87. D. S. Hochbaum, editor, Approximation Algorithms for A^P-Hard Problems, PWS Publishing (1996).

88. D. S. Hochbaum, Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems, in the book "Approximation algorithms for NP-hard problems", edited by D. S. Hochbaum, PWS Publishing Company, 1996.

89. D. S. Hochbaum and A. Pathria, Generalized p-Center Problems: Complexity Results and Approximation Algorithms, European Journal of Operational Research 100 (1997), pp.594-607.

90. D. S. Hochbaum and A. Pathria, Locating Centers in Dynamically Changing Network and Related Problems, to appear in Location Science.

91. D. S. Hochbaum and D. B. Shmoys, A Best Possible Heuristic for the Ar-center Problem, Mathematics of Operation Research 10 (1985), pp.180-184.

92. D. S. Hochbaum and D. B. Shmoys, A Unified Approach to Approximation Algorithms for Bottleneck Problems, Journal of ACM, 33 (1986), pp.533-550.

93. W. L. Hsu and G. L. Nemhauser, Easy and Hard Bottleneck Location Problems, Discrete Applied Mathematics 1 (1979), pp.209-216.

94. D. S. Johnson, Approximation Algorithms for Combinatorial Problems, Journal Comput. System Sei. 9 (1974), pp.256-278.

95. D. S. Johnson and M. S. Trick, editors, Cliques, Colorings and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26.

96. O. Kariv and S. L. Hakimi, An Algorithmic Approach to Network Location Problems. II. The p-Medians., SIAM Journal of Applied Mathematics 37 (1979), pp.539-560.

97. H. Karloff and U. Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, In Proceedings of the 38th FOCS (1997), pp.406-415.

98. N. Karmarkar, A New Polinomial-Time Algorithm for Linear Programming, Combinatorica 4 (1984), pp.373-395.

99. S. Khanna, V. Kann, J. Lagergren and A. Panconesi, On the Hardness of Approximating MAX k-CUT and Its Dual, Chicago Journal of Theoretical Computer Science 2 (1997).

100. S. Khanna, R. Motwani and M. Sudan, Towards Syntactic Characterization of PTAS, In Proceedings of the 28th Annual ACM Symp. on Theory of Computing (1996), pp.329-337.

101. S. Khanna, M. Sudan and D. Williamson, A Complete Classification of the Approximability of Maximization problems Derived from Boolean Constraint Satisfaction, In Proceedings of the 29th STOC, (1997), pp.11-20.

102. S. Khuller, A. Moss and J. Naor, The Budgeted Maximum Coverage Problem, submitted for publication.

103. S. Khuller, R. Pless and Y. J. Sussman, Fault Tolerant K-center Problems, In Proceedings of the 3rd Italian Conference on Algorithms and Complexity (1997), LNCS 1203, pp.37-48.

104. S. Khuller and Y. J. Sussman, Capacitated K-center Problems, In Proceedings of 4th Annual Europeap Symposium on Algorithms (ESA) (1996), LNCS 1136, pp.152-166.

105. T. Leighton and S. Rao, An Approximate Max-flow Mincut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms, In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (1988), pp.422-431.

106. J. H, Lin and J. S. Vitter, ^-Approximation with Minimum Packing Constraint Violation, In Proceedings of the 24th STOC (1992), pp.771-782.

107. J. H. Lin and J. S. Vitter, Approximation Algorithms for Geometric Median Problems, Information Processing Letters 44 (1992), pp.245249.

108. L. Lovasz, On the Shannon Capacity of a Graph, IEEE Trans, of Information Theory 25(1) (1979), pp.1-7.

109. C. Lund and M. Yannakakis, On the Hardness of Approximating Minimization Problems, Journal of the ACM 41 (1994), pp.960-981.

110. P. B. Mirchandani, The p-Median Problem and Generalizations, in the book "Discrete Location Theory", edited by P. B. Mirchandani and R. L. Francis (1990).

111. R. Motwani , J. Naor and P. Raghavan , Randomized Algorithms in Combinatorial Optimization, in the book "Approximation algorithms for NP-hard problems", PWS Publishing Company, 1996.

112. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press (1995).

113. G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.

114. G.L.Nemhauser and L.A.Wolsey, Best Algorithms for Approximating the Maximum of a Submodular Function, Mathematics of Operation Research 3 (1978), pp. 177-188.

115. G. L. Nemhauser, L. A. Wolsey and M. L. Fisher, An Analysis of Approximations for Maximizing Submodular Set Functions-I, Mathematical Programming 14 (1978), pp.265-294.

116. C. Papadimitrou, Worst-Case and Probabilistic Analysis of a Geometric Location Problem, SIAM Journal of Computing 10 (1981), pp.542-557.

117. C. Papadimitrou and M. Yannakakis, Optimization, Approximation and Complexity Classes, Journal of Computer and System Sciences 43 (1991), pp.425-440.

118. M. Queyranne, Performance Ratio of Polynomial Heuristics for Triangle Inequality Quadratic Assignment Problems, Operation Research Letters 4 (1986), pp. 231-234.119.

119. P.Raghavan, Probabilistic Construction of Determenistic Algorithms:

120. Approximating Packing Integer Programs, Journal of Computer and System Sciences 37 (1988), pp.130-143.

121. P. Raghavan and C. Thompson, Randomized Rounding: a Technique for Provably Good Algorithms and Algorithmic Proofs, Combinatorica 7 (1987), pp.365-374.

122. R. Raz, A Parallel Repetition Theorem, Journal of ACM (to appear).

123. A. H. G. Rinnoy Kan, An Introduction to the Analysis of Aproximation Algorithms, Discrete Applied A^athematics 14 (1986), pp.171-186.

124. S. Sahni, General Technique for Combinatorial Approximation, Operation Research 25 (1977), pp.920-936.

125. S Sahni and T. Gonzalez, P-Complete Approximation Problems, Journal of ACM 23 (1976), pp.555-565.

126. D. Shmoys, Cut Problems and Their Application to Divide-and-Conquer, in the "Approximation Algorithms for NP-hard problems", PWS Publishing (1996).

127. D. Shmoys, Computing Near-Optimal Solutions to Combinatorial Optimization Problems, In W. Cook, L. Lovasz, P. Seymour, editors, Advances in Combinatorial Optimization, AMS, Providence RI (1995), pp.355-397.

128. D. Shmoys, E. Tardos and K. Aardal, Approximation Algorithms for Facility Location Problems, In Proceedings of the 29 Annual ACM Symp. on Theory of Computing (1997).

129. P. Slavik, A Tight Analysis of the Greedy Algorithm for Set Cover, In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996), pp.435-439.

130. B. C. Tansel, R. L. Francis and T. J. Lowe, Duality: Covering and Constraining p-Center Problems on Trees, in the book "Discrete Location Theory", edited by P. B. Mirchandani and R. L. Francis (1990).

131. S. Vishwanathan, An O(log*n) Approximation Algorithm for the Assymetric p-Center Problem, In Proceedings of the 7th SODA (1996). pp.1-5.

132. L. A. Wolsey, An Analysis of the Greedy Algorithm for the Submodular Set Covering Problems, Mathematics of Operation Research 7 (1982), pp.417-425.

133. L. A. Wolsey, Maximizing Real-valued Submodular Functions: Primal and Dual Heuristics for Location Problems, Mathematics of Operation Research 7 (1982), pp.410-425.

134. M.Yannakakis, On the Approximation of Maximum Satisfiability, Journal of Algorithms 17 (1994), pp.475-502.

135. Список публикаций автора по теме диссертации

136. М. И. Свириденко, О точности решений жадными алгоритмами задач размещения на максимум, Дискретный анализ и Исследование операций 4(3) серия 1 (1997), стр.35-48.

137. М. И. Свириденко, Приближенный алгоритм для решения динамической задачи о р-медиане на максимум, Дискретный анализ и Исследование операций 4(2) серия 2 (1997), стр.55-62.

138. А. А. Агеев и М. И. Свириденко, Приближенный алгоритм с априорной оценкой точности для простейшей задачи размещения на максимум, Тезисы конференции "Приблемы оптимизации и экономические приложения", Омск 1997.

139. М. И. Свириденко, Приближенный алгоритм для решения задачи о р-центре с неравенством треугольника, Дискретный анализ и Исследование операций 5(1) серия 1 (1998), стр.60-63.

140. A. A. Ageev and М. I. Sviridenko, An Approximation Algorithm for the Uncapacitated Facility Location Problem, в тезисах 16-го международного симпозиума по математическому программированию, Лозанна1997.

141. A. A. Ageev and М. I. Sviridenko, An Approximation Algorithm for the Uncapacitated Facility Location Problem, в тезисах симпозиума по исследованию операций, Иенна 1997.

142. A.A. Ageev and М. I. Sviridenko, An Approximation Algorithms for Some Combinatorial Problems with Cardinality Constraints, В трудах 11-й Байкальской школы-семинара Методы оптимизации и их приложения т.1 (1998), стр.107-110.

143. М. I. Sviridenko, Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint, In Proceedings APPROX98, Lecture Notes in Computer Science v.1444, pp.193-199.