Date: 18.03.2026, 14:00 (s.t.)

Location: Am Propsthof 49, Seminar Room

Speakers: Hannaneh Akrami

We study the fundamental problem of fairly dividing a set of indivisible goods among agents with additive valuations. Here, envy-freeness up to any good (EFX) is a central fairness notion and resolving its existence is regarded as one of the most important open problems in this area of research. Two prominent relaxations of EFX are envy-freeness up to one good (EF1) and epistemic EFX (EEFX). While allocations satisfying each of these notions individually are known to exist even for general monotone valuations, whether both can be satisfied simultaneously remains open for all instances in which the EFX problem is itself unresolved. 
In this work, we show that there always exists an allocation that is both EF1 and EEFX for additive valuations. We introduce a new share-based fairness notion, termed strong EEFX share, which may be of independent interest and which implies EEFX feasibility of bundles. We show that this notion is compatible with EF1, leading to the desired existence result.
This is based on a joint work with Ryoga Mahara, Kurt Mehlhorn, and Nidhi Rathi.

Date: 28.01.2026, 15 c.t.

Location:  Computer Science Department, Friedrich-Hirzebruch-Allee 8, room 2.074

Speakers: David Čadež

Please Take Note of the Non-Standard Time and Location!

Date: 17.12.2025, 16:00 (s.t.)

Location: Poppelsdorfer Allee 24, Seminar Room

Speakers: Miká Kruschel, Timo Reichert, Paul Müller

1. 16:00 Miká Kruschel: Approximating Distant Paths in Planar Graphs (II)
2. 16:35 Timo Reichert: Combining MMS and EFX Guarantees for Fair Division (II)
3. 17:10 Paul Müller: Few-Cut fair division: Topological and Algorithmic bounds for Cake-cutting with Entitlements (I)

Date: 19.11.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Siyue Liu

Consider a matroid where all elements are labeled with an integer. We are interested in finding a base where the sum of the labels is congruent to g mod m. We show that this problem is fixed-parameter tractable if we parametrize by m when m is either the product of two primes or a prime power. The algorithm can be generalized to all moduli and, in fact, to all abelian groups if a classic additive combinatorics conjecture by Schrijver and Seymour holds true. We also discuss the optimization version of the problem. Joint work with Chao Xu.

Date: 29.10.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Hannaneh Akrami

We consider the problem of guaranteeing maximin-share (MMS) when allocating a set of indivisible items to a set of agents with fractionally subadditive (XOS) valuations.

For XOS valuations, it has been previously shown that for some instances no allocation can guarantee a fraction better than 1/2 of maximin-share to all the agents. Also, a deterministic allocation exists that guarantees 0.2192 of the maximin-share of each agent.

We derive approximation guarantees for both deterministic and randomized allocations. On the deterministic side, we improve the best approximation guarantee to 3/13 = 0.2307. Furthermore, we investigate randomized algorithms and the Best-of-both-worlds fairness guarantees. We propose a randomized allocation that is 1/4-MMS ex-ante and 1/8-MMS ex-post. Moreover, we prove an upper bound of 3/4 on the ex-ante guarantee.

This is a joint work with Kurt Mehlhorn, Masoud Seddighin, and Golnoosh Shahkarami.

Date: 08.10.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Lilian Witters

Lilian will be presenting recent work of Kumar and Swamy:

We consider the k-edge connected spanning subgraph (k-ECSS) problem, where we are given an undirected graph G = (V, E) with nonnegative edge costs c_e , and the goal is to find a minimum-cost subgraph H of G that is k-edge connected, i.e., there exist at least k edge-disjoint paths between every pair of vertices in H. For even k, we present a polynomial time algorithm that computes a (k − 2)-edge connected subgraph of cost at most that of the optimal k-edge connected subgraph of G; for odd k, we obtain a (k−3)-edge connected subgraph of cost at most the optimum. In fact, the cost of our solution does not exceed the optimal value, OPT of the natural LP-relaxation for k-ECSS. Since k-ECSS is APX-hard for all values of k ≥ 2, our results are nearly optimal. They also significantly improve upon the recent work of Hershkowitz, Klein, and Zenklusen, both in terms of solution quality and the simplicity of algorithm and its analysis. Interestingly, our techniques also yield an alternate guarantee, where we obtain a (k − 1)-edge connected subgraph of cost at most 1.5 · OPT; with unit edge costs, the cost guarantee improves to 1 + (4/3k) · OPT, which improves upon the state-of-the-art approximation guarantee for unit edge costs, albeit with a unit loss in edge connectivity. 

Date: 10.09.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Henri Saal

The Divide and Concur heuristic is a general technique to find a point in the intersection of m sets. Divide and Concur introduces a copy of every variable for each set and reformulates the problem as the intersection of two sets in the product space. The arising problem can be solved via iterative methods like alternating projections or Douglas-Rachford. In this talk, we prove convergence for the general convex case. Furthermore, for the special case of systems of linear equations, we show linear convergence and provide numerical experiments.

Date: 26.05.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Attila Jung

Two celebrated extensions of Helly's theorem are the Fractional Helly theorem of Katchalski and Liu (1979) and the Quantitative Volume theorem of Barany, Katchalski, and Pach (1982). Improving on several recent works, we prove an optimal combination of these two results. We show that given a family $F$ of $n$ convex sets in $\mathbb{R}^d$ such that at least $\alpha \binom{n}{d+1}$ of the $(d+1)$-tuples of $F$ have an intersection of volume at least 1, then one can select $\Omega_{d,\alpha}(n)$ members of $F$ whose intersection has volume at least $\Omega_d(1)$.

Joint work with Nóra Frankl and István Tomon.

Date: 05.05.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Matthias Kaul

We study the problem of partitioning a set of n objects in a metric space into k clusters V_1, . . . , V_k . The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the ℓp-norms).
For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in V_i, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering.

This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ℓ∞) as Min-Max
Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. 

As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single ℓp norm for the objective.

This is based on joint work with Kelin Luo, Matthias Mnich, and Heiko Röglin.

Date: 25.04.2025

Location: Endenicher Allee 60, Center for Mathematics, Lipschitz-Hall

Program and Registration: https://www.uni-bonn.de/en/research-and-teaching/research-profile/transdisciplinary-research-areas/tra-1-modelling/events/reports/inauguration_symposium

Date: 24.02.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Haoyuan Ma

We investigate a variant of the trust region interior point method (TR-IPM) which was originally given by Lan, Monteiro and Tsuchiya (SIAM J. Optim. 2009). We show that the iteration complexity of this algorithm is essentially optimal in the L2-neighbourhood of the central path. Namely, the iteration complexity of the TR-IPM is upper bounded by the minimum number of segments of any piecewise linear curve traversing in a close L2-neighbourhood of the central path. This strengthens the previous bounds that were in terms of the Dikin-Todd-Stewart conditional number of the constraint matrix.

Lan, Monteiro and Tsuchiya only gave a weakly polynomial algorithm for solving the trust region problem, and left it as an open question to develop a strongly polynomial algorithm. We resolve this question by presenting a new strongly polynomial algorithm that solves a parametric minimum norm problem to a very high accuracy. As a result, each iteration of our TR-IPM can be implemented in strongly polynomial time. Our algorithm for the parametric problem relies on approximately computing the singular value decomposition of an associated matrix. These singular values enable us to locate the optimal parameter value in a narrow interval, where Newton's method exhibits quadratic convergence.

This is based on joint work with Daniel Dadush, Bento Natura, and László Végh.

Date: 27.01.2025, 14 c.t.

Location: Poppelsdorfer Allee 24, Seminar Room

Speaker: Roshan Raj