О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости
Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі. For solving Ins-Λ-C...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/207602 |
| 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: | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862696864203145216 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі.
For solving Ins-Λ-CSP (reoptimization of Λ-CSP under insertion of one constraint) an optimal approximation algorithm with additive error exists. Approximation ratio of this algorithm depends on the integrality gap of LP relaxation of the initial problem.
|
| first_indexed | 2025-12-07T16:28:11Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-207602 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T16:28:11Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2025-10-10T10:41:32Z 2013 О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207602 519.854 10.1615/JAutomatInfScien.v45.i4.40 Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі. For solving Ins-Λ-CSP (reoptimization of Λ-CSP under insertion of one constraint) an optimal approximation algorithm with additive error exists. Approximation ratio of this algorithm depends on the integrality gap of LP relaxation of the initial problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости Про сублінійні алгоритми реоптимізації для узагальнених задач про виконуваність On Sublinear Algorithms of Reoptimization for Generalized Satisfiability Problems Article published earlier |
| spellingShingle | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости Михайлюк, В.А. Оптимальное управление и методы оптимизации |
| title | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_alt | Про сублінійні алгоритми реоптимізації для узагальнених задач про виконуваність On Sublinear Algorithms of Reoptimization for Generalized Satisfiability Problems |
| title_full | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_fullStr | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_full_unstemmed | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_short | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_sort | о сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207602 |
| work_keys_str_mv | AT mihailûkva osublineinyhalgoritmahreoptimizaciidlâobobŝennyhzadačovypolnimosti AT mihailûkva prosublíníiníalgoritmireoptimízacíídlâuzagalʹnenihzadačprovikonuvanístʹ AT mihailûkva onsublinearalgorithmsofreoptimizationforgeneralizedsatisfiabilityproblems |