О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости
Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі. For solving Ins-Λ-C...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207602 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Summary: | Для розв’язання задачі 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.
|
|---|---|
| ISSN: | 0572-2691 |