Discrete Algorithm Insights Seminar RMU

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.

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.

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.

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.