3 citations · 3 across the 3 of their papers we have counts for
9 papers
Online Search for a Hyperplane in High-Dimensional Euclidean Space
Antonios Antoniadis, Ruben Hoeksma, Sándor Kisfaludi-Bak +1
We consider the online search problem in which a server starting at the origin of a -dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competiti…
A Stronger Impossibility for Fully Online Matching
Alexander Eckl, Anja Kirschbaum, Marilena Leichter +1
We revisit the fully online matching model (Huang et al., J.\ ACM, 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (STOC 1990), which h…
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
José Correa, Paul Dütting, Felix Fischer +2
A prophet inequality states, for some , that the expected value achievable by a gambler who sequentially observes random variables and selects one of the…
Improved Bounds for Open Online Dial-a-Ride on the Line
Alexander Birx, Yann Disser, Kevin Schewior
We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a…
Online Multistage Subset Maximization Problems
Evripidis Bampis, Bruno Escoffier, Kevin Schewior +1
Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as \emph{subset maximization problems}: One is given a ground set $N=\{1,\do…
A general framework for handling commitment in online throughput maximization
Lin Chen, Franziska Eberle, Nicole Megow +2
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-serve…