Fixed-parameter tractability for geometric optimization problems

点击翻译按钮获取中文摘要

Many real-world problems can be formulated as geometric optimization problems. These are combinatorial optimization problems restricted to a geometric setting, where the objective is to maximize or minimize a function of a number of variables subject to a large number of constraints induced by a given collection of geometric input objects. These include, for example, problems on geometric graphs, geometric packing and covering, robot motion planning, and geometric pattern analysis.We propose to systematically study the parameterized complexity of computationally hard (NP-hard) geometric optimization problems. So far, the main approach for dealing with such problems has been approximation algorithms. However, such algorithms often have prohibitively high running times even for small error sizes while many geometric problems have been shown to be inapproximable. Parameterized complexity on the other hand provides a framework for a more refined, `multi-dimensional' analysis of hard combinatorial problems. It measures their complexity in terms of one or more parameters in addition to the traditional input size. In concrete applications parameters are hoped to take relatively small values, resulting in practical (efficient) algorithms. Geometric problems often come with such parameters, which, in a sense, measure properties of the input objects. In this project, we would like to develop new techniques, especially by combining methods from both fields of parameterized complexity and computational geometry, and use these techniques to tackle concrete fundamental problems from various application areas, such as discrete optimization, pattern analysis, sensor networks, and art galleries.