DAIS Logo

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

  • January 31, 2025
    frankfurt
    Goethe University Frankfurt (Campus Bockenheim)
  • 13:00
    Jesper Nederlof (Utrecht University)
    Fine-grained Complexity for NP-hard Problems
    [show abstract]
    [hide]
    Abstract:

    Assuming P ≠ NP, the worst case runtime for any algorithm solving an NP-hard must be super-polynomial. But what is the lowest runtime we can get? Before one can even hope to approach this question, a more provoking one presents itself: Since for many problems simple “brain-dead” algorithms are still the fastest known, maybe these are already optimal? In this survey talk we give three examples of research lines studying this type of question for the Traveling Salesperson Problem, the Set Cover problem, and (if time permits) a classical scheduling problem with precedence constraints.

  • 14:15
    Mathias Sowa (Christian-Albrechts-Universität zu Kiel)
    Recent Progress in the Maker-Breaker k-Cycle Game
    [show abstract]
    [hide]
    Abstract:

    Maker-Breaker games are sequential games with perfect information played by two players, called Maker and Breaker. For n,qNn,q \in \mathbb{N} and a subgraph CC of the complete graph KnK_n the Maker-Breaker CC-game is played as follows. Alternately Maker claims an edge and thereafter Breaker claims up to qq edges of KnK_n until every edge has been claimed by one of the two players. If at the end of the game the graph of Maker-edges contains a copy of CC, Maker wins the game, otherwise Breaker wins.

    Bednarska and Łuczak (1999) showed that there exists constants c0c_0 and c1c_1 such that for large enough nn Maker has a winning strategy if qc0n1/m(C)q \leq c_0 n^{1/m(C)} and Breaker has a winning strategy if qc1n1/m(C)q \geq c_1 n^{1/m(C)} where m(C)=maxHC,V(H)3E(H)1V(H)2m(C) = \max_{\substack{H \subseteq C, |V(H)| \geq 3}} \frac{|E(H)|-1}{|V(H)|-2}. Thus the asymptotics of the game has been determined exactly, but unfortunately the constants implicitly given in the proof of Bednarska and Łuczak are magnitudes apart from each other. For example for the C3C_3 game the constant c0c_0 is smaller than 10510^{-5} and the constant c1c_1 is larger than 10410^4.

    Bednarska and Łuczak conjectured that these constants could be chosen arbitrarily close to each other. This conjecture is open for every graph CC which contains a cycle and for the most graphs there are not even good constants known. These constants have a significant meaning: powerful strategies lead to good constants and the smaller the gap between these constants is, the closer the players are to optimal play. In the intensively studied case where CC is a cycle of length 3 Chvátal and Erdős (1978) showed that Maker can win the game if q2nq \leq \sqrt{2}\sqrt{n} and Breaker can win if q2nq \geq 2\sqrt{n}.

    Recently Glazik and Srivastav (2022) introduced a new potential function which gives a winning strategy for Breaker if q>8/3nq>\sqrt{8/3} \sqrt{n}, which is considered a breakthrough result. We were able to generalize this potential function concept to cycles of arbitrary length, a class of games for which previously no good strategies with explicit constants were known. We also give a constructive strategy for Maker in the C4C_4-game which leads to the first good constant c0c_0 for this game.

    • December 6, 2024
      mainz
      Johannes Gutenberg University Mainz
  • 13:00
    Daniel Kráľ (Masaryk University)
    Matroid depth and width parameters
    [show abstract]
    [hide]
    Abstract:

    Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and combinatorial sparsity.

    In this talk, we will survey structural and algorithmic results concerning width and depth parameters of matroids. We will view matroids as purely combinatorial objects and discuss their structural properties related to depth and width decompositions. As an algorithmic application, we will present matroid based algorithms that can uncover a hidden Dantzig-Wolfe-like structure of instances of integer programs (if such structure is present).

    The most recent results presented in the talk are based on joint work with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.

  • 14:15
    Jonas Blochwitz (JGU Mainz)
    A Practical FPT-Algorithm for Treedepth
    • November 8, 2024
      darmstadt
      TU Darmstadt (Campus Stadtmitte)
  • 13:00
    Anita Schöbel (Fraunhofer ITWM and RPTU Kaiserslautern-Landau)
    Integrated Optimization for Public Transport
    [show abstract]
    [hide]
    Abstract:

    Many real-world problems are treated sequentially. One prominent example for such a sequential process is public transport optimization: One starts with network design, then plans lines and their frequencies. Based on these, the timetable is determined, and later on the vehicles’ and drivers’ schedules. The goal is to transport passengers according to their needs efficiently.

    The sequential procedure sketched above can be regarded as a Greedy approach: in each planning stage one aims at the best one can do. This usually leads to suboptimal solutions. On the other hand, in public transport optimization, the single steps are already NP hard such that solving the integrated problem to optimality seems to be out of scope.

    We introduce and analyze the price of sequentiality which measures how much can be gained by integrated approaches. We present different approaches for integrated optimization and illustrate them for the case of public transport optimization. Among them is the Eigenmodel as a framework for (heuristic) integrated approaches. We conclude with algorithmic challenges towards sustainable mobility.

  • 14:15
    Kord Eickmeyer (TU Darmstadt)
    Finite Model Theory on Tame Classes of Structures
    • July 12, 2024
      darmstadt
      TU Darmstadt (Campus Stadtmitte)
  • 13:00
    Anna 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:15
    Maximilian Gläser (TU Darmstadt)
    Lower bounds for Branch-and-Bound with General Disjunctions via Monotone Real Interpolation
    • June 21, 2024
      frankfurt
      Goethe University Frankfurt (Campus Bockenheim)
  • 13:00
    Anthony 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:15
    Marco 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, 2024
      mainz
      Johannes Gutenberg University Mainz
  • 13:00
    Martin 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:15
    Annamá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, 2024
      mainz
      Johannes Gutenberg University Mainz
  • 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
      darmstadt
      TU Darmstadt (Campus Stadtmitte)
  • 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
      frankfurt
      Goethe University Frankfurt (Campus Bockenheim)
  • 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
      darmstadt
      TU Darmstadt (Campus Stadtmitte)
  • 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: