Seminar in Discrete Optimization

Upcoming talks

05.03.2024 16:00 Maximilian Gläser: Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation

We investigate linear programming based branch-and-bound using general disjunctions, also known as stabbing planes and derive the first sub-exponential lower bound (i.e., 2^{L^\omega(1)}) in the encoding length L of the integer program for the size of a general branch-and-bound tree. In fact, this is even the first super-linear bound. This is achieved by showing that general branch-and-bound admits quasi-feasible monotone real interpolation. Specialized to a certain infeasible integer program whose infeasibility expresses that no graph can have both a k-coloring and a (k+1)-clique, this property states that any branch-and-bound tree for this program can be turned into a monotone real circuit of similar size which distinguishes between graphs with a k-coloring and graphs with a (k+1)-clique. Thus, we can utilize known lower-bounds for such circuits. Using Hrubeš' and Pudlák's notion of infeasibility certificates, one can show that certain random CNFs are sub-exponentially hard to refute for branch-and-bound with high probability via the same technique. This is joint work with Marc Pfetsch.

Previous talks

27.02.2024 16:00 Marin Varivoda: The Banach-Mazur distance between the cube and the cross-polytope in dimensions three and four

The Banach-Mazur distance is a well-established notion of convex geometry with numerous important applications in the fields like discrete geometry or local theory of Banach spaces. This notion has already been extensively studied by many different authors, but the vast majority of established results are of the asymptotic nature. The non-asymptotic properties of Banach-Mazur distance seem to be quite elusive and even in very small dimensions they are surprisingly difficult to establish. Actually there are rather few situations in which the Banach-Mazur distance between a pair of convex bodies was determined precisely. One example illustrating this difficulty is the case of the cube and the cross-polytope, as their Banach-Mazur distance was known only in the planar case. In this talk we prove that the distance between the cube and the cross-polytope is equal to 9/5 in the dimension three and it is equal to 2 in dimension four.

27.02.2024 16:45 Tomasz Kobos: Planar convex bodies equidistant to all symmetric convex bodies

The n-dimensional simplex is a convex body well-known for its numerous remarkable features and it was studied extensively also from the point of view of the Banach-Mazur distance. Our starting point is the following well-known and interesting property: the n-dimensional simplex is equidistant (in the Banach-Mazur distance) to all symmetric convex bodies with the distance equal to n. Moreover, it is known the simplex is the unique convex body with this property. It is therefore natural to ask if the simplex is the unique convex body that is equidistant to all symmetric convex bodies, but not necessarily with the distance equal to n. We answer this question negatively in the planar case. For all 7/4 < r < 2 we provide a general construction of a family of convex bodies K, which are with the distance r to every symmetric convex body. It should be noted that this distance r coincides with the asymmetry constant of K and the construction is based on some basic properties of the asymmetry constant.

23.01.2024 16:00 Gennadiy Averkov: Plücker-type inequalities for mixed areas and intersection numbers of curve arrangements

Any collection of n compact convex planar sets K_1,…,K_n defines a vector of n over 2 mixed areas V(K_i, K_j) for 1≤i Quelle

09.01.2024 16:00 Florian Grundbacher: p-Means of Convex Bodies and a New Suggestion for the Geometric Mean of Convex Bodies

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.

08.01.2024 17:00 Steffen Borgwardt: Optimal Sites for Least-Squares Assignments

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.

19.12.2023 16:00 Katja Ettmayr: A (3 + ε)-approximation algorithm for the minimum sum of radii problem with outliers

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.

12.12.2023 16:00 Alexander Armbruster: Simpler constant factor approximation algorithms for weighted flow time -- now for any p-norm

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


10.11.2023 15:00 Lola Bermes: Integer programming methods for the Student Course Matching Problem

We study many-to-one matching problems for assigning a set of students to a set of courses according to their preference lists in which they rank the agents from the other set. The agents can also rate several agents of the other set equally or exclude them. Our goal is to find a stable matching that maximizes students’ satisfaction using Integer Programming (IP) methods. The flexibility of these methods becomes apparent by introducing additional conditions on the type of students and/or on the minimum number of students that must attend a course for it to be offered.

12.06.2023 14:00 Kilian Tscharke: Introduction to quantum computing for Mathematicians

Quantum Computing (QC) has witnessed remarkable growth and has garnered significant attention in recent years, often accompanied by strong hype. This introductory talk aims to provide a comprehensive overview of the fundamental concepts in QC and its potential for Mathematicians. The talk begins by explaining the core principles of QC like entanglement and superposition. Furthermore, the talk delves into the mathematical underpinnings of QC, demonstrating how operations on a quantum computer can be elegantly described using linear algebra. This approach enables the manipulation and analysis of quantum states, paving the way for the development of quantum algorithms. As an illustration of the power of quantum computing, the concept of quantum teleportation will be introduced, showcasing the remarkable ability to transmit quantum information using classical channels. The talk also highlights two influential quantum algorithms: Shor's and Grover's algorithm. Shor's algorithm, renowned for its impact on cryptography, presents a polylogarithmic approach to factoring large numbers, thereby threatening conventional encryption methods. On the other hand, Grover's algorithm offers a powerful tool for database search, potentially providing a quadratic speedup compared to classical search algorithms. Lastly, the current state of the art in quantum computing is addressed.

21.03.2023 16:00 Andreas Wiese: How to be productive

Instead of a classical research talk, Andreas Wiese will give a short presentation on the topic "How to be productive". The talk will be followed by an open discussion, where everyone is invited to participate and give their own input, opinions and ideas on the topic.

14.03.2023 16:00 Alexander Armbruster: A PTAS for Minimizing Weighted Flow Time on a Single Machine

An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. We answer this question in the affirmative and present a polynomial time (1 + 𝜀)-approximation algorithm for weighted flow time on a single machine. We use a reduction of the problem to a geometric covering problem, which was introduced in previous approaches and which loses only a factor of 1+𝜀 in the approximation ratio. However, unlike the previous algorithm, we solve the resulting instances of the covering problem exactly, rather than losing a factor 2 + 𝜀. Key for this is to identify and exploit structural properties of instances of that problem covering problem which arise in the reduction from weighted flow time. This talk is based on joint work with Lars Rohwedder and Andreas Wiese.

07.03.2023 16:00 Stefan Kober: Totally Delta-modular IPs on a TU constraint matrix with one additional row

It is a well-known conjecture that integer programs on an integer constraint matrix whose subdeterminants are bounded in absolute value by a constant could be solvable in polynomial time. Despite some recent progress in special cases, the question is still wide open. We consider the special case consisting of a TU constraint matrix with one additional row, which in general encompasses different hard and interesting problems. We present partial progress to the resolution of the question of polynomial solvability of such problems in particular for transposed network matrices. The applied techniques range from Seymour's decomposition of TU matrices over certain types of proximity results for integer programs to graph and minor theory. This is joint work with Manuel Aprile, Samuel Fiorini, Stefan Weltge and Yelena Yuditsky.

For talks not listed above please have a look at the Munich Mathematical Calendar.