The domination heuristic for LP-type problems

Simple item page
dc.contributor.authorGalkovskyi, Т.
dc.contributor.authorGartner, B.
dc.contributor.authorRublov, Bohdan
dc.date.accessioned2015-08-12T07:24:28Z
dc.date.available2015-08-12T07:24:28Z
dc.date.issued2008
dc.descriptionДеякі задачі геометричної оптимізації, наприклад пошук найменшого покриваючого еліпса множини точок, можуть бути розв'язані за лінійний час, використовуючи нескладні випадкові (чи складні детерміновані) комбінаторні алгоритми. На практиці ці алгоритми поліпшуються чи заміняються варіантами евристик, що працюють швидше, але теоретичні оцінки часу роботи для них не доведені. У цій статті ми пропонуємо нову прискорюючу евристику, що може бути легко застосована до відомих лінійних алгоритмів, без зменшення їх швидкості у найгіршому випадку. Ми показуємо, що ця евристика може бути визначена для будь-якої задачі з добре відомого класу задач лінійного програмування. Її ефективність на практиці залежить від того, чи можлива, і якщо можлива, то наскільки швидкою виявиться реалізація предиката для конкретної задачі. Ми наводимо результати експериментів, які показують, що для двох задач нова евристика може значно прискорити існуючі реалізації алгоритмів (з бібліотеки геометричних алгоритмів CGAL).uk
dc.description.abstractCertain geometric optimization problems, for example finding the smallest enclosing ellipse of a set of points, can be solved in linear time by simple randomized (or complicated deterministic) combinatorial algorithms. In practice, these algorithms are enhanced or replaced with heuristic variants that are faster but do not come with a theoretical runtime guarantee. In this paper, we introduce a new speed-up heuristic that can easily be integrated into the known lineartime algorithms, without decreasing their worst-case performance. The heuristic can actually be defined for any problem in the well-known abstract class of LP-type problems; its effectiveness in practice depends on whether and how fast the heuristic can be implemented for the specific problem at hand. We provide test results showing that for two concrete problems, the new heuristic may lead to significant speedups compared to state-of-the-art implementations that are available in the Computational Geometry Algorithms Library CGAL.en
dc.identifier.citationGalkovsyi T. The domination Heuristic for LP-type Problems / T. Galkovskyi, B. Gartner, B. Rublyov. // Наукові записки НаУКМА. - 2008. - Т. 86 : Комп'ютерні науки. - С. 4-10.uk
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/6003
dc.language.isoenen
dc.statuspublished earlieruk
dc.subjectgeometric optimizationen
dc.subjectcombinatorial algorithmsen
dc.subjectheuristicen
dc.subjectarticleen
dc.titleThe domination heuristic for LP-type problemsen
dc.title.alternativeЕвристика переваги для задач лінійного програмуванняuk
dc.typeArticleuk
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Galkovskyi_The_domination_heuristic_for_LP_type.PDF
Size:
334.57 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
086: Комп'ютерні науки