ATAndreas Tönnis

Andreas Tönnis

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Andreas Tönnis has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Hiring Secretaries over Time: The Benefit of Concurrent Employment

    by Yann Disser, John Fearnley, Martin Gairing, Oliver Göbel, Max Klimm, Daniel Schmand, Alexander Skopalik, Andreas Tönnis

    We consider a stochastic online problem where n applicants arrive over time, one per time step. Upon the arrival of each applicant, their cost per time step is revealed, and we have to fix the dura...


  • Open Access

    The Online Best Reply Algorithm for Resource Allocation Problems

    by Max Klimm, Daniel Schmand, Andreas Tönnis

    We study the performance of a best reply algorithm for online resource allocation problems with a diseconomy of scale. In an online resource allocation problem, we are given a set of resources and a set of requests that arrive in an online manner. Each request consists of a set of feasible allocations and an allocation is a set of resources. The total cost of an allocation vector is given by the sum of the resources' costs, where each resource's cost depends on the total load on the resource under the allocation vector. We analyze the natural online procedure where each request is allocated greedily to a feasible set of resources that minimizes the individual cost of that particular request. In the literature, this algorithm is also known as a one-round walk-in congestion games starting from the empty state. For unweighted resource allocation problems with polynomial cost functions with maximum degree $d$, upper bounds on the competitive ratio of this greedy algorithm were known only for the special cases $d\in\{1, 2, 3\}$. In this paper, we show a general upper bound on the competitive ratio of $d(d / W(\frac{1.2d-1}{d+1}))^{d+1}$ for the unweighted case where $W$ denotes the Lambert-W function on $\mathbb{R}_{\geq 0}$. For the weighted case, we show that the competitive ratio of the greedy algorithm is bounded from above by $(d/W(\frac{d}{d+1}))^{d+1}$.

  • A Collection of Lower Bounds for Online Matching on the Line

    by Antonios Antoniadis, Carsten Fischer, Andreas Tönnis


  • Open Access

    Hiring Secretaries over Time: The Benefit of Concurrent Employment

    by Yann Disser, John Fearnley, Martin Gairing, Oliver Göbel, Max Klimm, Daniel Schmand, Alexander Skopalik, Andreas Tönnis

    We consider a stochastic online problem where $n$ applicants arrive over time, one per time step. Upon arrival of each applicant their cost per time step is revealed, and we have to fix the duration of employment, starting immediately. This decision is irrevocable, i.e., we can neither extend a contract nor dismiss a candidate once hired. In every time step, at least one candidate needs to be under contract, and our goal is to minimize the total hiring cost, which is the sum of the applicants' costs multiplied with their respective employment durations. We provide a competitive online algorithm for the case that the applicants' costs are drawn independently from a known distribution. Specifically, the algorithm achieves a competitive ratio of 2.965 for the case of uniform distributions. For this case, we give an analytical lower bound of 2 and a computational lower bound of 2.148. We then adapt our algorithm to stay competitive even in settings with one or more of the following restrictions: (i) at most two applicants can be hired concurrently; (ii) the distribution of the applicants' costs is unknown; (iii) the total number $n$ of time steps is unknown. On the other hand, we show that concurrent employment is a necessary feature of competitive algorithms by proving that no algorithm has a competitive ratio better than $\Omega(\sqrt{n} / \log n)$ if concurrent employment is forbidden.