Seminar in Discrete Optimization

A graph is perfect if and only if its stable set polytope is equal to its associated QSTAB polytope, defined via clique inequalities. In 1975, Chvátal defined the analogous class of t-perfect graphs, which replaces the clique inequalities with certain odd-circuit inequalities. In 1994, Shepherd conjectured that the chromatic number of a t-perfect graph is at most 4. In 2024, Chudnovsky, Cook, Davies, Oum, and Tan have shown the first finite upper bound of 199,053. This talk discusses their proof, how their bound arises, and why they believe that it can be considerably improved.

The Banach-Mazur distance is a classical distance between isometry classes of normed spaces of the same dimension. As the metric space of such isometry classes with this distance turns out to be compact, it is traditionally called the Banach-Mazur compactum. Even though the Banach-Mazur compactum has been widely studied for several decades, many of its properties still seem to be quite elusive, even in low dimensions. For a general metric space, one frequently considered parameter is its equilateral dimension, that is, the maximum cardinality of a set in which any two elements are at the same distance. During the talk, we shall approach the problem of determining the equilateral dimension of the planar Banach-Mazur compactum.

Vortrag über die Problemstellung und deren Komplexität sowie die Entwicklung zweier Lösungsalgorithmen von Sonja Eberle im Rahmen ihrer Bachelorarbeit.

Each semester, faculties must allocate their staff members to exam supervision and correction duties. These problems were modelled as a joint mixed-integer linear program, incentivizing simultaneous allocation of staff to supervise and correct the same exam. This MILP is then modified to enable an adjustment of a given solution based on explicit assignments or exclusions of staff members. A long-term perspective that links semesters by carrying over unfulfilled duties and allows staff to work ahead was further given as a modification.

Solving Integer linear programs (ILPs) is significantly harder than finding optimal solutions for their linear relaxations which can be solved using many algorithms, most popularly the Simplex Algorithm. Depending on their structure and dimensions, the problem scales in complexity really fast. Here, cutting planes serve as an important tool to iteratively approach the integer optimal solution. Starting from a fractional optimal solution, a hyperplane (called cutting plane) is generated, that cuts off the fractional solution and eventually approaches the optimal integer solution in a few iterations. The generation of cutting planes (separation technique) and the approach of obtaining the optimal solution via the cutting planes provide good geometric insights and can often be visualised. The theoretical ideas of prominent cutting planes like the Chvátal-Gomory cuts, Lift and Project Cuts and Intersection Cuts will be described and applied on a few examples, thus visualizing the generation and approach of these cutting planes in the Optimization process. The geometrical ideas complement the theoretical framework and improve the overall intuition in generating these cutting planes.

In this talk, I will discuss two of our recent results on three-dimensional (3D) packing problems: the 3D Knapsack problem and the 3D Bin Packing problem. In both settings, we are given a collection of axis-aligned cuboids. In the Knapsack problem, each cuboid is associated with a profit, and the objective is to pack a subset of cuboids non-overlappingly into a unit cube to maximize total profit. In contrast, the Bin Packing problem seeks to pack all the cuboids using the minimum number of unit cubes (bins). Both problems are NP-hard and unlike their two-dimensional counterparts that have been extensively studied, the 3D variants have received much less attention. The previously best-known approximation ratios for 3D Knapsack and 3D Bin Packing are 7 + ε and (T_∞)^2 + ε ≈ 2.86, respectively for any constant ε > 0, where T_∞ ≈ 1.691 is the well-known Harmonic constant in Bin Packing. We provide improved approximation ratios of 139/29 + ε ≈ 4.794, and 3T_∞/2 + ε ≈ 2.54, for 3D Knapsack and 3D Bin Packing, respectively. Our key technical contribution is container packing -- a structured packing in 3D wherein all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. I shall also discuss few extensions of our techniques to related 3D packing problems.

We study a problem arising in the management of staff positions in institutions with a cameralistic budgeting system, for example in public universities in Germany. When a new employee is hired, she needs to be assigned to one or (partially) to several of the available positions. These position may already be (partially) assigned to other staff members during certain time periods. Some positions are better suited for the new hire due to, e.g., their associated pay grades or other administrative reasons. One seeks a solution with assignments to suitable open positions and wants few changes of those assignments over time. This yields a multi-objective optimization problem with a lexicographic objective function which can be seen as a scheduling problem with non-availability periods for the machines. We derive structural insights into this problem and present several MIP-formulations for it. Their solutions are optimal w.r.t. the three most important objectives and optimal or near-optimal w.r.t. the least important objective, respectively. In particular, we are able to solve our problem faster than with a straight-forward approach if one is willing to potentially sacrifice a bit of accuracy in the least important objective. In addition, we present very fast combinatorial algorithms for important special cases of the problem. Overall, we can solve most practically relevant instances in less than a few seconds. Our optimization tool was developed in collaboration with the administration of the School of Computation, Information, and Technology (CIT) at the Technical University of Munich where it is now used on a regular basis.

Solving Integer Programs (IPs) is generally NP-hard. But this does not imply that all instances are inherently hard. In fact, a substantial body of research has focused on identifying tractable subclasses and developing efficient (fixed-parameter tractable) time algorithms for those. This talk will give a little overview of some of the key results and techniques.

We provide an algorithm giving a 140/41 (3.415)-approximation for Coflow Scheduling and a 4.36-approximation for Coflow Scheduling with release dates. This improves upon the best known 4- and respectively 5-approximations and addresses an open question posed by Agarwal, Rajakrishnan, Narayan, Agarwal, Shmoys, and Vahdat [Aga+18], Fukunaga [Fuk22], and others. We additionally show that in an asymptotic setting, the algorithm achieves a (2+ϵ)-approximation, which is essentially optimal under P≠NP. The improvements are achieved using a novel edge allocation scheme using iterated LP rounding together with a framework which enables establishing strong bounds for combinations of several edge allocation algorithms.

The talk focuses on two the 66 problems stated in my book Geometric Tomography that are arguably the most notorious in convex geometry: Bourgain’s hyperplane conjecture from 1986 (finally confirmed last year) and Mahler’s conjecture from 1939 (still open). Both have great significance, not only for convex geometry, but for mathematics as a whole. A fairly comprehensive survey of these two important questions will be attempted, including their relationship to each other and to many other open conjectures from diverse areas of mathematics.

This talk is about a certain kind of finite undirected graph, said to be distance-regular. In this talk, the following concepts will be relevant. We will consider the concepts of Q-polynomial property, perfect 1-codes, and Cayley graphs.