Discrete Algorithm Insights Seminar RMU
The Discrete Algorithm Insights Seminar at the Rhine-Main-Universities is a regular in-person seminar for researchers and students interested in discrete algorithms and related topics, such as graph theory, complexity, and optimization.
- July 12, 2024TU Darmstadt (Campus Stadtmitte)Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt (show on map)
- 13:00Anna Zych-Pawlewicz (University of Warsaw)Randomization techniques for online bipartite matching[show abstract][hide]Abstract:
In the online bipartite matching problem, a bipartite graph G=(S, C, E) is revealed in the online manner. While all the vertices in S, also called servers, are known to the algorithm from the beginning, the vertices of C are revealed in an online fashion one vertex at the time. Upon its arrival, the client presents all the edges that are adjacent to it. The algorithm must then either match the client to one of its neighbors, or leave it unmatched forever. The goal of the algorithm is to maximize the size of the matching even though the future is unknown. This is a very fundamental problem with applications to online advertisement, combinatorial auctions and economy. The usual measure of performance for an online algorithm is the worst possible ratio (called the competitive ratio) of the size of the matching produced by the algorithm to the optimum offline matching. It is not hard to see that a deterministic cannot beat the ratio of 1/2 and there is a very simple deterministic algorithm achieving this ratio.
In 1990, Karp, Vazirani and Vazirani proposed the celebrated ranking algorithm for this problem. Over the years, the analysis of the ranking algorithm was gradually simplified to become a textbook example of the primal-dual analysis. The primal-dual analysis for this problem opened the toolbox that allows to attack more general variants of online bipartite matching: the edge arrival model, and the two-sided vertex arrival model. Surprisingly, the edge arrival model turns out substantially more difficult than the vertex arrival model. In this talk, we present a survey of these results and the basic techniques behind them.
- 14:15Maximilian Gläser (TU Darmstadt)Lower bounds for Branch-and-Bound with General Disjunctions via Monotone Real Interpolation
Past talks
- June 21, 2024Goethe University Frankfurt (Campus Bockenheim)H IV | Hörsaaltrakt Bockenheim, Gräfstraße 50-54, 60486 Frankfurt am Main (show on map)
- 13:00Anthony Lin (RPTU Kaiserslautern-Landau)Understanding the expressive power of transformers through the lens of formal language theory[show abstract][hide]Abstract:
I will discuss recent developments at the intersection of formal language theory and machine learning, especially with the goal to understand the expressiveness of transformers. Among others, I will discuss results connected my recent work (e.g. from ICLR’24).
- 14:15Marco Schmalhofer (Goethe University Frankfurt)Best of Both World Fair Division with Entitlements[show abstract][hide]Abstract:
Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW).
We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1,1)). We show that this result is tight - ex-ante WEF is incompatible with any stronger ex-post WEF relaxation.
In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.
- May 17, 2024Johannes Gutenberg University MainzRaum 03-428 | Staudingerweg 9, 55128 Mainz (show on map)
- 13:00Martin Grohe (RWTH Aachen)The Descriptive Complexity of Graph Neural Networks[show abstract][hide]Abstract:
Graph neural networks (GNNs) are deep learning models for graph data that play a key role in machine learning on graphs. A GNN describes a distributed algorithm carrying out local computations at the vertices of the input graph. Typically, the parameters governing this algorithm are acquired through data-driven learning processes.
After introducing the basic model, in this talk we will focus on the expressiveness of GNNs: which functions on graphs or their vertices can be computed by GNNs? An intriguing and nontrivial facet of this inquiry is that GNNs are “analog” computation models operating on and with real numbers. Nevertheless, we can give precise characterisations of the expressiveness of GNNs in terms of Boolean circuits and logic, that is, computation models of classical (descriptive) complexity theory.
- 14:15Annamária Kovács (Goethe University Frankfurt)A proof of the Nisan-Ronen conjecture[show abstract][hide]Abstract:
Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.
Joint work with George Christodoulou and Elias Koutsoupias
- February 2, 2024Johannes Gutenberg University MainzRaum 01-211 | Binger Str. 14-16, 55122 Mainz (show on map)
- 13:00Martin Skutella (TU Berlin)Transshipments over time and submodular functions[show abstract][hide]Abstract:
Network flows over time are a fascinating generalization of classical (static) network flows, introducing an element of time. They naturally model problems where travel and transmission are not instantaneous and flow may vary over time. Not surprisingly, flow over time problems turn out to be more challenging to solve than their static counterparts. In this talk, we mainly focus on the efficient computation of transshipments over time in networks with several source and sink nodes with given supplies and demands, which is arguably the most difficult flow over time problem that can still be solved in polynomial time.
- 14:15Rebecca Steiner (Johannes Gutenberg University Mainz)Broadcasting on Random Recursive Trees[show abstract][hide]Abstract:
In the broadcasting problem on trees, a {0,1}-message, originating in an unknown node, is passed along the tree with a certain error probability q. The goal is to estimate the original message without knowing the order in which the nodes were informed. A variation of the problem is considering this broadcasting process on a randomly growing tree, which Addario-Berry et al. have investigated for uniformly recursive and linear preferential attachment trees. We extend their studies to the entire group of very simple increasing trees, as well as shape exchangeable trees, using the connection between them and other stochastic processes with memory effects.
- January 19, 2024TU Darmstadt (Campus Stadtmitte)Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt (show on map)
- 13:00Isolde Adler (University of Bamberg)Logic and property testing[show abstract][hide]Abstract:
Property testing (for a property P) asks for a given graph, whether it has property P, or is “structurally far” from having that property. A “testing algorithm” is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as “extremely efficient”, making them relevant in the context of large data sets.
In this talk I will present recent positive and negative results about testability of properties definable in first-order logic and monadic second-order logic on classes of bounded-degree graphs.
This is joint work with Polly Fahey, Frederik Harwath, Noleen Köhler and Pan Peng.
- 14:15Irene Heinrich (TU Darmstadt)All interesting graphs are symmetric
- November 24, 2023Goethe University Frankfurt (Campus Bockenheim)H 3 | Hörsaaltrakt Bockenheim, Gräfstraße 50-54, 60486 Frankfurt am Main (show on map)
- 13:00Pascal Schweitzer (TU Darmstadt)Symmetries of Combinatorial Structures
- 14:15Manuel Penschuck (Goethe University Frankfurt)Sampling Random Graphs at Scale[show abstract][hide]Abstract:
Random graphs are commonly used as network models and, as such, often capture typical features shared amongst graphs from some (application) domain. In algorithmics, we can use such models to improve our theoretical understanding of the practical performance of graph algorithms, e.g., by encoding input classes for average case analyses as random graphs.
Especially in the algorithm engineering community, random graphs additionally gained attention as a controllable and versatile data source for experimental campaigns. However, generating such data-sets at scale is a non-trivial task in itself.
In this talk, we introduce a selection of basic algorithmic techniques used in practical graph generators and highlight how the presumed model of computation informs the design of state-of-the-art generators. Most ideas are also applicable to sample discrete objects beyond random graphs.
- November 3, 2023TU Darmstadt (Campus Stadtmitte)Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt (show on map)
- 13:00Kurt Mehlhorn (Max Planck Institute for Informatics)Who Gets What? Fair Division of Indivisible Goods[show abstract][hide]Abstract:
A set of indivisible goods, e.g., a car, a house, a toothbrush, …, has to be split among a set of agents in a fair manner. Each agent has its own valuation function for sets of goods. What constitutes a fair allocation? When does a fair allocation exist? If it exists, can we compute it efficiently? Can we approximate fair allocations?
The talk is based on joint work with H. Akrami, N.Alon, B. Chaudhury, J. Garg, M. Hoefer, T. Kavitha, R. Mehta, P. Misra, M. Schmalhofer, A. Sgouritsa, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland that appeared in EC20, EC21, EC23, JACM 23, FSTTCS 20, SODA 21, AAAI 22, IJCAI 23, and SICOMP 22.
- 14:15Júlia Baligács (TU Darmstadt)The online graph exploration problem
About
DAIS is organized by the Consortium on Discrete Algorithm Insights (CoDa Insights). The Consortium consists of all interested researchers and students from the Rhine-Main-Universities, and is currently coordinated by the following faculty members:- Prof. Dr. Ernst Althaus (Johannes Gutenberg University Mainz)
- Prof. Dr. Holger Dell (Goethe University Fankfurt)
- Prof. Dr. Pascal Schweitzer (TU Darmstadt)