Реоптимизация упорядоченных обобщенных задач о выполнимости

При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автор:	Михайлюк, В.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207498
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Реоптимизация упорядоченных обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 3. — С. 56–65. — Бібліогр.: 16 назв. - рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207498
record_format	dspace
spelling	irk-123456789-2074982025-10-09T00:06:04Z Реоптимизация упорядоченных обобщенных задач о выполнимости Реоптимізація впорядкованих узагальнених задач про виконуваність Reoptimization of Ordered Generalized Satisfaction Problems Михайлюк, В.А. Оптимальное управление и методы оптимизации При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’язання задачі OCSP. Assume that Unique Games Conjecture (UGC) holds. Then for solving Ins-OCSP (reoptimization of OCSP under insertion of one constraint) polynomial optimal (threshold) approximated algorithm exists. The approximation ratio of this algorithm depends on threshold «random» approximation ratio for solving OCSP problem. 2012 Article Реоптимизация упорядоченных обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 3. — С. 56–65. — Бібліогр.: 16 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207498 519.854 10.1615/JAutomatInfScien.v44.i6.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Михайлюк, В.А. Реоптимизация упорядоченных обобщенных задач о выполнимости Проблемы управления и информатики
description	При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’язання задачі OCSP.
format	Article
author	Михайлюк, В.А.
author_facet	Михайлюк, В.А.
author_sort	Михайлюк, В.А.
title	Реоптимизация упорядоченных обобщенных задач о выполнимости
title_short	Реоптимизация упорядоченных обобщенных задач о выполнимости
title_full	Реоптимизация упорядоченных обобщенных задач о выполнимости
title_fullStr	Реоптимизация упорядоченных обобщенных задач о выполнимости
title_full_unstemmed	Реоптимизация упорядоченных обобщенных задач о выполнимости
title_sort	реоптимизация упорядоченных обобщенных задач о выполнимости
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207498
citation_txt	Реоптимизация упорядоченных обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 3. — С. 56–65. — Бібліогр.: 16 назв. - рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT mihajlûkva reoptimizaciâuporâdočennyhobobŝennyhzadačovypolnimosti AT mihajlûkva reoptimízacíâvporâdkovanihuzagalʹnenihzadačprovikonuvanístʹ AT mihajlûkva reoptimizationoforderedgeneralizedsatisfactionproblems
first_indexed	2025-10-09T01:08:32Z
last_indexed	2025-10-12T01:07:27Z
_version_	1845736240366747648
fulltext	© В.А. МИХАЙЛЮК, 2012 56 ISSN 0572-2691 УДК 519.854 В.А. Михайлюк РЕОПТИМИЗАЦИЯ УПОРЯДОЧЕННЫХ ОБОБЩЕННЫХ ЗАДАЧ О ВЫПОЛНИМОСТИ Введение Обобщенные задачи о выполнимости (Constraint Satisfaction Problems — CSP- задачи) описывают широкий класс оптимизационных задач, которые возникают во многих приложениях. Важные, хорошо изученные задачи, такие как Max Cut, Max 3-Sat, Max 3-Lin являются CSP-задачами. В CSP-задачах имеется множество переменных и множество ограничений (задаваемых предикатами), каждое из них зависит от некоторого числа переменных. Цель состоит в том, чтобы определить значения переменных, при которых выполняется максимальное количество огра- ничений. Более формально CSP-задача Q задается множеством предикатов над конечной областью }....,,2,1{][ qq  Каждый экземпляр задачи Q состоит из мно- жества переменных V и множества ограничений на нем. Нужно определить значе- ния переменных, при которых выполняется максимальное количество ограниче- ний. В общем случае предикаты могут быть заменены действительными платеж- ными функциями, и цель состоит в максимизации общего платежа. Для решения CSP-задач рассматриваются эффективные приближенные алго- ритмы. Для максимизационной задачи считается, что алгоритм является C-при- ближенным, если для произвольного экземпляра он дает решение со значением целевой функции, не меньшим ),10(  COPTC где OPT — глобальный опти- мум. При этом C называют отношением аппроксимации. Подобное определение можно дать для минимизационных задач. Считается, что для задачи Q установлена верхняя оценка отношения аппрок- симации C, если существует полиномиальный C-приближенный алгоритм для ре- шения .Q Для задачи Q установлена нижняя оценка отношения аппроксимации c, если для произвольного 0 не существует полиномиального приближенного ал- горитма для ,Q на котором достигается отношение аппроксимации, равное .c Если ,cC  то для задачи Q установлен порог отношения аппроксимации. Соот- ветствующий алгоритм называется пороговым или оптимальным (и отношение ап- проксимации оптимально). Фундаментальный вопрос для заданной NP-трудной задачи — определить, для каких значений C можно получить эффективный (полиномиальный) C-прибли- женный алгоритм. Это большая область исследований в теоретической информа- тике с положительными и отрицательными результатами. Проблема установления нижних оценок отношения аппроксимации (как и любая проблема получения нижних оценок сложности) является очень трудной задачей. Для такой проблемы существует термин неаппроксимируемость (inappro- ximability) или трудность аппроксимации (hardness of approximation). Большое влияние на развитие методов получения нижних оценок оказала известная PCP- теорема (probabilistically checkable proof theorem) [1] и дискретный анализ Фурье для тестирования свойств задач (property testing) [2, 3]. Тривиальный алгоритм, который игнорирует структуру экземпляра задачи и присваивает значения переменным случайно и независимо, удовлетворяет части  всех ограничений. Этот алгоритм может быть дерандомизирован стандартным способом. Таким образом, порог отношения аппроксимации всегда, как мини- Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 57 мум, — пороговое случайное присвоение значений. CSP-задача называется ап- проксимационно-устойчивой (approximation resistant), если аппроксимировать ее лучше, чем случайное пороговое присвоение значений, является NP-трудной за- дачей. Для таких задач порог аппроксимации равен случайному пороговому при- своению значений. В данной работе рассматриваются упорядоченные обобщенные задачи о вы- полнимости (Ordering CSP — OCSP). Каждая OCSP-задача размерности k задается подмножеством kS перестановок на }....,,1{][ kk  Экземпляр такой задачи состоит из множества переменных V и множества ограничений, каждое из кото- рых есть упорядоченный k-кортеж V. Нужно найти глобальное упорядочение  переменных, которое максимизирует число кортежей ограничений, выполняю- щих . Это естественное расширение CSP-задач на множество упорядоченных задач. Как и в случае CSP-задач, OCSP  аппроксимационно-устойчивая, если ее порог отношения аппроксимации равен !/ k — ожидаемому значению части ограничений, выполненных случайной перестановкой переменных. Наиболее из- вестными и простыми OCSP-задачами являются: задача максимального ацикличе- ского подграфа (Maximum Acyclic Subgraph — MAS-задача) [4, 5] и задача про- межуточности (Betweenness problem) [6, 7]. Проблема неаппроксимируемости успешно решена для многих задач с ис- пользованием PCP-теоремы [1]. В частности, Хастад (Hastad) [8] показал, что Max-E3-Lin-2 и Max 3-Sat являются аппроксимационно-устойчивыми. Наиболее перспективный подход к получению сильных результатов (порогов отношений ап- проксимации) — это так называемая уникальная игровая гипотеза (Unique Games Conjecture — UGC), введенная С. Хотом (S. Khot) [9], одна из наиболее важных открытых проблем в современной теоретической информатике из-за большого количества сильных результатов по неаппроксимируемости, которые следуют из UGC. Руководствуясь UGC, удалось показать, что каждая OCSP-задача с констант- ной размерностью аппроксимационно-устойчивая [5]. Этот факт используется в данной работе. Понятие реоптимизации [10–16] состоит в следующем. Пусть Q — некото- рая NP-трудная (возможно, NP-полная) задача, I — начальный экземпляр задач Q, оптимальное решение которого известно. Предлагается новый экземпляр I  зада- чи Q, полученный вследствие некоторых «незначительных» изменений экземпля- ра I. Возникает вопрос: как эффективно использовать знания об оптимальном ре- шении I для вычисления точного или приближенного решения экземпляра I  ? Цель реоптимизации при использовании приближенных методов — применение знаний о решении начального экземпляра I при условии: либо достижения лучше- го качества приближения (аппроксимационного отношения) ,I  либо создания более эффективного (по времени) алгоритма определения оптимального или близкого к нему решения ,I  либо выполнения обоих условий. Известны следующие результаты по реоптимизации дискретных задач оптими- зации. При добавлении элементарной дизъюнкции реоптимизация Max Weighted Sat (взвешенная задача о выполнимости на максимум) аппроксимируема с отношени- ем 0,81, хотя Max Weighted Sat аппроксимируема с отношением 0,77 [15]. При до- бавлении вершины в граф реоптимизация Min Vertex Cover (минимальное вершин- ное покрытие графа) аппроксимируема с отношением 1,5, Min Vertex Cover — с от- ношением 2 [15]. При добавлении вершины (терминальной или нетерминальной) реоптимизация Min Steiner Tree (минимальное дерево Штейнера) аппроксимируема с отношением 1,5, Min Steiner Tree — с отношением 55,1 2 )3ln( 1  [11]. 58 ISSN 0572-2691 При добавлении или удалении элемента из множества задача о покрытии множествами аппроксимируема с отношением )),1/(ln12(  m где m — число элементов множества. Подобный результат имеет место при добавлении или уда- лении произвольного числа mp 1 элементов из множества [16]. Следует от- метить цикл работ по реоптимизации задачи о коммивояжере (TSP — Travelling Salesman Problem) [10–12, 14]. Например, задача Minimum Metric TSP (Min TSP — задача о коммивояжере на минимум с метрическими расстояниями) аппроксими- руема с отношением 1,5, ее реоптимизация при добавлении нового узла — с от- ношением 1,34, реоптимизация этой задачи при изменении расстояний аппрок- симируема с отношением 1,4 [15]. Для общей задачи о коммивояжере (Min TSP) неизвестны оценки аппроксимации как для нее самой, так и для различных вер- сий реоптимизации. Основные результаты данной работы заключаются в следующем. Изучались реоптимизационные варианты упорядоченных обобщенных задач о выполнимо- сти размерности k )const( k при добавлении произвольного ограничения. При выполнении UGC для решения задачи Ins-OCSP (реоптимизация OCSP) суще- ствует полиномиальный оптимальный (пороговый) ))((  d -приближенный алго- ритм, где !/)(( )(2 1 ))(( kd d d    — пороговое «случайное» отношение аппроксимации для решения задачи OCSP). Постановка задачи Рассмотрим задачу максимального ациклического подграфа (Maximum Acyc- lic Subgraph, MAS-задача) [4, 5]. Для данного ориентированного ациклического графа G можно эффективно упорядочить его вершины так, чтобы обойти все реб- ра от вершин с меньшим рангом к вершинам с большим рангом. Что произойдет, если часть  ребер G изменит направление на противоположное? Можно ли об- наружить эту «ошибку» и найти упорядочение, если некоторые ребра изменят направление на противоположное? Можно ли для данного ориентированного гра- фа, вершины которого допускают упорядочение с частью 1 всех ребер, направленных вперед (т.е. от вершин с меньшим рангом к вершинам с бóль- шим рангом), формально найти упорядочение с частью  ребер, направленных вперед (при ),1 что эквивалентно отысканию подграфа G, который является ациклическим и имеет наибольшее количество ребер. Для того чтобы тривиально найти упорядочение с частью 1/2 ребер, направленных вперед: нужно взять луч- шее из произвольного упорядочения и противоположного ему. Это дает отноше- ние аппроксимации 1/2 для MAS-задачи (этого также можно достичь случайным упорядочением вершин). Несмотря на многочисленные попытки, не удалось найти эффективный -приближенный алгоритм для MAS-задачи при .2/1 Задача промежуточности (Betweenness problem — Bp) [6, 7] состоит в следу- ющем. Задано конечное множество вершин }...,,,{ 21 nvvvV  и множество m ограничений. Каждое ограничение — это тройка .),,( VVVvvv kji  Решение для Bp — это общий порядок «» на вершинах. Общий порядок niii vvv   21 удовлетворяет (выполняет) ограничению ),,,( kji vvv если либо ,kji vvv  ли- бо .ijk vvv  Нужно найти упорядочение с максимальным числом выполнен- ных ограничений. Эта задача используется в молекулярной биологии и является NP-полной [6]. Легко найти упорядочение, которое выполняет 1/3 всех m ограни- чений — это случайное упорядочение, что дает )3/1( — приближенный алгоритм для Bp. Попытки найти эффективный -приближенный алгоритм для Bp при 3/1 также пока не увенчались успехом. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 59 Приведем необходимые обозначения и определения [4, 5, 7]. Определение 1. Упорядоченная OCSP  размерности k задается платежной функцией ],1,0[: kSP где kS — множество перестановок }....,,2,1{ k Экзем- пляр такой задачи состоит из множества переменных V и множества кортежей- ограничений T, каждое из которых — упорядоченный k-кортеж из V. Цель состо- ит в определении глобального упорядочения  множества V, которое максимизи- рует ожидаемое значение платежа )]([ \|TPE  для случайного ,T где kT S \| — упорядочение k элементов T, индуцированное глобальным упорядо- чением . Для общности вместо {0, 1} можно использовать платежные функции со зна- чениями из [0, 1], что соответствует значениям истина/ложь в ограничениях. Без потери общности путем переупорядочения входных данных любого ограничения можно предполагать, что перестановка , которая максимизирует ),(P тожде- ственна ).(id Пусть )(opt Iw — значение оптимального решения  экземпляра I задачи . Определение 2. Алгоритм A есть C-приближенный алгоритм для максимиза- ционной задачи, если для всех экземпляров I задачи ),(),( opt IwCIAw  где ),( IAw — значение решения алгоритма A на входе I. При этом считается, что A имеет отношение аппроксимации C. Для вероятностных алгоритмов ),( IAw — ожидаемое значение (математическое ожидание) среди случайных выборов алго- ритма A. Определение 3. Считается, что OCSP размерности k с платежной функцией P аппроксимационно-устойчивая, если ее пороговое отношение аппроксимации рав- но )( )]([ idP PE kS   — отношению, выбранному случайным упорядочением. Согласно определению 1 MAS соответствует такой простой OCSP:  состоит из упорядочения }21{ из множества ).2(2 kS Задача Bp состоит из ограничений вида }321,123{ из множества ).3(3 kS В дальнейшем будем считать, что OCSP задаются не платежными функциями, а предикатами },1,0{: kSP где 0 — ложь, а 1 — истина. Пусть  — число перестановок в предикате P со значением 1 (ис- тина) для OCSP-задачи . Будем считать, что const.k Имеет место утверждение. Теорема 1. Для произвольной OCSP-задачи  существует полиномиальный приближенный алгоритм с отношением аппроксимации !./ k Доказательство. Пусть m — число ограничений в произвольном экземпля- ре I OCSP задачи . Рассмотрим случайное упорядочение переменных V. Среднее число выполненных ограничений при таком упорядочении (математическое ожи- дание) есть , ! m k   откуда следует утверждение теоремы. Рассмотрим следующую реоптимизационную версию упорядоченной обоб- щенной задачи о выполнимости. Пусть  есть OCSP размерности k и I экземпляр такой задачи состоит из множества переменных V и множества кортежей- ограничений Т, каждое из которых есть упорядоченный k-кортеж из V. Пусть  — оптимальное решение I, а T  есть k-кортеж, не содержащийся в T. Экзем- пляр I  получается из I добавлением k-кортежа .T  Задача Ins-OCSP. Входные данные. Произвольный экземпляр I OCSP задачи ,  — оптимальное решение экземпляра I. 60 ISSN 0572-2691 Результат. Оптимальное решение экземпляра I  (полученного исходя из I, как описано выше) задачи , используя . Цель. Найти , которое максимизирует число выполненных ограничений экземпляра .I  Уникальная игровая гипотеза и неаппроксимируемость Как отмечалось ранее, большое влияние на развитие методов получения нижних оценок отношения аппроксимации (неаппроксимируемости) оказала PCP- теорема [1] и дискретный анализ Фурье для тестирования свойств задач (property testing) [2, 3]. Типичную технику получения результатов по неаппроксимируемо- сти можно описать следующим образом. Пусть P — произвольная оптимизацион- ная (для определенности на максимум) задача. Под gapsc ),( версией задачи P (обозначение ), scPGap будем понимать задачу, для которой либо ,)( cIOPT  либо sIOPT )( для произвольного экземпляра .PI  Рассмотрим NP-полную задачу 3-Sat (3-выполнимость). Произвольная 3-Sat формула CNFE 3( форму- ла) — это конъюнкция множества скобок, где каждая скобка — это дизъюнкция трех булевых переменных или их отрицаний. Нужно определить приписывания булевым переменным таких значений истинности, что формула становится логи- чески истинной (выполнимой). Допустим, что существует полиномиальная сво- димость от 3-Sat к scPGap , для некоторых ,0 cs  т.е. сводимость, которая отображает 3-Sat формулу  на экземпляр I задачи P такой, что: (случай «да»): Если  имеет приписывание, которое делает ее выполнимой, то ;)( cIOPT  (случай «нет»): Если  не имеет приписываний, которые делают ее выпол- нимой, то .)( sIOPT  Такая сводимость предполагает, что если существует полиномиальный алго- ритм с отношением аппроксимации, строго большим, чем s /c для задачи Р, то имеется возможность определить, выполнима ли 3-Sat формула и, следовательно, .NPP  Таким образом, при стандартном предположении NPP  эта своди- мость — источник получения результатов по неаппроксимируемости для зада- чи Р. Будем исходить из PCP-теоремы [1] в той или иной форме для некоторого NP-полного языка (например, 3-Sat). Строится сводимость к задаче (языку), неап- проксимируемость которой нужно установить (например, )., scPGap Конструи- руется PCP проверяющий (verifier) для данной задачи Р, представимый в виде не- которого теста (диктаторского) для булевой функции, соответствующей Р [8]. Ис- пользуя элементы и некоторые результаты Фурье-анализа булевых функций, оценивается полнота (completeness) c проверяющего (нижняя оценка вероятности принятия теста, что булева функция диктаторская, или случай «да») и коррект- ность (soundness) s проверяющего (верхняя оценка вероятности непринятия теста, булева функция далека от диктаторской или случай «нет»). Отсюда следует, что задача Р — NP-трудная для аппроксимации с отношением, большим s/c. Это обычная неаппроксимируемость. Если исходить не из PCP-теоремы, а из UGC в описанной выше сводимости, получим неаппроксимируемость, основанную на UGC, или условную неаппрок- симируемость (conditional inapproximability). UGG есть некоторое усиление PCP-теоремы, сформулируем ее для уникаль- ной игровой задачи (Unique Games Problem — UGP). Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 61 Определение 4. Экземпляр UGP представлен в виде ])[,,,( REBA   и состоит из двудольного графа со множеством вершин  BA , и ребер E между ними. Частью экземпляра есть множество меток }...,,1{][ RR  и множество биек- ций ][][: RRba   для каждого ребра ,),( Ebae  где   BbAa , (иног- да биекция ba для ребра ),( bae  обозначается как ).e Считается, что при- писывание ][: RBAA   меток к вершинам удовлетворяет ребру ),,( bae  если ).())(( bAaAba   Нужно определить присвоение А меток, которое делает максимальное число ребер выполнимыми. Используется следующая версия UGC, эквивалентная оригинальной [9]. Для любого 0 следующая задача NP-трудная для достаточно большого выбора R: для данного экземпляра уникальной игровой задачи ])[},),(\|][][:{,,( REbaeRREBA ba   с числом меток R нужно отличить два случая:  )1(  — сильно выполнимые экземпляры: существует присвоение A меток такое, что часть 1 вершин Aw сильно выполнима, т.е. все ребра ),( vw выполнимы;  экземпляры, которые не являются  -выполнимыми: никакое присвоение меток не удовлетворяет более чем части  ребер E. Аппроксимационно-устойчивые упорядоченные обобщенные задачи о выполнимости Основной результат работы [5] состоит в следующем. Произвольная OCSP фиксированной размерности k (не более чем константа) аппроксимационно- устойчивая, если исходить из UGC. Согласно определению 3 это означает, что улучшение тривиального аппроксимационного отношения, достижимого случай- ным упорядочением, невозможно, если UGC истинна. В дальнейшем этот факт будем формулировать так: улучшение случайного аппроксимационного отноше- ния является UG-трудной задачей (Unique Games-hard — UG-hard). Если исходить из стандартной гипотезы ),( NPP  то такое улучшение случайного аппроксима- ционного отношения является NP-трудным [8]. Ясно, что если UGC истинна, то UG -трудность превращается в NP-трудность. Используем следующий результат. Теорема 2 [5]. Пусть k — положительное целое и  есть OCSP, связанная с платежной функцией ]1,0[: kSP на множестве k-перестановок .kS Пусть )(maxmax   P kS — максимальное значение P и )(  PE kS random — среднее значение P (ожидаемое значение, достижимое однородным случайным упорядо- чением). Тогда для произвольного 0 выполняется следующее. Для данного экземпляра OCSP с платежной функцией P, который допускает упорядочение со значением, не меньшим, чем ,max  найти упорядочение экземпляра с дости- жением значения random по отношению к P является UG-трудной задачей. Следствие 1. Для произвольного 0 аппроксимировать OCSP с отношени- ем  max/random является UG-трудной задачей. Иными словами, OCSP ап- проксимационно-устойчива при выполнении UGC. Предполагая, что OCSP задаются не платежными функциями, а предикатами }1,0{: kSP (где 0 — ложь, а 1 — истина), получим 1)(maxmax   P kS и ,!/)( kPE kS random   откуда вытекает утверждение. 62 ISSN 0572-2691 Следствие 2. Пусть k — положительное целое и  есть OCSP, связанная с предикатом }1,0{: kSP на множестве k-перестановок .kS Тогда для произ- вольного 0 отличить экземпляры, где часть 1 ограничений может быть упорядочена согласно  экземпляров, где не более чем часть  !/ k экзем- пляров может быть упорядочена, как в , является UG-трудной задачей. Теорема 3. Пусть k — положительное целое и  есть OCSP, связанная с преди- катом }1,0{: kSP на множестве k-перестановок .kS Тогда при выполнении UGC для  существует оптимальный (пороговый) !k  -приближенный алгоритм. Доказательство. Верхняя оценка !/ k следует из теоремы 1. Нижняя оцен- ка, которая совпадает с верхней (при выполнении UGC), вытекает из следствия 2. Теорема 4. Для произвольного экземпляра  задачи MAS (максимальный ациклический подграф) при выполнении UGC существует оптимальный (порого- вый) 2 1 -приближенный алгоритм. Доказательство. Как уже отмечалось, согласно определению 1 MAS соответ- ствует такой простой OCSP:  состоит из упорядочения }12{ из множества ).2(2 kS Таким образом, в нашем случае .2/1!/  k Осталось применить теорему 3. Теорема 5. Для произвольного экземпляра  задачи Bp (задача промежу- точности) при выполнении UGC существует оптимальный (пороговый) 3 1 -при- ближенный алгоритм. Доказательство. Как уже отмечалось, задача Bp состоит из ограничений ви- да }321,123{ из множества ).3(3 kS Таким образом, в нашем случае  !/ k .3/16/2  Осталось применить теорему 3. Приближенные полиномиальные алгоритмы для реоптимизации упорядоченных задач о выполнимости. Порог отношения аппроксимации Пусть k — положительное целое и  есть OCSP, связанная с предикатом }1,0{: kSP на множестве k-перестановок .kS Обозначим !./)( kd  Пусть I — произвольный экземпляр задачи . Если  — произвольное упорядочение V, то )(w есть значение решения  экземпляра I задачи  т.е. )()( \|   T TPw (где T — множество всех кортежей-ограничений экземпляра I ). Если )(opt Iw — значение оптимального решения  экземпляра I задачи , то ).()( opt  wIw Теорема 6. Для произвольной задачи Ins-OCSP (реоптимизация OCSP) суще- ствует полиномиальный приближенный алгоритм с отношением аппроксимации .))(2/(1 d Доказательство. Применим подход, рассмотренный в [15, 16]. Пусть I — про- извольный экземпляр OCSP задачи  который состоит из системы ограничений }}...,,1{][,{ )( mmiTΤ i  и оптимального решения ; )( w — количество выполненных ограничений в системе T решением . К системе добавляем ограни- чение ,)1( mT в результате получаем экземпляр I  задачи Ins-OCSP, пусть I' — его оптимальное решение. Если * I' не выполняет ограничение ,)1( mT то  есть оптимальное решение экземпляра I  задачи Ins-OCSP, отсюда Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 63 .1)()( *  I'ww (1) Из левой части неравенства следует, что  — оптимальное решение ,I  а из правой части — что оптимальное решение не выполняет ограничение .)1( mT Пусть I' выполняет ограничение ,)1( mT и пусть имеется число l вариантов, при которых будет выполнено ограничение )1( mT (очевидно, ,!kl  что является константой). Построим l приближенных решений })...,,1{][( llii  следующим образом. Берем i-е упорядочение, которое выполняет .)1( mT Из системы ограни- чений удаляем )1( mT и к ограничениям, которые остались, применяем некото- рый полиномиальный -приближенный алгоритм, в результате получаем прибли- женное решение :i .1)(1)1)(()(   II i www (2) Умножая (1) на 1 и складывая с (2), получаем ).(1)()1()()1()()()1( ** I'I'I' i wwwww  Среди решений  и i выбираем наилучшее (т.е. с наибольшим значением целевой функции )w и обозначаем . Имеем ),()2()}(),(max{)11()( *   wwww i I откуда ).( 2 1 )( * Iww    Таким образом, в результате выполнения описанного алгоритма получено приближенное решение  экземпляра I  с отношением ап- проксимации ).2/(1  Ясно, что всегда ).1()2/(1  Положим  )(d ,!/ k т.е., применив приближенный алгоритм из теоремы 1, получим утвер- ждение данной теоремы. Теорема 7. Если при выполнении UGC для Ins-OCSP существует полиноми- ально приближенный алгоритм с отношением аппроксимации , то . )(2 1   d Доказательство. Пусть I — произвольный экземпляр OCSP задачи , кото- рый состоит из системы ограничений }}...,,1{][,{ )( mmiTΤ i  и оптимального решения ; )( w — число выполненных ограничений в системе T решением . К системе добавляется ограничение ,)1( mT в результате получаем экземпляр I  задачи Ins-OCSP. Пусть  — решение задачи Ins-OCSP, получен- ное в результате применения алгоритма из доказательства теоремы 6. Решение  является лучшим (бóльшим по значению целевой функции) из решений  и i );!],[( klli  оно получается полиномиальным приближенным алгоритмом с от- ношением аппроксимации .)2/(1)(  Доказательство проведем от противно- го. Пусть ))(2/(1  d и .)(  Поскольку функция )( является возраста- ющей по  и )),(())(2/(1)(  dd то отсюда следует, что ),( d а это противоречит теореме 3 (в частности, следствию 2). Поскольку при выполнении UGC для задачи OCSP не существует полиномиального приближенного алгоритма с отношением аппроксимации, бóльшим ).(d Теорема 8. При выполнении UGC для произвольной задачи Ins-OCSP (ре- оптимизация OCSP) существует полиномиальный приближенный алгоритм с от- 64 ISSN 0572-2691 ношением аппроксимации )).(2/(1 d Данное отношение аппроксимации явля- ется пороговым. Доказательство следует из теорем 6 и 7. Последовательно применяя теорему 8 для MAS-задачи и задачи промежуточ- ности, получаем утверждения. Утверждение 1. При выполнении UGC для реоптимизации задачи макси- мального ациклического подграфа при добавлении произвольного направленного ребра существует полиномиальный приближенный алгоритм с отношением ап- проксимации 2/3. Данное отношение аппроксимации пороговое. Утверждение 2. При выполнении UGC для реоптимизации задачи промежу- точности при вставке произвольного ограничения существует полиномиальный приближенный алгоритм с отношением аппроксимации 3/5. Данное отношение аппроксимации пороговое. Заключение При выполнении UGC для решения задачи Ins-OCSP (реоптимизация OCSP) существует полиномиальный оптимальный (пороговый) ))((  d -приближенный алгоритм, где ! )(())(2())(( 1 k ddd    — пороговое «случайное» от- ношение аппроксимации для решения задачи OCSP). Результаты настоящей работы существенно зависят от истинности UGC, что наряду с проблемами взаимоотношения классов сложности задач по включению (например, ?)NPP  . Это является одной из основных открытых задач современ- ной теоретической информатики. Даже если UGC ложна, может оказаться, что в уникальной игровой задаче указанные два случая трудны в смысле неразрешимо- сти за полиномиальное время (что, на наш взгляд, кажется наиболее вероятным) и такая (слабая) трудность может применяться ко всем задачам, где трудность воз- никала, исходя из UGC. В.О. Михайлюк РЕОПТИМІЗАЦІЯ ВПОРЯДКОВАНИХ УЗАГАЛЬНЕНИХ ЗАДАЧ ПРО ВИКОНУВАНІСТЬ При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі Ins- OCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліно- міальний оптимальний (пороговий) наближений алгоритм. Його апроксима- ційне відношення залежить від порогового «випадкового» відношення апрок- симації для розв’язання задачі OCSP. V.A. Mikhailyuk REOPTIMIZATION OF ORDERED GENERALIZED SATISFACTION PROBLEMS Assume that Unique Games Conjecture (UGC) holds. Then for solving Ins-OCSP (reoptimization of OCSP under insertion of one constraint) polynomial optimal (threshold) approximated algorithm exists. The approximation ratio of this algorithm depends on threshold «random» approximation ratio for solving OCSP problem. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 65 1. Arora S., Lund C., Motwani R., Sudan M., Szegedy M. Proof verification and intractability of ap- proximation problems // J. of the ACM. — 1998. — 45, N 3. — P. 501–555. 2. Goldreich O., Goldwasser S., Ron D. Property testing and its connection to learning and approx- imation abstract // Ibid. — 1998. — 45, N 4. — P. 653–750. 3. Goldreich O., Sudan M. Locally testable codes and PCPs of almost-linear length // Ibid. — 2006. — 53, N 4. — P. 558–655. 4. Guruswami V., Manokaran R., Raghavendra P. Beating the random ordering is hard: Inapproxi- mability of maximum acyclic subgraph // Proceedings of the 49th Annual IEEE Symposium on Foundation of Computer Science. — 2008. — P. 573 — 582. 5. Beating the random ordering is hard: every ordering CSP is approximation resistant / V. Gurus- wami, J. Hastad, R. Manokaran, P. Raghavendra, M. Charikar // Electronic Colloquium on Com- putational Complexity. — 2011. — Rep. N 27. 6. Chor B., Sudan M. A geometric approach to betweenness // SIAM Journal on Discrete Mathemat- ics. — 1998. — 11. — P. 511–523. 7. Charikar M., Guruswami V., Manokaran R. Every permutation CSP of arity 3 is approximation resistant // Proceedings of the 24th Annual IEEE Conference on Computational Complexity. — 2009. — P. 62–73. 8. Hastad J. Some optimal inapproximability results // Journal of the ACM. — 2001. — 48, N 4. — P. 798–859. 9. Khot S. On the power of unique 2-prover 1-round games // STOC’02 Proceedings of the thirty- fourth annual ACM symposium on Theory of computing. — 2002. — P. 767–775. 10. Ausiello G., Escoffier B., Monnot J., Paschos V.Th. Reoptimization of minimum and maximum traveling salesman’s tours // Algorithmic theory. — SWAT 2006, Lect. Notes Comput. Sci. — Berlin : Springer, 2006. — 4059. — P. 196–207. 11. Bockenhauer H.J., Forlizzi L., Hromkovic J., et al. On the approximability of TSP on local modi- fications of optimal solved instances // Algorithmic Oper. Res. — 2007. — 2(2). — P. 83–93. 12. Bockenhauer H J., Hromkovic J., Momke T., Widmayer P. On the hardness of reoptimization // Lect. Notes Comput. Sci. — 2008. — Berlin : Springer — 4910. — P. 50–65. 13. Escoffier B., Milanic M., Paschos V. Simple and fast reoptimizations for the Steiner tree problem // Algorithmic Oper. Res. — 2009. — 4(2). — P.86–94. 14. Archetti C., Bertazzi L., Speranza M.G. Reoptimizing the travelling salesman problem // Net- works. — 2003. — 42(3). — P. 154–159. 15. Ausiello G., Bonifaci V., Escoffier B. Complexity and approximation in reoptimization // Comput- ability in Context: Computation and Logic in the Real World (ed. S. Barry Cooper and Andrea Sorbi). — London : Imperial College Press., 2011. — P. 101–130. 16. Михайлюк В.А. Реоптимизация задачи о покрытии множествами // Кибернетика и систем- ный анализ. — 2010. — 46, № 6. — С. 27–31. Получено 07.12.2011 Статья представлена к публикации членом редколлегии акад. НАН Украины И.В. Сергиенко.

Реоптимизация упорядоченных обобщенных задач о выполнимости

Репозитарії

Схожі ресурси