Seminar in Discrete Optimization

We study a fair resource scheduling problem, where a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time, deadline, and processing time, such that it can be processed if its complete processing period is between release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.

The Traveling Salesman Problem (TSP) is one of the most-studied hard problems in combinatorial optimization. We developed a new algorithm that uses a connection between Minimum Cost Flow Problems (MCF) and the TSP to improve on a given local optimum. MCF problems can be solved efficiently through linear programming or combinatorial algorithms such as cycle-cancelling. We investigated the potential of cycle-cancelling in the context of the TSP. Through a restriction of the search space of cycles to cancel for a given tour, practical results exhibit that only a low number of subtours is created, and a simple patching step suffices for a high success rate and gap closure towards an optimum.

Geometric packing problems have been investigated for centuries in mathematics and a notable example is the Kepler's conjecture, from the 1600s, about the packing of spheres in the Euclidean space. In this talk, we mainly address the knapsack problem of hyperspheres. The input is a set of hyperspheres associated with profits and a hyperrectangular container, the knapsack. The goal is to pack a maximum profit subset of the hyperspheres into the knapsack. For this problem, we present a PTAS. For a more general version, where we can have arbitrary fat objects instead of hyperspheres, we present a resource augmentation scheme (an algorithm that gives a super optimal solution in a slightly increased knapsack).

This thesis presents a mathematical formulation for time-shortening endurance runs of electric drive machines in the automotive industry. These runs test motor service life, identifying issues for future development. A program developed here automatically generates endurance profiles, factoring in conditions like maximum temperature and damage targets. Predefined blocks of speed and torque are combined to create a profile with minimum running time using Mixed Integer Programming (MIP) and solvers like Gurobi, HiGHS, or SCIP. This reduces manual labor and guarantees the shortest possible endurance run, while also enabling the consideration of various damage mechanisms that would be difficult to handle manually.

The dominating number of a graph is the minimum size of a vertex set whose closed neighborhoods cover all the vertices of the graph. The packing number of a graph is the maximum size of a vertex set whose closed neighborhoods are disjoint. We show constant bounds on the ratio of the above two parameters for various graph classes. For example, we improve the bound for planar graphs. The result implies a constant integrality gap for the domination and packing problems. This is a joint work with Marthe Bonamy, Monika Csikos and Anna Gujgiczer.

A good vertex of a graph is a vertex whose removal doesn't change the Wiener Index of the graph. Šoltés posed the problem of finding all simple graphs with only good vertices. He found that the cycle on 11 vertices does the trick and to this day it is still the only known graph with this property. Due to the challenge of finding more examples of such graphs, the relaxed version of the problem was tackled, namely the problem of finding graphs with a large proportion of good vertices. We consider a similar problem, but instead of the shortest path distance as in the Wiener Index, we use the resistance distance and the Kirchhoff Index. Similarly to the original problem, we find only the cycle on 5 vertices to solve the full problem. We construct several families of graphs with large proportions of good vertices.

The Minkowski asymmetry of a convex body K in R^d, i.e., the smallest dilation factor λ for which K is contained in a translate of λ(-K), is known to be at most d. The maximizers of the Minkowski symmetry are precisely the simplices, in particular those which are mirror symmetric with respect to some hyperplane. In order to quantify how mirror symmetric a given convex body K in R^d is, we may study the smallest dilation factor λ for which K is contained in a translate of some λ A_L(K) where A_L is the reflection about some j-dimensional linear subspace L of R^d. The Minkowski asymmetry is the j=0 case, and in this talk we focus on the case where d=2, j=1, and K is a triangle. We present some numerical evidence and discuss our analytical findings.

Assigning supervisors and correctors to exams is a recurrent task handled at the TUM-CIT Department of Mathematics. The current practice of determining a suitable allocation has several drawbacks leading to increased time consumption, which the implemented tool should help mitigate.

Ongoing changes in the residential energy sector, along with the emergence of Distributed Energy Resources (DER) such as photovoltaic (PV) energy generation and battery storage, as well as newer (and potentially more flexible) energy demands like heat pumps and electric vehicle charging, have significantly increased the importance of demand response management to ensure grid stability. The goal of this thesis is to formulate a linear program to model the operation of DER technologies such as electric vehicle charging, battery energy storage, heat pumps, and thermal storages in residential households. The objective is to minimize customers' energy costs based on given energy prices and demands. Different use-case scenarios are established. In these scenarios, households can either be considered individually or as a community where households have the option to share excess energy with their neighbors in a coordinated manner. Furthermore, the scenarios are distinguished based on whether they enforce network limitations, i.e., constrain the available power a transformer substation can supply, or not. After defining the corresponding LPs for these scenarios, some necessary conditions for solutions to the problems are analyzed and proven. Numerical experiments on exemplary data sets provided by Siemens are performed using the Pyomo modeling framework and Gurobi. Key performance indicators such as substation and household load profiles, substation peak loads, and energy costs for households are evaluated. This thesis was done in cooperation with the Siemens AG.

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be small discrete values or more generally m-dimensional vectors of small discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by the maximum weight and m for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in 0/1, or arbitrary and m = 1. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. This is joint work with Friedrich Eisenbrand and Karol Węgrzycki.

We study Blaschke-Santaló diagrams for the inradius, circumradius and diameter in general Minkowski spaces. Independent of the gauge, they can be described by at most five parts of boundaries. We analyse which bodies fill these bounds and for which gauges they become redundant. Furthermore, we give a complete description of the union over all these diagrams with respect to planar symmetric gauges (solving an open problem stated by Brandenberg and Gonzáles Merino in a recent paper) by providing a new inequality that tightens Bohnenblust's bound. This union is equal to the union over all diagrams with respect to intersections of triangles with their origin reflection. This is joint work with René Brandenberg and Bernardo Gonzáles Merino.

In the Multiple Allocation k-Hub Center (MAkHC), we are given a connected edge-weighted graph G, sets of clients C and hub locations H, where V (G) = C ∪ H, a set of demands D ⊆ C 2 and a positive integer k. A solution is a set of hubs H ⊆ H of size k such that every demand (a, b) is satisfied by a path starting in a, going through some vertex of H, and ending in b. The objective is to minimize the largest length of a path. We show that finding a (3 − ϵ)-approximation is NP-hard already for planar graphs. For arbitrary graphs, the approximation lower bound holds even if we parameterize by k and the value r of an optimal solution. An exact FPT algorithm is also unlikely when the parameter combines k and various graph widths, including pathwidth. To confront these barriers, we give a (2 + ϵ)-approximation algorithm parameterized by treewidth, and, as a byproduct, for unweighted planar graphs, we give a (2 + ϵ)-approximation algorithm parameterized by k and r. Compared to classical location problems, computing the length of a path depends on non-local decisions. This turns standard dynamic programming algorithms impractical, thus we introduce new ideas so that our algorithm approximates the length using only local information.