Andreas Tönnis
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
Research Subjects
Research Interests
Andreas Tönnis has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Daniel Schmand
University of Bremen, Bremen, Germany
3 shared publications - Max Klimm
TU Berlin
3 shared publications - John Fearnley
University of Liverpool, Liverpool, United Kingdom
2 shared publications - Oliver Göbel
Department of Computer Science, RWTH Aachen University, Aachen 52062, Germany
2 shared publications - Yann Disser
TU Darmstadt
2 shared publications Alexander Skopalik
Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500 AE, Netherlands
1 shared publication
Latest Publications
- 1 February 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 323-352
Hiring Secretaries over Time: The Benefit of Concurrent Employment
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...
- 1 February 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 323-352
Hiring Secretaries over Time: The Benefit of Concurrent Employment
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
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}$.Open AccessThe Online Best Reply Algorithm for Resource Allocation Problems
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}$. - 13 March 2018
- Published by Springer Nature
- p. 52-65
A Collection of Lower Bounds for Online Matching on the Line
- 13 March 2018
- Published by Springer Nature
- p. 52-65
A Collection of Lower Bounds for Online Matching on the Line
- Open Access
Hiring Secretaries over Time: The Benefit of Concurrent Employment
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.Open AccessHiring Secretaries over Time: The Benefit of Concurrent Employment
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.