9 papers
Threshold Dynamics and Correlated Prophet Inequalities
José Correa, Maximilian Fichtl, Reda Jlibene +4
Prophet inequalities have become a central tool for analyzing the performance of online algorithms. However, most existing results assume that input random variables are independen…
Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules
Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen +1
This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system , a schedule consists of an independent…
Forwarding Packets Greedily on the Line
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +2
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its…
Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior
We consider the following Stochastic Boolean Function Evaluation problem, which is closely related to several problems from the literature. A matroid (in compact repr…
Non-Adaptive Evaluation of -of- Functions: Tight Gap and a Unit-Cost PTAS
Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior
We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of -of- functions: There are independent Boolean random variables $x_1,\dots,x_…
Improved Approximation Algorithms for the Expanding Search Problem
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm +1
A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At…