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.

The research outlined in this proposal is theoretical in nature, nevertheless positive results, i.e., FPT algorithms for our concrete problems--where previously there was none, have the potential for an immediate impact in the respective application areas.

Note that while showing that a problem is in FPT may initially come with an inefficient algorithm (e.g., doubly-exponential or worse), such a result can spawn a race of subsequent more practical algorithms with improved running times, as, for example, in the case of the well-known Vertex Cover problem and its applications on real-world graphs.

We consider now the areas in which our results could have an impact.

Optimization. The Vertex Enumeration problem (P1) finds applications in several areas of mathematical programming and modeling. Vertex enumeration is typically applied when the problem to be modeled can be characterized (or approximated) by a set of linear constraints, but the objective function is either non-linear or linear but unknown. For many cases (e.g., when the objective function is concave), the theory asserts that an optimal solution must occur at a vertex of the polytope defined by the constraints. By enumerating all vertices, one is then able to find the global solution. Thus, an efficient output-sensitive algorithm for vertex enumeration is of significant importance for such problems. Other applications of the Vertex Enumeration problem include global optimization, combinatorial optimization and multi-objective linear programming.

Machine Learning. The point sets separation problem (P3) is motivated by the problem of univariate discretization of continuous variables. In particular, it's two-dimensional version models problem instances with decision tables of two real-valued attributes and a binary decision function. The lines to be found represent cut points which determine a partition of the values into intervals and one opts for a set of cuts that is consistent with the given decision table. In practice, having an exact algorithm that can quickly decide whether a given number of such cuts exist (even for moderate number of cuts) before trying other empirical methods can be of particular help.

Wireless Sensor Networks. Barrier coverage is one of the most important sensor network applications, e.g., in national border control, critical resource protection, security surveillance and intruder detection. The barrier coverage problem we have described in this proposal (P5) models the typical scenario where the sensors have been already deployed and one wants to find the minimum number of sensors that need to be active so that they still form a barrier and the physical space of interest is observed in the requested way. This is particularly important for energy-efficiency purposes as sensor battery resources are limited and thus have a direct impact on the network's lifetime.

Workshop. Towards the end of the project, we would like to host a one-day workshop at Middlesex on its topics. We will invite international researchers and this will be a good opportunity to present our research to the academic community in the UK.