The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio is $1-1/e$ for both integral and fractional versions of the problem.
Since then, there has been considerable effort to find optimal competitive ratios for other related settings.

In this work, we go beyond the graph case and study the online matching problem on $k$-uniform hypergraphs.
For $k=3$, we provide an optimal primal-dual fractional algorithm, which achieves a competitive ratio of $(e-1)/(e+1)\approx 0.4621$. As our main technical contribution, we present a carefully constructed adversarial instance, which shows that this ratio is in fact optimal. It combines ideas from known hard instances for bipartite graphs under the edge-arrival and vertex-arrival models.

For $k\geq 3$, we give a simple integral algorithm which performs better than greedy when the online nodes have bounded degree. As a corollary, it achieves the optimal competitive ratio of 1/2 on 3-uniform hypergraphs when every online node has degree at most 2. This is because the special case where every online node has degree 1 is equivalent to the edge-arrival model on graphs, for which an upper bound of 1/2 is known.

An important aspect of the branch-and-bound algorithm is the node selection rule, which decides the order in which the solution space is explored. Ideally, such a rule guarantees not only that the number of unnecessary subproblems that are solved is small, but also that consecutively solved problems are close in the branch-and-bound tree. The design of a good node selection rule is equivalent to the solving the 'explorable heap selection' problem, an online graph exploration problem which was originally proposed by Karp, Saks and Wigderson (FOCS '86).

In this talk we discuss the connection between the two problems and we propose a new randomized algorithm for this problem with significantly better performance guarantees than any previously known algorithm. In the low-space setting this algorithm is nearly optimal in the light of a new lower bound that we provide.

We propose TSP-T3CO as a uniform, easy-to-use and extensible means for the formal and precise classification of TSP variants. It allows to reveal subtle differences within the same named variant and also brings out the differences between variants more clearly. We demonstrate its merits by a comprehensive, concise, and compact display of approximability results for a large number of TSP variants. This makes it easier to understand the approximability landscape and the assumptions under which certain results hold. Open gaps become more evident and results can be compared more easily. [arXiv:2311.00604]

Many businesses require intelligent adjustable algorithms, whose behavior is well-understood for a reliable practical deployment. This talk focuses on the application of adjustable planning for picking operations in e-commerce warehouses. Since order picking accounts for a substantial portion (60-70\%) of total operating costs in warehouses, it holds a pivotal role. In e-commerce settings, picking operations are essentially online, with customer orders arriving dynamically in real-time, highlighting the need for adjustable algorithms, or online policies.

Although several online policies for order picking have been suggested in the literature, there is a notable lack of understanding of their performance with respect to optimality. In this talk, we will conduct a comprehensive examination of a prominent online warehousing policy – myopic, immediate reoptimization (Reopt) – and establish analytical performance bounds using probabilistic- and worst-case analysis. We demonstrate that, under broad stochastic assumptions, Reopt is almost surely asymptotically optimal and, notably, we validate its near-optimal performance empirically.