Seminar in Discrete Optimization

In light of the log-Brunn-Minkowski conjecture, various attempts have been made to define the geometric means of convex bodies. Many of these constructions are fairly complex and/or fail to satisfy some natural properties one would expect of such a mean. To improve our understanding of potential geometric mean definitions, we study the closely related p-means of convex bodies, with the usual definition extended to two series ranging over all p in [-∞,∞]. We characterize their equality cases and obtain (in almost all instances tight) inequalities that quantify how well these means approximate each other. Based on our findings, we propose a fairly simple definition of the geometric mean that satisfies the properties considered in recent literature, and discuss potential axiomatic characterizations. Finally, we conclude that some of these properties are incompatible with approaches to proof the log-Brunn-Minkowski conjecture via geometric means.

Least-squares assignments are a common way to partition a data set in clustering applications. While the combined choice of best clusters and representative sites is a known hard problem, linear programming methods and polyhedral theory provide insight into closely related tasks. We show that it is efficient to decide whether a given clustering can be represented as a least-squares assignment, and extend the related algorithm to arrive at soft-margin multiclass support vector machines. Further, we connect the search for optimal sites for a given clustering to volume computations for normal cones of an associated vertex in a certain polyhedron. This leads to new measures for the robustness of clusterings and explains why popular algorithms like k-means work well in practice.

Clustering is a fundamental problem setting with applications in many different areas. For a given set of points in a metric space and an integer k, we seek to partition the given points into k clusters. For each computed cluster, one typically defines one point as the center of the cluster. A natural objective is to minimize the sum of the cluster center’s radii, where we assign the smallest radius r to each center such that each point in the cluster is at a distance of at most r from the center. The best-known polynomial time approximation ratio for this problem is 3.389. In the setting with outliers, i.e., we are given an integer m and allow up to m points that are not in any cluster, the best-known approximation factor is 12.365. In this paper, we improve both approximation ratios to 3 + ε. Our algorithms are primal-dual algorithms that use fundamentally new ideas to compute solutions and to guarantee the claimed approximation ratios. For example, we replace the classical binary search to find the best value of a Lagrangian multiplier λ by a primal-dual routine in which λ is a variable that is raised. Also, we show that for each connected component due to almost tight dual constraints, we can find one single cluster that covers all its points and we bound its cost via a new primal-dual analysis. We remark that our approximation factor of 3 + ε is a natural limit for the known approaches in the literature.

A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The goal is to find a (possibly preemptive) schedule for the jobs in order to minimize the sum of the weighted flow times, where the flow time of a job is the time between its release time and its completion time. It had been a longstanding important open question to find a polynomial time O(1)-approximation algorithm for the problem and this was resolved in a recent line of work. These algorithms are quite complicated and involve for example a reduction to (geometric) covering problems, dynamic programs to solve those, and LP-rounding methods to reduce the running time to a polynomial in the input size. In this paper, we present a much simpler (6+ϵ)-approximation algorithm for the problem that does not use any of these reductions, but which works on the input jobs directly. It even generalizes directly to an O(1)-approximation algorithm for minimizing the p-norm of the jobs' flow times, for any 0

1 only a pseudopolynomial time O(1)-approximation algorithm was known for this variant, and no algorithm for p<1. For the same objective function, we present a very simple QPTAS for the setting of constantly many unrelated machines for 0

Quelle