Faster Algorithms for Geometric Clustering and Competitive Facility-Location Problems

Mehran Mehr

first promotor: prof.dr. Mark de Berg (TU/e)
co-promotor: dr.ir. Kevin Buchin (TU/e)
Eindhoven University of Technology
Date: 5 December 2018
Thesis: PDF

Summary

In this thesis we study algorithmic problems related to clustering and competitive facility location of point sets in 2- and higher-dimensional space.

In the geometric clustering problems we consider, we want to partition a given set of points in the plane into a number of clusters, so that a certain cost function is minimized. This cost function could be the sum of radii of the clusters or some other geometric measure.

One of the contributions of the thesis is an algorithm to compute an approximately optimal clustering that works for a large class of cost functions, which we call regular functions. Next we focus on a specific cost function, namely the sum of the perimeters of the clusters. We present the first sub-quadratic algorithm to compute an optimal clustering for this cost function, for the case where the number of clusters is two. We also present an efficient approximation algorithm that is specifically optimized for this cost function and this number of clusters. Our final contribution on geometric clustering problems is the first polynomial-time algorithm to compute an optimal clustering (for the sum-of-perimeters as cost function) where the number of clusters is part of the input.

In the competitive facility-location problems we consider, we are given a set of voters, each represented by a point in a Euclidean space, two numbers k and l, and two players P and Q who want to select k resp. l locations in this Euclidean space in order to win as many voters as possible. More precisely, the game the two players play is as follows. First player P chooses k locations, then player Q chooses l locations. Player Q wins a voter if he owns the closest location to the voter, and otherwise player P wins the voter. Player P wins the game if he can win at least the same number of voters as player Q. We want to develop an algorithm to verify if player P has a winning strategy for the given point set.

We present the first polynomial-time algorithm for the one-dimensional case of this problem. It was already known that this problem is NP-hard in higher dimensions when k and l are part of the input. We narrow down the complexity class of the problem in higher dimensions by showing that it is Sigma_2^P-hard and is contained in exists-forall-R. The latter result also provides an explicit algorithm to solve the problem in polynomial time when k and l are fixed. As a second contribution about competitive facility-location problems, we study the special case when players have exactly one point, that is where k = l =1, with slightly modified tie-breaking rules. For this special case, we provide the first O(n log n) time algorithm to verify if the first player can win the game. We also present an exponential algorithm that solves the problem when the distance is measured in the L_1 norm.

For the special case, where k = l = 1, we also consider the problem when player P does not have a winning strategy. In this case, we consider two different approaches to enable player P win the game, that is either by removing some the voters or by restricting the location of player Q to be in certain fixed radius r from the location of player P. First, we provide an algorithm that computes the minimum number of voters that needs to be ignored so that player P has a winning strategy that works in O(n^4) time. We provide a faster algorithm for this problem when the number of voters that needs to be removed is small. Then, we present an algorithm that solves the problem with restricted locations for player Q efficiently.