086: Комп'ютерні науки

Permanent URI for this collection

Now showing 1 - 1 of 1

The domination heuristic for LP-type problems
(2008) Galkovskyi, Т.; Gartner, B.; Rublov, Bohdan
Certain 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.