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
isolated vertex is also considered as a star. A spanning star forest is a star forest whose vertex set is
also a
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
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.