Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа

За наближеного розв’язання дискретних задач оптимізації виникає така iдея: чи можна, виходячи з інформації про оптимальний розв’язок екземпляра задачі (або близького до нього), використовувати цю інформацію для знаходження оптимального (або близького до нього) розв’язку екземпляра задачі, отриманого...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Михайлюк, В.О.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2013
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Методи оптимізації, оптимальне управління і теорія ігор
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50019
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа / В.О. Михайлюк // Систем. дослідж. та інформ. технології. — 2013. — № 1. — С. 79-86. — Бібліогр.: 10 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50019
record_format	dspace
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор
spellingShingle	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор Михайлюк, В.О. Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа Системні дослідження та інформаційні технології
description	За наближеного розв’язання дискретних задач оптимізації виникає така 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дношення також називають пороговим або оптимальним). Складність алгоритмів оцінюється кількістю звернень (запитів) до спеціального оракулу. Для реоптимізації задачі про мінімальне вершинне покриття графа (за добавлення однієї вершини і деякої множини ребер) отриманий (3/2)-наближений алгоритм із адитивною помилкою з сублінійною (константною) складністю. Показано, що відношення апроксимації 3/2 є пороговим у класі алгоритмів із константною складністю.
format	Article
author	Михайлюк, В.О.
author_facet	Михайлюк, В.О.
author_sort	Михайлюк, В.О.
title	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
title_short	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
title_full	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
title_fullStr	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
title_full_unstemmed	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
title_sort	сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2013
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	http://dspace.nbuv.gov.ua/handle/123456789/50019
citation_txt	Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа / В.О. Михайлюк // Систем. дослідж. та інформ. технології. — 2013. — № 1. — С. 79-86. — Бібліогр.: 10 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT mihajlûkvo sublíníjnijoptimalʹnijnabliženijalgoritmreoptimízacíídlâzadačípromínímalʹneveršinnepokrittâgrafa
first_indexed	2023-10-18T18:13:33Z
last_indexed	2023-10-18T18:13:33Z
_version_	1796143640608768000
spelling	irk-123456789-500192013-10-03T03:10:05Z Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа Михайлюк, В.О. Методи оптимізації, оптимальне управління і теорія ігор За наближеного розв’язання дискретних задач оптимізації виникає така 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дношення також називають пороговим або оптимальним). Складність алгоритмів оцінюється кількістю звернень (запитів) до спеціального оракулу. Для реоптимізації задачі про мінімальне вершинне покриття графа (за добавлення однієї вершини і деякої множини ребер) отриманий (3/2)-наближений алгоритм із адитивною помилкою з сублінійною (константною) складністю. Показано, що відношення апроксимації 3/2 є пороговим у класі алгоритмів із константною складністю. При приближенном решении дискретных задач оптимизации возникает такая идея: можно ли, исходя из информации об оптимальном решении экземпляра задачи (или близкого к нему), использовать эту информацию для нахождения оптимального (или близкого к нему) решения экземпляра задачи, полученного в результате незначительных локальных модификаций исходного экземпляра. Данный подход, названный реоптимизацией, позволяет, например, в некоторых случаях получить лучшее качество приближения (которое определяется как отношение значения приближенного решения к точному и называется отношением аппроксимации) в локально модифицированных экземплярах, чем в исходных. Если для некоторых оптимизационных задач отношение аппроксимации нельзя улучшить (например, в классе всех приближенных алгоритмов с полиномиальной сложностью), то такое отношение называют пороговым или оптимальным (алгоритм на котором достигается это отношение также называют пороговым или оптимальным). Сложность алгоритмов оценивается количеством обращений (запросов) к специальному оракулу. Для реоптимизации задачи о минимальном вершинном покрытии графа (при добавлении одной вершины и некоторого множества ребер) получен (3/2)-приближенный алгоритм с аддитивной ошибкой с сублинейной (константной) сложностью. Показано, что отношение аппроксимации 3/2 является пороговым в классе алгоритмов с константной сложностью. With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a result of minor local modifications of the initial instance. This approach, called reoptimization, allows, for example, in some cases, getting the best quality of approximation (which is defined as the ratio between the value of an approximate solution to the exact ratio and called approximation ratio) in locally modified instances than at initials. If for some tasks approximation ratio can not be improved (e.g. in class of all approximation algorithms with polynomial complexity), the ratio is called the threshold or optimal (algorithm which achieved this ratio is also called the threshold or optimal). The complexity of the algorithms is estimated by the number of hits (queries) to a special oracle. For reoptimization of minimum vertex cover problem (with addition of one vertex and some set of edges) (3/2)-approximation algorithm with additive error and sublinear (constant) complexity is received. It is shown that the approximation ratio of 3/2 is the threshold in the class of algorithms with constant complexity. 2013 Article Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа / В.О. Михайлюк // Систем. дослідж. та інформ. технології. — 2013. — № 1. — С. 79-86. — Бібліогр.: 10 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50019 519.854 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України

Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа

Репозитарії

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