О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3
При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84720 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859946115576627200 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3CSP - EQUAL и Φ(αEQU ) = 1 / (2 - αEQU ) ≈ 0.831 .
При виконанні унікальної ігрової гіпотези (UGC) для задачі Ins - Max - E3CSP - EQUAL (реоптимізація Max - E3CSP - EQUAL при добавленні одного обмеження) існує поліноміальний оптимальний (пороговий) Φ(αEQU ) -наближений алгоритм, де αEQU ≈ 0.796 порогове відношення апроксимації Max - E3CSP - EQUAL і Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831.
If the unique games conjecture (UGC) is true, for the problem Ins - Max - E3CSP - EQUAL ( reoptimization of Max - E3CSP - EQUAL under insertion of one constraint) polynomial optimal (threshold) Φ(αEQU ) - approximation algorithm exists, where aEQU ≈ 0.796 is the threshold approximation ratio of Max - E3CSP - EQUAL and Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831.
|
| first_indexed | 2025-12-07T16:14:18Z |
| format | Article |
| fulltext |
156
При выполнении уникальной игро-
вой гипотезы (UGC) для задачи
3Ins Max E CSP EQUAL− − − (реоп-
тимизация 3Max E CSP EQUAL− −
при добавлении одного огра-
ничения) существует полиноми-
альный оптимальный (пороговый)
( )EQUφ α -приближенный алгоритм,
где 0.796EQUα ≈ пороговое отно-
шение аппроксимации Max −
3E CSP EQUAL− − и ( )EQUφ α =
1 / (2 ) 0.831EQU= − α ≈ .
В.А. Михайлюк, 2012
УДК 519.854
В.А. МИХАЙЛЮК
О ПОРОГЕ ОТНОШЕНИЯ
АППРОКСИМАЦИИ
ДЛЯ РЕОПТИМИЗАЦИИ
ОБОБЩЕННОЙ ЗАДАЧИ О
ВЫПОЛНИМОСТИ
С ПРЕДИКАТОМ РАЗМЕРНОСТИ
3
Введение. Ообобщенные задачи о выполни-
мости (Constraint Satisfaction Problems или
CSP задачи) задаются множеством перемен-
ных и множеством ограничений (которые со-
стоят из предикатов), каждое из которых за-
висит от некоторого числа переменных, и
цель состоит в том, чтобы найти такие при-
писывания значений переменным, выпол-
няющим (удовлетворяющим) максимальное
число ограничений. Большое число фунда-
ментальных оптимизационных проблем, та-
ких как Max Cut и Max k-Sat, – примеры CSP
задач.
Большинство CSP задач являются NP -труд-
ными и поэтому решить их точно за прием-
лемое время вряд ли представляется возмож-
ным. Поэтому рассматриваются эффектив-
ные (полиномиальные) приближенные алго-
ритмы для решения таких задач. Для макси-
мизационной задачи говорят, что алгоритм
есть C -приближенным алгоритмом, если он
для произвольного экземпляра дает решение
со значением целевой функции не меньшим,
чем (0 1)C OPT C⋅ < < , где OPT − глобаль-
ный оптимум. При этом C называют отно-
шением аппроксимации. Подобное определе-
ние можно дать для минимизационных задач.
Компьютерная математика. 2012, № 2
157
Говорят, что для задачи Q
установлена верхняя оценка
отношения аппроксимации
C , если существует полино-
миальный C -при-ближенный
алгоритм для решения Q .
В.А. МИХАЙЛЮК
158 Компьютерная математика. 2012, № 2
Для задачи Q установлена нижняя оценка отношения аппроксимации ,c
если для произвольного 0ε > не существует полиномиального приближенного
алгоритма для Q на котором достигается отношение аппроксимации c − ε . Если
C c= , то для задачи Q установлен порог отношения аппроксимации (равный
C c= ). Соответствующий алгоритм называется пороговым или оптимальным
(и отношение аппроксимации – оптимально). Если для CSP задачи верхняя
оценка C достигается случайными приписываниями и эта оценка совпадает
с нижней c , то предикат соответствующий задаче (и задачу) называют аппрок-
симационно-устойчивой.
Для некоторых CSP задач удалось получить пороговые значения отношения
аппроксимации. Например, для Max 3-Sat и Max 3-Lin это удалось сделать с ис-
пользованием известной PCP теоремы [1]. Для некоторых (Vertex Cover, задача о
минимальном вершинном покрытии графа) для этого привлекалась уникальная иг-
ровая гипотеза (Unique Games Conjecture, UGC), введенная Кхотом (Khot) [2, 3].
В работе [4] установлен факт существования порогового отношения аппроксимации
для произвольных CSP константной размерности с привлечением техники полу-
определенного программирования (Semidefinite Programming, SDP) и UGC.
Понятие реоптимизации [5, 6] состоит в следующем. Пусть Q − некоторая
NP -трудная (возможно, NP -полная) проблема, I − начальный экземпляр про-
блемы Q , оптимальное решение которого известно. Предлагается новый экзем-
пляр 'I задачи Q , полученный некоторыми «незначительными» изменениями
экземпляра I . Как можно эффективно использовать знания об оптимальном ре-
шении I для вычисления точного или приближенного решения экземпляра 'I ?
Цель реоптимизации при применении приближенных методов – использование
знаний о решении начального экземпляра I для достижения лучшего качества
приближения (аппроксимационного отношения) 'I .
Мало изучена и исследована проблема нахождения пороговых (оптималь-
ных) приближенных алгоритмов для реоптимизации дискретных задач оптими-
зации. В [7] найден порог отношения аппроксимации для реоптимизации упоря-
доченных CSP задач (с использованием UGC). Для реоптимизации CSP задач с
аппроксимационно-устойчивыми предикатами в [8] установлен порог отноше-
ния аппроксимации (с использованием PCP теоремы). В работе [9] найдены по-
роговые значения отношения аппроксимации (конкретные численные значения)
для реоптимизации Max Cut и Max 2-Sat(с использованием UGC).
В данной работе устанавливается порог отношения аппроксимации (конкретное
численное значение) для реоптимизации CSP задачи с предикатом размерно-
сти 3, который не является аппроксимационно-устойчивым.
Основные определения и постановка задачи. Пусть Q обозначает NP -пол-
ную (или NP -трудную) проблему. Для экземпляра I проблемы Q размерности
n ( )OPT I является значение оптимального решения. Для полиномиально
О ПОРОГЕ ОТНОШЕНИЯ АППРОКСИМАЦИИ ДЛЯ РЕОПТИМИЗАЦИИ ОБОБЩЕННОЙ ЗАДАЧИ…
Компьютерная математика. 2012, № 2 159
приближенного алгоритма ( )ALG I обозначает значение решения, находящее
алгоритм (или его математическое ожидание, если алгоритм случайный). Пусть
C параметр, который может быть и функцией от n .
Определение 1. Алгоритм достигает аппроксимационное отношение C , если
для произвольного экземпляра I :
( ) ( )ALG I C OPT I≥ ⋅ , Q − максимизационная проблема, при этом 0 1C< < ;
( ) ( )ALG I C OPT I≤ ⋅ , Q − минимизационная проблема, при этом 1C > .
При этом говорят, что алгоритм – C -приближенный.
Пусть задан алфавит [ ] {1,..., }q q= и множество предикатов :[ ] {0,1}kqΠ → ,
здесь k размерность предикатов.
Определение 2. Экземпляр задачи Max CSP P− − (скажем I ) задается n пе-
ременными 1,..., nx x и множеством ограничений Ε таким, что каждое e∈Ε
имеет вид ( , )e S P= , где [ ]kS n∈ и P ∈Π . Рассмотрим отображение
:[ ] [ ]L n q→ . Будем говорить, что ограничение ( , )e S P= выполняется (удовле-
творяется), если 1( ( ),..., ( )) 1kP L S L S = , где iS – i -й элемент S . Определим зна-
чение целевой функции 1( ) ( ( ),..., ( ( ))L e kval I E P L S P L S∈Ε= =
1( ( ),..., ( ))e ke
w P L S L S∈Ε=∑ , где ew задает распределение весов ограничений.
Нужно найти такое отображение L , что ( )Lval I максимально, т. е.
*( ) ( ) max ( )L LL
val I val I val I= = , при этом *L – оптимальное решение. Если P
зависит от не более чем k литералов Max CSP P− − будем называть
Max kCSP P− − , если в P ровно k литералов – то Max EkCSP P− − .
В дальнейшем будем считать 1ew = для произвольного e∈Ε . В качестве
реоптимизационной версии задачи Max EkCSP P− − будем рассматривать зада-
чу следующего вида.
Задача Ins Max EkCSP P− − − . Входные данные. Экземпляр I задачи
Max EkCSP P− − , содержащий ограничение ( , )e S P= , где [ ]kS n∈ и P ∈Π .
Экземпляр 'I получается из I добавлением некоторого ' ( ', )e S P= ,
где ' [ ]kS n∈ .
Результат. Найти оптимальное решение экземпляра 'I задачи
Max EkCSP P− − , используя оптимальное решение *L экземпляра I .
Цель. Найти L , которое максимизирует число выполненных ограничений
экземпляра 'I .
Будем рассматривать случай 3k = и положим P EQUAL= (булевский пре-
дикат EQUAL выполняется тогда и только тогда, когда все его переменные ли-
бо единицы, либо нули). Известно, что задача 3Max E CSP EQUAL− − не являет-
ся аппроксимационно-устойчивой [10].
В.А. МИХАЙЛЮК
160 Компьютерная математика. 2012, № 2
Оптимальный приближенный алгоритм для задачи Max – E3CSP – EQUAL.
Используем результаты работы [11]. Верхняя оценка отношения аппроксимации
для задачи 3Max E CSP EQUAL− − получена с помощью полу-определенной
(Semidefinite, SDP) релаксации.
Теорема 1 [11]. Для задачи 3Max E CSP EQUAL− − существует полиноми-
альный приближенный алгоритм со следующим отношением аппроксимации:
1
(0,1]
3cos (1 )
1
2min 0.796
3
1
4
EQU
−
δ∈
− δ−
πα = ≈δ−
.
Нижняя оценка отношения аппроксимации получена с помощью уникаль-
ной игровой гипотезы (UGC). Типичную технику получения результатов по
нижним оценкам отношения аппроксимации (неаппроксимируемости) можно
описать следующим образом. Пусть Q − произвольная оптимизационная (для
определенности на максимум) проблема. Под ( . )c s gap− версией проблемы
Q (обозначение ,c sGap Q− ) будем понимать проблему, для которой либо
( )OPT I c≥ , либо ( )OPT I s≤ для произвольного экземпляра I Q∈ . Рассмотрим
NP -полную проблему 3-Sat (3-выполнимость). Произвольная 3-Sat формула
( 3E CNF− формула) – это конъюнкция множества скобок, где каждая скобка
это дизъюнкция трех булевских переменных или их отрицаний. Цель состоит в
определении приписывания булевским переменным таких значений истинности,
что формула становится логически истинной (выполнимой). Допустим, что су-
ществует полиномиальная сводимость от 3 Sat− к ,c sGap Q− для некото-
рых0 s c< < , т. е. сводимость, отображающая 3-Sat формулу ψ на экземпляр
I проблемы Q такой, что:
(Случай-да): Если ψ имеет приписывание, которое делает ее выполнимой,
то ( )OPT I c≥ ;
(Случай-нет): Если ψ не имеет приписываний, которые делают ее выпол-
нимой, то ( )OPT I s≤ .
Такая сводимость предполагает, что если существует полиномиальный ал-
горитм с отношением аппроксимации большим, чем /s c для проблемы Q , то
есть возможность эффективно определить выполнима ли 3-Sat формула и, сле-
довательно, P NP= . Таким образом, при стандартном предположении P NP≠
эта сводимость – источник получения результатов по неаппроксимируемости
для проблемы Q . Если исходить из Probabilistically Checkable Proof (PCP) тео-
ремы [12] в той или иной форме для некоторого NP-полного языка (например,
3-Sat) получим обычную неаппроксимируемость. Если же исходить не из PCP
теоремы, а из уникальной игровой гипотезы (UGC) в вышеописанной сводимо-
сти, получим неаппроксимируемость, основанную на UGC или условную неап-
проксимируемость (conditional inapproximability).
О ПОРОГЕ ОТНОШЕНИЯ АППРОКСИМАЦИИ ДЛЯ РЕОПТИМИЗАЦИИ ОБОБЩЕННОЙ ЗАДАЧИ…
Компьютерная математика. 2012, № 2 161
Уникальная игровая гипотеза рассматривалась в такой постановке.
Уникальная игровая гипотеза (UGC). Для любого 0δ > существует такое про-
стое p , что для данной системы линейных уравнений (mod )i j ijx x c p− = явля-
ется NP -трудным определить, какое из этих двух утверждений истинно:
• существует приписывание ix , выполняющее (удовлетворяющее) (1 )− δ –
часть всех ограничений (уравнений);
• все приписывания ix могут выполнять не больше δ – часть всех ограни-
чений.
Теорема 2[11]. Предполагая UGC для любого 0 1< δ < и 0ε > является
NP -трудным различить экземпляр задачи 3Max E CSP EQUAL− − со значением
1 3 / 4− δ − ε от экземпляра со значением
13cos (1 )
1
2
− − δ− + ε
π
. Иными словами,
предполагая UGC, для любого 0δ > не существует приближенного полиноми-
ального алгоритма для 3Max E CSP EQUAL− − с отношением аппроксимации
EQUα + δ .
Используя теоремы 1 и 2, получаем результат.
Следствие. Для задачи 3Max E CSP EQUAL− − существует оптимальный
(пороговый) EQUα -приближенный алгоритм.
Порог отношения аппроксимации для задачи Ins – Max – E3CSP – EQUAL.
Имеет место следующий результат.
Теорема 3. Если для задачи 3Max E CSP P− − существует полиномиальный
ρ -приближенный алгоритм, то для задачи 3Ins Max E CSP P− − − (реоптимиза-
ция 3Max E CSP P− − ) существует полиномиальный ( )φ ρ -приближенный алго-
ритм, где
1
( )
2
φ ρ =
− ρ
.
0, с множеством ограничений Ε и *L – оптимальное решение
I *( ( ) ( ))
L
val I val I= . К системе добавляется ограничение ' ( ', )e S P= , где
' [ ]kS n∈ , в результате получаем экземпляр 'I проблемы 3Ins Max E CSP P− − − ,
пусть *
'IL его оптимальное решение *
'
( ( ') ( '))
IL
val I val I= . Если *
'IL не выполняет
ограничение 'e , то *L – оптимальное решение экземпляра 'I задачи
3Ins Max E CSP P− − − , отсюда
( ) ( ') 1val I val I≥ − (1)
(в левой части записано условие, что *L – оптимальное решение 'I , а в правой,
что оптимальное решение *
'IL не выполняет ограничение 'e ). Пусть *
'IL выпол-
няет ограничение 'e и есть l вариантов, при которых будет выполнено ограни-
В.А. МИХАЙЛЮК
162 Компьютерная математика. 2012, № 2
чение 'e (очевидно 32 8l < = ). Построим l приближенных решений
( [ ])ix i l∈ следующим образом. Берем i -е приписывание, выполняющее 'e . Из
системы ограничений удаляем 'e и к ограничениям, оставшимся (учитывая ре-
зультат приписывания) применяем некоторый полиномиальный ρ -прибли-
женный алгоритм, получаем приближенное решение iL . В результате получаем
( ) ( ( ') 1) 1 ( ') 1iL
val I val I val I≥ ρ − + = ρ + − ρ (2)
Умножая (1) на 1− ρ и складывая с (2) получаем
(1 ) ( ) ( ) (1 ) ( ') (1 ) ( ') 1 ( ')iL
val I val I val I val I val I− ρ + ≥ − ρ − − ρ + ρ + − ρ =
Среди решений *L и iL выбираем наилучшее (т. е. с наибольшим значением
целевой функции val ) и обозначаем L . Имеем
( ') (1 1) max{ ( ), ( )} (2 ) ( )i LL
val I val I val I val I≤ − ρ + = − ρ ,
откуда
1
( ) ( ')
2Lval I val I≥
− ρ
. Таким образом, в результате выполнения описан-
ного алгоритма получено приближенное решение L экземпляра 'I с отношени-
ем аппроксимации
1
( )
2
φ ρ =
− ρ
. Ясно, что всегда
1
( 1)
2
> ρ ρ <
− ρ
.
Теорема 4. Если для задачи 3Max E CSP P− − существует полиномиальный
оптимальный (пороговый) ρ -приближенный алгоритм, а для задачи
3Ins Max E CSP P− − − (реоптимизация 3Max E CSP P− − ) существует полино-
миальный γ -приближенный алгоритм, то ( )γ ≤ φ ρ .
Доказательство. Пусть I − экземпляр задачи 3Max E CSP P− − , с множест-
вом ограничений Ε и *L – оптимальное решение I *( ( ) ( ))
L
val I val I= . К системе
добавляется ограничение ' ( ', )e S P= , где ' [ ]kS n∈ , в результате получаем экзем-
пляр 'I проблемы 3Ins Max E CSP P− − − , пусть *
'IL его оптимальное реше-
ние *
'
( ( ') ( '))
IL
val I val I= . Пусть L решение проблемы 3Ins Max E CSP P− − − ,
полученное в результате алгоритма из доказательства теоремы 3. Решение L –
лучше (больше по значению целевой функции) из решений *L и ( [ ], 8)iL i l l∈ < ,
оно получается полиномиальным приближенным алгоритмом с отношением
аппроксимации
1
( )
2
φ ρ =
− ρ
. Доказательство проведем от противного. Пусть
( )γ > φ ρ и *ρ − такое, что *( )φ ρ = γ . Поскольку функция ( )φ ρ возрастающая по
О ПОРОГЕ ОТНОШЕНИЯ АППРОКСИМАЦИИ ДЛЯ РЕОПТИМИЗАЦИИ ОБОБЩЕННОЙ ЗАДАЧИ…
Компьютерная математика. 2012, № 2 163
ρ и *( ) ( )φ ρ = γ > φ ρ , то отсюда следует, что *ρ > ρ . А это противоречит тому
факту, что для проблемы 3Max E CSP P− − существует полиномиальный опти-
мальный (пороговый) ρ -приближенный алгоритм (т. е. для получения решения
iL должен применяться полиномиальный алгоритм с отношением аппроксима-
ции *ρ большим чем ρ , что невозможно).
Теорема 5. Если для проблемы 3Max E CSP P− − существует полиномиаль-
ный оптимальный (пороговый) ρ -приближенный алгоритм, то для проблемы
3Ins Max E CSP P− − − (реоптимизация 3Max E CSP P− − ) существует полино-
миальный оптимальный (пороговый) ( )φ ρ -приближенный алгоритм,
где
1
( )
2
φ ρ =
− ρ
.
Доказательство следует из теорем 3 и 4.
Теорема 6. Предположим, что имеет место уникальная игровая гипотеза
(UGC). Тогда для проблемы 3Ins Max E CSP EQUAL− − − (реоптимизация
3Max E CSP EQUAL− − ) существует полиномиальный оптимальный (порого-
вый) ( )EQUφ α -приближенный алгоритм, где
1
( ) 0.831.
2EQU
EQU
φ α = ≈
− α
Доказательство следует из теоремы 5 и следствия, если положить
EQUρ = α , т. е. применить для решения 3Max E CSP EQUAL− − алгоритм из
теоремы 1.
Заключение. В данной работе явно определено численное значение (0.831)
порогового отношения аппроксимации для задачи 3Ins Max E CSP EQUAL− − − ,
что стало возможным благодаря новым результатам по оптимальным разбиени-
ям пространства Гаусса [11] . Также заметим, что предикат EQUAL не является
аппроксимационно-устойчивым [10] и поэтому результаты работы [8] к нему не
применимы.
В.О. Михайлюк
ПРО ПОРІГ ВІДНОШЕННЯ АПРОКСИМАЦІЇ ДЛЯ РЕОПТИМІЗАЦІЇ ЗАДАЧІ
ПРО УЗАГАЛЬНЕНУ ВИКОНУВАНІСТЬ З ПРЕДИКАТОМ РОЗМІРНОСТІ 3
При виконанні унікальної ігрової гіпотези (UGC) для задачі 3Ins Max E CSP EQUAL− − −
(реоптимізація 3Max E CSP EQUAL− − при добавленні одного обмеження) існує
поліноміальний оптимальний (пороговий) ( )EQUφ α -наближений алгоритм, де 0.796EQUα ≈
В.А. МИХАЙЛЮК
164 Компьютерная математика. 2012, № 2
порогове відношення апроксимації 3Max E CSP EQUAL− − і
( ) 1 / (2 ) 0.831EQU EQUφ α = − α ≈ .
V.A. Mikhailyuk
ON THE THRESHOLD OF APPROXIMATION RATIO FOR REOPTIMIZATION
OF CONSTRAINT SATISFACTION PROBLEM WITH PREDICATE OF ARITY 3
If the unique games conjecture (UGC) is true, for the problem 3Ins Max E CSP EQUAL− − − ( reop-
timization of 3Max E CSP EQUAL− − under insertion of one constraint) polynomial optimal (thre-
shold) ( )EQUφ α - approximation algorithm exists, where 0.796EQUα ≈ is the threshold approxi-
mation ratio of 3Max E CSP EQUAL− − and ( ) 1 / (2 ) 0.831EQU EQUφ α = − α ≈ .
1. Hastad J. Some optimal inapproximability results // J. of the ACM. – 2001. – 48, N 4.–
P. 798–859.
2. Khot S. On the power of unique 2-prover 1-round games// In Proc. ACM Symposium on the
Theory of Computing (STOC). – 2002. – P. 767–775.
3. Khot S., Regev O. Vertex cover might be hard to approximate to within 2 − ε // J. Comput.
Syst. Sci. – 2008. – 74(3). – P. 335–349.
4. Raghavendra P. Optimal algorithms and inapproximability results for every csp? // In STOC. –
2008. – P. 245 – 254.
5. Bockenhauer H.J, Hromkovic J., Momke T. and Widmayer P. On the hardness of reoptimiza-
tion // Lect. Notes Comput. Sci. – 2008. – Springer: Berlin. – 4910. – P. 50 – 65.
6. Ausiello G., Bonifaci V. and Escoffier B. Complexity and approximation in reoptimization //
Computability in Context: Computation and Logic in the Real World (ed. S. Barry Cooper and
Andrea Sorbi). – 2011. – London: Imperial College Press. – P. 101 – 130.
7. Михайлюк В.А. Реоптимизация упорядоченных обобщенных задач о выполнимости//
Проблемы управления и информатики. – 2012. – № 3. – С. 56 – 65.
8. Михайлюк В.А., Сергиенко И.В. Реоптимизация обобщенных проблем о выполнимости с
аппроксимационно-устойчивыми предикатами // Кибернетика и системный анализ. –
2012 . – № 1. – С. 89 – 104.
9. Сергієнко І.В., Михайлюк В.О. Реоптимізація проблем про узагальнену виконуваність з
предикатами розмірності 2 // Доповіді НАН України. – 2012. – № 6 . – С. 39 – 46.
10. Zwick U. Approximation algorithms for constraint satisfaction problems involving at most
three variables per constraint // In Proc. of the Ninth Annual ACM/SIGACT-SIAM Sympo-
sium on Discrete Algorithms (SODA). – 1998. – P. 201 – 210.
11. De A., Mossel E. Explicit optimal hardness via Gaussian stability results // Electronic Collo-
quium on Computational Complexity. – 2012. – Report N 16.
12. Arora S., Lund C., Motwan R., Sudan M. and Szegedy M. Proof verification and intractabili-
ty of approximation problems // J. of the ACM. – 1998. – 45, N 3. – P. 501 – 555.
Получено 19.09.2012
Об авторе:
Михайлюк Виктор Алексеевич,
кандидат физико-математических наук, доцент,
докторант Института кибернетики имени В.М. Глушкова НАН Украины.
e-mail: mikhailyukvictor2@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-84720 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T16:14:18Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2015-07-13T16:01:55Z 2015-07-13T16:01:55Z 2012 О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84720 519.854 При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3CSP - EQUAL и Φ(αEQU ) = 1 / (2 - αEQU ) ≈ 0.831 . При виконанні унікальної ігрової гіпотези (UGC) для задачі Ins - Max - E3CSP - EQUAL (реоптимізація Max - E3CSP - EQUAL при добавленні одного обмеження) існує поліноміальний оптимальний (пороговий) Φ(αEQU ) -наближений алгоритм, де αEQU ≈ 0.796 порогове відношення апроксимації Max - E3CSP - EQUAL і Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831. If the unique games conjecture (UGC) is true, for the problem Ins - Max - E3CSP - EQUAL ( reoptimization of Max - E3CSP - EQUAL under insertion of one constraint) polynomial optimal (threshold) Φ(αEQU ) - approximation algorithm exists, where aEQU ≈ 0.796 is the threshold approximation ratio of Max - E3CSP - EQUAL and Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 Про поріг відношення апроксимації для реоптимізації задачі про узагальнену виконуваність з предикатом розмірності 3 On the threshold of approximation ratio for reoptimization of constraint satisfaction problem with predicate of arity 3 Article published earlier |
| spellingShingle | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 Михайлюк, В.А. Теория и методы оптимизации |
| title | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_alt | Про поріг відношення апроксимації для реоптимізації задачі про узагальнену виконуваність з предикатом розмірності 3 On the threshold of approximation ratio for reoptimization of constraint satisfaction problem with predicate of arity 3 |
| title_full | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_fullStr | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_full_unstemmed | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_short | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_sort | о пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84720 |
| work_keys_str_mv | AT mihailûkva oporogeotnošeniâapproksimaciiobobŝennoizadačiovypolnimostispredikatomrazmernosti3 AT mihailûkva proporígvídnošennâaproksimacíídlâreoptimízacíízadačíprouzagalʹnenuvikonuvanístʹzpredikatomrozmírností3 AT mihailûkva onthethresholdofapproximationratioforreoptimizationofconstraintsatisfactionproblemwithpredicateofarity3 |