AdONE Seminar - Monday, July 6, 2026: Maximilian v. Aspern, Lukas Brandl, Felix Buld (all AdONE)

Maximilian von Aspern: Scheduling under Parallelization with Diminishing Returns

Motivated by modern applications in computing, we study the problem of scheduling parallelizable jobs on a large number of machines. Since these jobs are not arbitrarily parallelizable but suffer from diminishing returns, we must balance individual job completions with overall system efficiency. We revisit known properties of optimal schedules, develop a convex program that computes such optimal schedules in special cases, and explore the possibility of deriving approximation guarantees for the (hard) general case.

 

Lukas Brandl: Bounding the integrality gap of a blocker-type relaxation of the circuit dominant of regular matroids

In this talk, we study the problem of finding minimum-weight circuits in regular matroids, which generalizes the problems of finding shortest cycles or minimum cuts in graphs. This problem, in particular with additional modularity constraints, plays a fundamental role in integer programming with bounded subdeterminants. While it can be solved with an additional parity constraint using Seymour's decomposition, the standard approaches seem to break down for higher modularity constraints. This motivates the exploration of alternative algorithmic approaches and, thus, we study the minimum-weight circuit problem for regular matroids by investigating a natural blocker relaxation of the circuit dominant: its cobase LP relaxation.

Our main result establishes that the integrality gap of this relaxation is bounded by O(log n). First, we show that the integrality gap is bounded by 2 for cographic matroids and by O(log n) for graphic matroids. Then, we use Seymour's decomposition to lift these bounds to general regular matroids.

Finally, this allows us to design an LP-based randomized algorithm that finds minimum-weight circuits in n^O(log n) time.

 

Felix Buld: Flow Shop Scheduling with Stochastic Reentry

Flow shop scheduling with reentry models production systems in which jobs repeatedly pass through the same sequence of machines. A prominent and highly relevant application arises in semiconductor manufacturing, where dozens of layers are successively deposited onto a wafer.
In this talk, we build on prior work that focuses on deterministic reentry and consider a more realistic setting of uncertainty, where the number of required passes is stochastic. We design and analyze scheduling policies to minimize classical performance measures, such as makespan and total weighted completion time, in expectation.
Our main methodological contribution is a reduction to a stochastic parallel machine scheduling problem with machine arrivals, enabling the transfer of structural results and optimality guarantees. We show that simple priority policies are optimal under monotonicity conditions on the underlying distributions and, in more general settings, derive approximation guarantees that depend only on the squared coefficients of variation.
We further highlight the implications of our results for practically motivated distributions capturing rework or failure mechanisms in manufacturing processes.

Date: July 6, 2026

Time: 5 pm, s.t.

Place: Arcisstr. 21, 80333 München, room Z538, Seminarraum (0505.Z1.538Z)