Constrained Clustering Problems and Parity Games

Abstract

Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. We study several clustering objectives. We begin with studying the Euclidean <em>k</em>-center problem. The <em>k</em>-center problem is a classical combinatorial optimization problem which asks to select <em>k</em> centers and assign each input point in a set <em>P</em> to one of the centers, such that the maximum distance of any input point to its assigned center is minimized. The Euclidean <em>k</em>-center problem assumes that the input set P is a subset of a Euclidean space and that each location in the Euclidean space can be chosen as a center. We focus on the special case with <em>k</em> = 1, the smallest enclosing ball problem: given a set of points in m-dimensional Euclidean space, find the smallest sphere enclosing all the points. We combine known results about convex optimization with structural properties of the smallest enclosing ball to create a new algorithm. We show that on instances with rational coefficients our new algorithm computes the exact center of the optimal solutions and has a worst-case run time that is polynomial in the size of the input. We use the new algorithm to show that we can solve the Euclidean <em>k</em>-center problem in polynomial time for constant <em>k</em> and dimension <em>m</em>.<br /> The general unconstrained clustering problems are mostly very well studied. The <em>k</em>-center problem for example allows for elegant <em>2</em>-approximation algorithms(Gonzalez 1985, Hochbaum,Shmoys 1986). However, the situation becomes significantly more difficult when constraints are added to the problem. We first look at the fair clustering. The fairness constraint is motivated by the fact that the general process of computing a clustering may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters -- especially if the data is already biased.<br /> At NIPS 2017, Chierichetti et al. proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a <em>4</em>-approximation algorithm for the fair <em>k</em>-center problem and an <em>O(t)</em>-approximation algorithm for the fair <em>k</em>-median problem, where <em>t</em> is a parameter for the fairness model. For multiple protected classes, the best known result is a <em>14</em>-approximation algorithm for fair <em>k</em>-center (Rösner, Schmidt 2018).<br /> We extend and improve the known results. Firstly, we give a <em>5</em>-approximation algorithm for the fair <em>k</em>-center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximation algorithms for the fair version of all of the classical clustering objectives (<em>k</em>-center, <em>k</em>-supplier, <em>k</em>-median, <em>k</em>-means and facility location). The latter approximation algorithms are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where for example the centers are already fixed.<br /> The second clustering constraint we study is privacy: Here, we are asked to only open a center when at least <em>l</em> points will be assigned to it. We raise the question whether a general method can be derived to turn an approximation algorithm for a clustering problem with some constraints into an approximation algorithm that additionally respects privacy. We show how to combine privacy with several other constraints and obtain approximation algorithms for the <em>k</em>-center problem with several combinations of constraints.<br /> In this dissertation we also study parity games, a two player game played on a directed graph. We study the case in which one of the two players controls only a small number <em>k</em> of nodes and the other player controls the <em>n-k</em> other nodes of the game. Our main result is a fixed-parameter-tractable algorithm that solves bipartite parity games in time <em>k^{O(sqrt{k})} O(n^3)</em>, and general parity games in time <em>(p+k)^{O(sqrt{k})} O(pnm)</em>, where <em>p</em> is the number of distinct priorities and <em>m</em> is the number of edges. For all games with <em>k = o(n)</em> this improves the previously fastest algorithm by Jurdziński, Paterson, and Zwick (2008).<br /> We also obtain novel kernelization results and an improved deterministic algorithm for parity games on graphs with small average node-degree.