Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність
Для розв’язання задачi Ins−Λ−CSP (реоптимiзацiя обмеженої Λ−CSP задачi при додаваннi довiльного обмеження) iснує оптимальний наближений алгоритм з адитивною помилкою з константною складнiстю. Вiдношення апроксимацiї алгоритму залежить
 вiд цiлочислового розриву лiнiйної релаксацiї вихiдної з...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85635 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 38–42. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860258082731327488 |
|---|---|
| author | Михайлюк, В.О. |
| author_facet | Михайлюк, В.О. |
| citation_txt | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 38–42. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Для розв’язання задачi Ins−Λ−CSP (реоптимiзацiя обмеженої Λ−CSP задачi при додаваннi довiльного обмеження) iснує оптимальний наближений алгоритм з адитивною помилкою з константною складнiстю. Вiдношення апроксимацiї алгоритму залежить
вiд цiлочислового розриву лiнiйної релаксацiї вихiдної задачi.
Для решения задачи Ins−Λ−CSP (реоптимизация ограниченной Λ−CSP задачи при добавлении произвольного ограничения) существует оптимальный приближенный алгоритм с аддитивной ошибкой с константной сложностью. Отношение аппроксимации алгоритма
зависит от целочисленного разрыва линейной релаксации исходной задачи.
To solve the problem Ins−Λ−CSP (reoptimization of a bounded-degree Λ−CSP problem under the
insertion of an arbitrary constraint), there is an optimal constant-time approximation algorithm
with additive error. The approximation ratio of the algorithm depends on the integral gap of a
linear relaxation of the initial problem.
|
| first_indexed | 2025-12-07T18:51:52Z |
| format | Article |
| fulltext |
УДК 519.854
В.О. Михайлюк
Наближення до оптимальних сублiнiйних алгоритмiв
реоптимiзацiї обмежених задач про узагальнену
виконуванiсть
(Представлено академiком НАН України I. В. Сергiєнком)
Для розв’язання задачi Ins−Λ−CSP (реоптимiзацiя обмеженої Λ−CSP задачi при до-
даваннi довiльного обмеження) iснує оптимальний наближений алгоритм з адитивною
помилкою з константною складнiстю. Вiдношення апроксимацiї алгоритму залежить
вiд цiлочислового розриву лiнiйної релаксацiї вихiдної задачi.
Теоретичнi дослiдження алгоритмiв сублiнiйної складностi є новим роздiлом теоретичної
iнформатики, що iнтенсивно розвивається. Вони виникли внаслiдок необхiдностi обробки
величезних масивiв iнформацiї, що має мiсце в багатьох застосуваннях. Фiнансовi операцiї
з мiльярдами вхiдних даних, аналiз iнтернет-трафiку є прикладами сучасних наборiв даних
величезного обсягу. Аналiз та керування такими даними змусили переглянути традицiйнi
поняття ефективних алгоритмiв обробки iнформацiї. Ранiше пiд такими алгоритмами ро-
зумiли алгоритми полiномiальної складностi вiд n (розмiрностi задачi). Зараз навiть лiнiйнi
алгоритми можуть бути занадто повiльними. Таким чином, доцiльною є розробка не тiльки
полiномiальних алгоритмiв, а й сублiнiйних вiд n.
Говоритимемо, що алгоритм має сублiнiйну складнiсть, якщо час його роботи оцiнюється
величиною o(n), де n — розмiрнiсть входу. Для того щоб сублiнiйний алгоритм був точним,
необхiдно, щоб вiн використовував паралельну або некласичну обробку даних або врахову-
вав спецiальнi обмеження на вхiднi данi (наприклад, логарифмiчний бiнарний пошук у вiд-
сортованих масивах). Iнакше такий алгоритм не в змозi прочитати весь вхiд, щоб забезпе-
чити деякий результат роботи. Тому сублiнiйнi алгоритми повиннi видавати результат без
читання всього входу, а мати доступ до нього тiльки деякими обмеженими порцiями i бути
випадковими, видаючи тiльки наближенi розв’язки. Ефективнiсть таких алгоритмiв вимi-
рюється так званою складнiстю запитiв (query complexity) — кiлькiстю доступiв до деякого
оракулу, що обробляє вхiд (порцiями). Сублiнiйнi алгоритми знайшли широке застосуван-
ня в роздiлi теоретичної iнформатики, який називається “перевiрка властивостей проблем”
(property testing) [1]. Перевiрка властивостей проблем (релаксацiя проблем розпiзнавання)
пов’язана з розробкою сублiнiйних алгоритмiв, що розрiзняють об’єкти iз заданою власти-
вiстю вiд об’єктiв, далеких вiд неї (ε-далекi, ε-far). Наприклад, для задач теорiї графiв
з n вершинами i обмеженим степенем вершин d властивiсть “бути ε-далекими вiд деякої
властивостi P” означає: треба додати або видалити щонайменше εdn ребер, щоб граф мав
цю властивiсть P. Сублiнiйнi алгоритми перевiрки властивостей (тестери) знайшли своє
застосування в теорiї навчання i теорiї наближення [1].
При розв’язаннi дискретних задач оптимiзацiї виникла iдея використання iнформацiї
про оптимальний (або близький до нього) розв’язок екземпляра проблеми для знаходження
© В. О. Михайлюк, 2013
38 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №4
оптимального (або близького до нього) розв’язку екземпляра проблеми, одержаного в ре-
зультатi незначних локальних модифiкацiй вихiдного екземпляра. Даний пiдхiд, названий
реоптимiзацiєю (i вперше запропонований в [2]), дозволяє в деяких випадках отримати,
наприклад, кращу якiсть наближення (воно визначається як вiдношення наближеного зна-
чення цiльової функцiї до оптимального i називається вiдношенням апроксимацiї) в локаль-
но модифiкованих екземплярах, нiж у вихiдних. Якщо для деяких оптимiзацiйних задач
вiдношення апроксимацiї не можна покращити (наприклад, для класу всiх наближених
алгоритмiв з полiномiальною складнiстю), то таке вiдношення називають пороговим або
оптимальним (алгоритм, на якому досягається це вiдношення, також називають пороговим
або оптимальним). У [3] вдалося одержати точне значення порогового вiдношення апрокси-
мацiї для реоптимiзацiї узагальнених проблем про виконуванiсть спецiального класу для
алгоритмiв полiномiальної складностi. У данiй роботi це питання вивчається для реопти-
мiзацiї проблем про узагальнену виконуванiсть у класi сублiнiйних алгоритмiв, зокрема
константної складностi.
Основнi означення. В роботi [4] пропонується наближений алгоритм з константною
складнiстю для розв’язання задач про узагальнену виконуванiсть з обмеженим степенем
(обмеженi Λ−CSP задачi). Час роботи цього алгоритму не залежить вiд розмiрностi ек-
земплярiв задачi. Вивчаються задачi з обмеженим степенем (bounded-degree model). У цiй
моделi число символiв в алфавiтi, максимальна розмiрнiсть (число входiв предикатiв), мак-
симальний степiнь (число обмежень, де зустрiчається кожна змiнна) i максимальна вага
обмежень оцiнюються зверху константами, що не залежать вiд n. Нехай I — екземпляр та-
кої Λ−CSP задачi. Оскiльки алгоритм з константною складнiстю не може прочитати весь
вхiд I, припускаємо iснування оракула OI , який дає iнформацiю про I. Вказуючи значен-
ня змiнної v та iндексу i, OI видає i-те обмеження P , де зустрiчається v. Ефективнiсть
алгоритму вимiрюється числом звернень до оракула OI , яке називається складнiстю за-
питiв (query complexity). У [4] отримано результат, аналогiчний [5]: для кожної обмеженої
Λ−CSP задачi релаксацiя лiнiйного програмування (LP) разом з деяким алгоритмом окру-
глення видає найкраще наближення серед всiх алгоритмiв з константною складнiстю. При
цьому результат є безумовним (не використовується унiкальна iгрова гiпотеза, UGC [6]).
Для формального подання результатiв наведемо деякi означення.
Для цiлого k[k] позначає множину {1, . . . , k}. Розмiрнiстю предиката P : [q]k → {0, 1}
є число входiв P , тобто в даному випадку k. Степiнь змiнної — це число обмежень, де вона
зустрiчається. Для обмеження P в CSP екземплярi V (P ) позначає множину змiнних у P .
Нехай β — вектор або множина, iндексована елементами з множини V . Для пiдмножини
S ⊆ V визначимо β|S = {βv}v∈S .
Означення 1. Задача про узагальнену виконуванiсть з обмеженим степенем (обмеже-
на Λ−CSP задача) визначається так: Λ = ([q], s, t, w,Π), де [q] = {1, . . . , q} — скiнченна
область; s — максимальна розмiрнiсть предикатiв; t — максимальний степiнь змiнних (чис-
ло обмежень, де зустрiчається змiнна); w — максимальна вага предикатiв i Π = {P : [q]k →
→ {0, 1} | k 6 s} — множина предикатiв.
Означення 2. Екземпляр I обмеженої Λ−CSP задачi визначається як
I = (V, S, PS , w),
де V = {v1, . . . , vn} — множина змiнних iз значеннями з [q]; PS — множина обме-
жень, що складається з предикатiв P ∈ Π, якi застосовуються до послiдовностi S змiн-
них V розмiром не бiльше s. Бiльш точно, коли предикат P застосовується до послiдовностi
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №4 39
S = {i1, . . . , ik} ⊆ [n]k, то P вибирає змiннi V|S = {vi1 , . . . , vik} як вхiднi; w є множиною ваг
{wP }P∈PS
, приписаних до кожного обмеження P ∈ PS , де 1 6 wP 6 w.
Задача полягає у знаходженнi приписування змiнним β ∈ [q]V , що максимiзує загальну
вагу виконаних обмежень, тобто
∑
P∈PS
wPP (β). Будемо вважати, що q, s, t, w обмеженi
i не залежать вiд розмiрностi задачi n.
Означення 3. У задачi про узагальнену виконуванiсть з обмеженим степенем Λ i мно-
жиною змiнних V (обмеженiй Λ−CSP задачi) екземпляр I = (V, S, PS , w) подається ораку-
лом OI , таким, що OI за двома числами v ∈ V , i ∈ [t] видає P ∈ PS , P є i-м обмеженням, де
знаходиться v. Якщо таких обмежень не iснує, то вiн видає деякий спецiальний символ ⊥.
Складнiстю запитiв алгоритму (query complexity) є число звернень до OI .
У [4] наводиться релаксацiя лiнiйного програмування (LP релаксацiя) для обмеженої
Λ−CSP задачi, яку назвемо BasicLP. Нехай lp(I) та opt(I) — вiдповiдно значення цiльової
функцiї для оптимального розв’язку LP релаксацiї BasicLP екземпляра I та екземпляра I,
а val(I, β) — значення, отримане приписуванням β ∈ [q]V . Нехай wI є сума всiх ваг обмежень
з I. Визначимо lp(I) = lp(I)/wI , opt(I) = opt(I)/wI i val(I, β) = val(I, β)/wI , а також криву
цiлочислового розриву i цiлочисловий розрив LP релаксацiї Λ−CSP задачi як SΛ(c) =
= inf
I∈Λ,lp(I)>c
{opt(I)} i αΛ = inf
I∈Λ
{opt(I)/lp(I)}.
Означення 4. Значення x будемо називати (α, β)-наближенням x∗, якщо αx∗ − β 6
6 x 6 x∗. Алгоритм називається (α, β)-наближеним алгоритмом для Λ−CSP задачi, якщо
для довiльного екземпляра I вiн обчислює (α, β)-наближення до opt(I) з ймовiрнiстю, не
меншою, нiж 2/3.
Теорема 1 [4]. Для довiльної обмеженої Λ−CSP задачi i ε > 0 iснує алгоритм, який
для екземпляра I з n змiнними i lp(I) = c ∈ (0, 1] з ймовiрнiстю, не меншою, нiж 2/3,
видає значення x, таке, що SΛ(c − ε)wI − εn 6 x 6 opt(I). Для деякого фiксованого при-
писування β, такого, що SΛ(c − ε)wI − εn 6 val(I, β) 6 opt(I) для даної змiнної v з I
обчислює βv за константний час.
Маємо такий результат з безумовної неапроксимованостi.
Теорема 2 [4]. Для довiльних обмеженої Λ−CSP задачi, c ∈ [0, 1] i ε > 0 iснує δ > 0,
таке, що будь-який алгоритм для екземпляра I з n змiнними i opt(I) = c ∈ [0, 1], який
з ймовiрнiстю, не меншою, нiж 2/3, видає значення x, таке, що (SΛ(c) + ε)wI − δn 6 x 6
6 opt(I), вимагає Ω
(√
n
)
запитiв.
Використовуючи алгоритм з теореми 1 для екземпляра I, можна вiдрiзнити випадок
opt(I) > cwI вiд випадку opt(I) 6 SΛ(c − ε)wI − εn. Навпаки, теорема 2 стверджує, що не
можна вiдрiзнити випадок opt(I) > cwI вiд випадку opt(I) 6 (SΛ(c)+ ε)wI − δn з констант-
ною складнiстю.
Оптимальнi наближенi алгоритми з константною складнiстю для обмежених
Λ−CSP задач. Використовуючи визначення SΛ(c), αΛ, означення 4 та теореми 1 i 2, отри-
маємо такий наслiдок.
Наслiдок 1. Для довiльної обмеженої Λ−CSP задачi i ε > 0 iснує (αΛ − ε, εn)-на-
ближений алгоритм з константною складнiстю. З iншого боку, для довiльної обмеженої
Λ−CSP задачi i ε > 0 iснує δ > 0 таке, що довiльний (αΛ + ε, δn)-наближений алгоритм
вимагає Ω
(√
n
)
запитiв.
Означення 5. Говоритимемо, що для довiльної обмеженої Λ−CSP задачi iснує опти-
мальний (α, εn)-наближений алгоритм з константною складнiстю, якщо виконуються такi
умови:
40 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №4
для Λ−CSP задачi i будь-якого ε > 0 iснує (α−ε, εn)-наближений алгоритм з констант-
ною складнiстю;
для довiльного ε > 0 iснує таке δ > 0, що для будь-якої Λ−CSP задачi не iснує (α +
+ ε, δn)-наближеного алгоритму з константною складнiстю.
При цьому α називається порогом вiдношення апроксимацiї наближеного алгоритму,
а сам алгоритм — оптимальним α-наближеним алгоритмом з адитивною помилкою з кон-
стантною складнiстю.
Використовуючи наслiдок 1 i означення 5, маємо
Наслiдок 2. Для довiльної обмеженої Λ−CSP задачi i ε > 0 iснує оптимальний
(αΛ, εn)-наближений алгоритм з константною складнiстю.
Реоптимiзацiя обмежених Λ−CSP задач. Порiг вiдношення апроксимацiї. Ви-
значимо реоптимiзацiйний варiант обмеженої Λ−CSP задачi. Нехай I = (V, S, PS , w) —
екземпляр Λ−CSP задачi. Будемо вважати, що wP = 1 для довiльного P ∈ PS . Екземпляр
I ′ = (V, S′, PS′ , w) отримується з I таким чином: S′ = S
⋃{i′1, . . . , i′k}, де {i′1, . . . , i′k} ⊆ [n]k
при деякому k 6 s.
Задача Ins−Λ−CSP . Вхiднi данi. Довiльний екземпляр IΛ−CSP задачi, x∗ — опти-
мальний розв’язок екземпляра I.
Результат. Знайти оптимальний розв’язок екземпляра I ′ (отриманого з I, як описано
вище) Λ−CSP задачi, використовуючи x∗.
Мета. Знайти x, яке максимiзує число виконаних обмежень екземпляра I ′.
Теорема 3. Якщо для довiльної обмеженої Λ−CSP задачi i ε > 0 iснує (ρ − ε, εn)-на-
ближений алгоритм з константною складнiстю, то для задачi Ins−Λ−CSP iснує (ϕ(ρ)−
− ε1, ε1n) такий же алгоритм, де ϕ(ρ) = 1/(2 − ρ) i ε1 = εϕ(ρ).
Теорема 4. Нехай A — це будь-який (γ− ε, εn)-наближений алгоритм з константною
складнiстю для задачi Ins−Λ−CSP , тодi γ 6 ϕ(αΛ).
Використовуючи теореми 3 i 4, отримаємо основний результат.
Теорема 5. Для задачi Ins−Λ−CSP i ε1 > 0 iснує оптимальний (ϕ(αΛ), ε1n)-набли-
жений алгоритм з константною складнiстю.
Таким чином, для задачi Ins−Λ−CSP iснує оптимальний ϕ(αΛ)-наближений алгоритм
з адитивною помилкою з константною складнiстю.
Приклад застосування. Розглянемо задачу Max-3-Sat, що є варiантом обмеженої
Λ−CSP задачi, коли множина предикатiв Π становить диз’юнкцiю не бiльше трьох лiтера-
лiв. Щоб застосувати теорему 5, треба знайти цiлочисловий розрив αΛ LP релаксацiї задачi
Max-3-Sat. Верхня оцiнка (7/8) для αΛ випливає з застосування алгоритму з теореми 1
(i наслiдку 2).
Важливим є отримання нижнiх оцiнок цiлочислового розриву. Безумовна нижня оцiнка
для αΛ в класi алгоритмiв константної складностi одержана для Max-3-Sat в [7]. Зокрема,
має мiсце твердження.
Теорема 6 [7]. Для довiльного ε > 0 кожний (7/8 + ε)-наближений алгоритм для
Max-3-Sat має складнiсть запитiв Ω(n + m), де n — число змiнних, а m — число диз’юн-
кцiй. Теорема залишається справедливою i для спецiального випадку, коли кожна змiнна
зустрiчається в O(1) диз’юнкцiях i m = O(n).
Отже, для задачi Max-3-Sat αΛ = 7/8, ϕ(αΛ) = 8/9 i, застосувавши теорему 5, отримаємо
твердження.
Теорема 7. Для задачi Ins-Max-3-Sat iснує оптимальний (8/9)-наближений алго-
ритм з адитивною помилкою з константною складнiстю.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №4 41
Таким чином, результати цiєї роботи є безумовними. Вони не залежать нi вiд iстинностi
унiкальної iгрової гiпотези UGC [6], нi вiд загальноприйнятої гiпотези теорiї складностi
обчислень P 6= NP .
1. Goldreich O., Goldwasser S., Ron D. Property testing and its connection to learning and approximation
abstract // Journal of the ACM. – 1998. – 45, Nо 4. – P. 653–750.
2. Archetti C., Bertazzi L., Speranza M.G. Reoptimizing the travelling salesman problem // Networks. –
2003. – 42, No 3. – P. 154–159.
3. Михайлюк В.А., Сергиенко И.В. Реоптимизация обобщенных проблем о выполнимости с аппрокси-
мационно-устойчивыми предикатами // Кибернетика и систем. анализ. – 2012. – 47, № 1. – С. 89–104.
4. Yoshida Y. Optimal costant-time approximation algorithms and (unconditional) inapproximability results
for every bounded-degree CSP // In Proc. ACM Symp. on the Theory of Computing (STOC). – 2011. –
P. 665–674.
5. Raghavendra P. Optimal algorithms and inapproximability results for every csp? // Proc. ACM Symposium
on the Theory of Computing(STOC). – 2008. – P. 245–254.
6. Khot S. On the power of unique 2-prover 1-round games // STOC. – 2002. – P. 767–775.
7. Bogdanov A., Obata K., Trevisan L. A lower bound for testing 3-colorability in bounded-degree graphs //
Proc. of IEEE Symp. on Foundations of Computer Science (FOCS). – 2002. – P. 93–102.
Надiйшло до редакцiї 17.07.2012Iнститут кiбернетики iм. В.М. Глушкова
НАН України, Київ
В.A. Михайлюк
Приближение к оптимальным сублинейным алгоритмам
реоптимизации ограниченных задач об обобщенной выполнимости
Для решения задачи Ins−Λ−CSP (реоптимизация ограниченной Λ−CSP задачи при до-
бавлении произвольного ограничения) существует оптимальный приближенный алгоритм
с аддитивной ошибкой с константной сложностью. Отношение аппроксимации алгоритма
зависит от целочисленного разрыва линейной релаксации исходной задачи.
V.A. Mikhailyuk
Approximation to the optimal sublinear algorithms for the
reoptimization of bounded-degree problems of a general feasibiliity
To solve the problem Ins−Λ−CSP (reoptimization of a bounded-degree Λ−CSP problem under the
insertion of an arbitrary constraint), there is an optimal constant-time approximation algorithm
with additive error. The approximation ratio of the algorithm depends on the integral gap of a
linear relaxation of the initial problem.
42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №4
|
| id | nasplib_isofts_kiev_ua-123456789-85635 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:51:52Z |
| publishDate | 2013 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.О. 2015-08-11T13:11:01Z 2015-08-11T13:11:01Z 2013 Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 38–42. — Бібліогр.: 7 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/85635 519.854 Для розв’язання задачi Ins−Λ−CSP (реоптимiзацiя обмеженої Λ−CSP задачi при додаваннi довiльного обмеження) iснує оптимальний наближений алгоритм з адитивною помилкою з константною складнiстю. Вiдношення апроксимацiї алгоритму залежить
 вiд цiлочислового розриву лiнiйної релаксацiї вихiдної задачi. Для решения задачи Ins−Λ−CSP (реоптимизация ограниченной Λ−CSP задачи при добавлении произвольного ограничения) существует оптимальный приближенный алгоритм с аддитивной ошибкой с константной сложностью. Отношение аппроксимации алгоритма
 зависит от целочисленного разрыва линейной релаксации исходной задачи. To solve the problem Ins−Λ−CSP (reoptimization of a bounded-degree Λ−CSP problem under the
 insertion of an arbitrary constraint), there is an optimal constant-time approximation algorithm
 with additive error. The approximation ratio of the algorithm depends on the integral gap of a
 linear relaxation of the initial problem. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність Приближение к оптимальным сублинейным алгоритмам реоптимизации ограниченных задач об обобщенной выполнимости Approximation to the optimal sublinear algorithms for the reoptimization of bounded-degree problems of a general feasibiliity Article published earlier |
| spellingShingle | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність Михайлюк, В.О. Інформатика та кібернетика |
| title | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність |
| title_alt | Приближение к оптимальным сублинейным алгоритмам реоптимизации ограниченных задач об обобщенной выполнимости Approximation to the optimal sublinear algorithms for the reoptimization of bounded-degree problems of a general feasibiliity |
| title_full | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність |
| title_fullStr | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність |
| title_full_unstemmed | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність |
| title_short | Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність |
| title_sort | наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85635 |
| work_keys_str_mv | AT mihailûkvo nabližennâdooptimalʹnihsublíníinihalgoritmívreoptimízacííobmeženihzadačprouzagalʹnenuvikonuvanístʹ AT mihailûkvo približeniekoptimalʹnymsublineinymalgoritmamreoptimizaciiograničennyhzadačobobobŝennoivypolnimosti AT mihailûkvo approximationtotheoptimalsublinearalgorithmsforthereoptimizationofboundeddegreeproblemsofageneralfeasibiliity |