The domination heuristic for LP-type problems
dc.contributor.author | Galkovskyi, Т. | |
dc.contributor.author | Gartner, B. | |
dc.contributor.author | Rublov, Bohdan | |
dc.date.accessioned | 2015-08-12T07:24:28Z | |
dc.date.available | 2015-08-12T07:24:28Z | |
dc.date.issued | 2008 | |
dc.description.abstract | Деякі задачі геометричної оптимізації, наприклад пошук найменшого покриваючого еліпса множини точок, можуть бути розв'язані за лінійний час, використовуючи нескладні випадкові (чи складні детерміновані) комбінаторні алгоритми. На практиці ці алгоритми поліпшуються чи заміняються варіантами евристик, що працюють швидше, але теоретичні оцінки часу роботи для них не доведені. У цій статті ми пропонуємо нову прискорюючу евристику, що може бути легко застосована до відомих лінійних алгоритмів, без зменшення їх швидкості у найгіршому випадку. Ми показуємо, що ця евристика може бути визначена для будь-якої задачі з добре відомого класу задач лінійного програмування. Її ефективність на практиці залежить від того, чи можлива, і якщо мож¬ лива, то наскільки швидкою виявиться реалізація предиката для конкретної задачі. Ми наводимо результати експериментів, які показують, що для двох задач нова евристика може значно приско¬ рити існуючі реалізації алгоритмів (з бібліотеки геометричних алгоритмів CGAL). | uk |
dc.identifier.citation | Galkovsyi T. The domination Heuristic for LP-type Problems / T. Galkovskyi, B. Gartner, B. Rublyov. // Наукові записки НаУКМА. - 2008. - Т. 86 : Комп'ютерні науки. - С. 4-10. | uk |
dc.identifier.uri | https://ekmair.ukma.edu.ua/handle/123456789/6003 | |
dc.language.iso | uk | uk |
dc.status | published earlier | uk |
dc.subject | лінійне програмування | uk |
dc.subject | евристика | uk |
dc.subject | геометричні алгоритми | uk |
dc.subject | heuristic | uk |
dc.title | The domination heuristic for LP-type problems | uk |
dc.type | Article | uk |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Galkovskyi_The_domination_heuristic_for_LP_type.PDF
- Size:
- 334.57 KB
- Format:
- Adobe Portable Document Format
- Description:
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 7.54 KB
- Format:
- Item-specific license agreed upon to submission
- Description: