### 1 — 08:30 — Totally equimodular matrices

Totally unimodular matrices play a fundamental role in combinatorial optimization, as they offer combinatorial min-max theorems such as the MaxFlow-MinCut theorem and Kőnig's theorem about matchings in bipartite graphs.

Recently, a generalization called totally equimodular matrices has emerged within the context of box-totally dual integral polyhedra, which are the polyhedra hidden underneath "strong" min-max relations.

This talk aims to explore some connections between totally unimodular and totally equimodular matrices, offering insights into promising avenues while also addressing one notable drawback.

### 2 — 09:00 — A 2/3-approximation algorithm for the maximum weight spanning star forest problem

Given an undirected graph $G=(V,E)$ where the edges in $E$ is weighted positively, a star is a subgraph of $G$ of diameter at most 2. A star forest is a collection of (vertex) disjoint stars in $G$. In particular, an

isolated vertex is also considered as a star. A spanning star forest is a star forest whose vertex set is $V$. In this paper, we consider the Maximum Weight Spanning Forest Problem (MWSFP) which consists in finding a spanning forest of maximum weight in $G$. The MWSFP is defined in a paper by Nguyen et al. (SODA 2005) where it is proved to be NP-hard. In the same paper, the authors have given of a $\frac{1}{2}$-approximation algorithm for MWSFP and

also a $0.64$-approximation algorithm for the unweighted version.

Since then several improvements have been done for the unweighted version of MWSFP to achieve an approximation ratio 0.804 (Athanassopoulos et al. MFCS 2009) but the approximation ratio

$\frac{1}{2}$ obtained by Nguyen et al. remains the best so far for the MWSFP. In this paper, we improves the approximation ratio for MWSFP to $\frac{2}{3}$. Our algorithm is mainly an iterated rounding approximation algorithm based on a simple integer formulation for MWSFP.

### 3 — 09:30 — ** CANCELLED ** On the Congruency-Constrained Matroid Base

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.

### 4 — 10:00 — Combinatorial algorithms for large household allocation problems

Microsimulation models are efficient tools for predicting changes in certain aspects of society, such as demography and economy. A dynamic spatial microsimulation model is being developed for the entire German population in the project MikroSim. A fundamental stage of this model is the use of available geographic statistical information to create a high-quality allocation of households in dwellings at the municipal level.

In this work, the step of household-dwelling allocation is treated as a maximum weight matching problem with side constraints, which in general is too large to be solved by the available optimization methods. We present two different solution algorithms for the problem. The first is a case-specific decomposition algorithm, which generates an allocation with the property that it cannot be extended by any assignment without becoming infeasible. The second is a penalty approach where approximation algorithms are applied to obtain solutions for the penalized models, guaranteeing a certain optimality level for the final allocation. Numerical experiments show that both methods find high-quality allocations using less time and memory than standard algorithms, which allows them to handle instances with more than one billion variables.