Logo of DAIS RMU

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.

Everyone is welcome to attend without registration! If possible, please subscribe to our mailing list so that we have a rough estimate for the number of participants.

Past talks

  • February 2, 2024
    Johannes Gutenberg University Mainz
    Raum 01-211 | Binger Str. 14-16, 55122 Mainz  (show on map)
  • 13:00
    Martin 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:15
    Rebecca 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, 2024
    TU Darmstadt (Campus Stadtmitte)
    Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt  (show on map)
  • 13:00
    Isolde 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:15
    Irene Heinrich (TU Darmstadt)
    All interesting graphs are symmetric
  • November 24, 2023
    Goethe University Frankfurt (Campus Bockenheim)
    H 3 | Hörsaaltrakt Bockenheim, Gräfstraße 50-54, 60486 Frankfurt am Main  (show on map)
  • 13:00
    Pascal Schweitzer (TU Darmstadt)
    Symmetries of Combinatorial Structures
  • 14:15
    Manuel 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, 2023
    TU Darmstadt (Campus Stadtmitte)
    Raum S3|13/30 | Schloss Kaisersaalbau, Marktplatz 15, 64283 Darmstadt  (show on map)
  • 13:00
    Kurt 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:15
    Jú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: