Seminar in Discrete Optimization

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.

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.

As part of our work on a standardized interface for exchanging models for gear calculation (www.rexs.info), we have defined a modeling structure for gears. Different component types are available as building blocks (e.g. shafts, bearings, gears). These can be connected to each other via component-specific relations. For example, there is a stage_relation with the roles "stage", "gear 1", "gear 2" for a gear stage or a side_relation that connects a bearing with two other components. Most relations have 2 or 3 roles, or components that connect them. So the model structure resembles a graph. Now it is in most cases so that such a model in the interface format can be imported by different tools and thereby into their internal data structure is transferred which deviates from this modeling structure (at least partly). If the model is exported then again thereby in many cases the Ids of components and relations change. After importing and exporting, certain aspects of the model may be more or less detailed than before (depending on what the tool can do and what it requires). This poses a challenge when you want to compare the two model states. The idea is therefore to create a matching between the two models based on the similarity of the model structure, which identifies related components. In the seminar I would like to describe the REXS modeling system, outline the matching problem and discuss if there are any solutions that could be modified for the concrete problem.

The goal of this project was, assuming both a group of seminars and a group of students give preferences over the agents in the other group they are interested in, to find an homogeneous assignment of participants and seminars which addresses the situation of each seminar and each student as best as possible. This problem is a generalization of the classical Hospitals/Residents Problem, where we allowed indifference in the preference relations of each agent, assigned an arbitrary but fixed number of types to each student (each belonging to a category, e.g. study program, exchange student or not, etc) and were interested in allowing each seminar to state the minimal number of participants they would require to be held. The impact of all these changes was studied and the resulting problem formulated as a Linear Program.

When considering non-symmetric gauges there are several ways to define the diameter of a convex body. These correspond to different symmetrizations of the gauge, i.e., means of the gauge $C$ and $-C$. We study inequalities involving the inradius, circumradius and diameter and present examples and results that confirm that not only does studying the symmetrizations help to understand the diameters better but also the other way around.

In „Ellipsoids of maximal volume in convex bodies“ Keith Ball proved a general bound on the volume of k-dimensional ellipsoids in n-dimensional convex bodies in relation to their John ellipsoid. A stronger bound is known in the symmetric case. Our goal was to connect these results by establishing a bound depending on the John asymmetry s_0. We could prove a tight bound for all k and all asymmetry values s_0 not in (1,1+2/n), and characterize the equality cases.

The clas­sical Brunn-Minkowski inequality in the $n$-dimensional Euclid­ean space asserts th­at the volume (Lebes­gue measure) to the power $1/n$ is a conca­ve functional when dealing with convex bodies (non-empty com­pact convex sets). It quickly yields, am­ong other results, the classical isope­rimetric inequality, which can be summar­ized by saying that the Euclidean balls minimize the surface area measure (Minko­wski content) among those convex bodies with prescribed posi­tive volume. Moreover, it implies the so-called Rogers-Shephard inequality, which provides a sharp upper bound for the volume of the difference set in terms of the volume of the original convex body. There exist various facets of the prev­ious results, due to their different ver­sions, generalizatio­ns, and extensions. In this talk, after recalling the above classical inequalities for the volume, we wi­ll discuss and show certain discrete ana­logues of them for the lattice point enumerator, which gives the number of integer points of a bounded set. Moreover, we will show that these new discrete inequa­lities imply the corresponding classical results for convex bodies. This is about joint works with David Alonso-Gutiérrez (Universidad de Zaragoza), David Iglesias (Universidad de Murcia), Eduardo Lucas (Universidad de Murcia), and Artem Zvavitch (Kent State University).

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another; such a scenario arises, for example, when a gradual transition from an old solution to a new one is required.   Based on linear programming and network theory, we develop methods for the construction of a sequence of so-called elementary moves that accomplishes such a transition. Specifically, we discuss two types of transitions: short transitions with a low number of steps and transitions that retain separation of clusters throughout.

After a short presentation by Andreas Wiese, there will be an open discussion where everyone is invited to participate and give their own input, opinions and ideas on the topic.

Eine bestmögliche Einteilung von Studierenden zu Kursen stellt für viele Algorithmen eine große Herausforderung dar. Dabei sind Eigenschaften wie Strategiesicherheit, Pareto-Effizienz und Fairness schwer einzuhalten. Es haben sich in diesem Zusammenhang zwei bekannte Algorithmen bewährt und sollten bezüglich ihrer Vor- und Nachteile verglichen werden.