О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости
Для розв’язання задачі 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| Zusammenfassung: | Для розв’язання задачі 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 |