10 citations · 61 across the 34 of their papers we have counts for
12 papers · 1 filter
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given dist…
Sorting in One and Two Rounds using -Comparators
Ran Gelles, Zvi Lotker, Frederik Mallmann-Trenn
We examine sorting algorithms for elements whose basic operation is comparing elements simultaneously (a -comparator). We focus on algorithms that use only a single roun…
Prophet Inequalities: Separating Random Order from Order Selection
Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values in an online fashion, sampled from an instance of independent distributions,…
Online Page Migration with ML Advice
Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrović +1
We consider online algorithms for the {\em page migration problem} that use predictions, potentially imperfect, to improve their performance. The best known online algorithms for t…
Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?
Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
Motivated by crowdsourced computation, peer-grading, and recommendation systems, Braverman, Mao and Weinberg [STOC'16] studied the \emph{query} and \emph{round} complexity of funda…
Skyline Computation with Noisy Comparisons
Benoît Groz, Frederik Mallmann-Trenn, Claire Mathieu +1
Given a set of points in a -dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons b…
Hierarchical Clustering: Objective Functions and Algorithms
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn +1
Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering…
How large is your graph?
Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a \emph{seed} nod…
Plurality Consensus via Shuffling: Lessons Learned from Load Balancing
Petra Berenbrink, Tom Friedetzky, Peter Kling +2
We consider \emph{plurality consensus} in a network of nodes. Initially, each node has one of opinions. The nodes execute a (randomized) distributed protocol to agree on th…
Improved Analysis of Deterministic Load-Balancing Schemes
Petra Berenbrink, Ralf Klasing, Adrian Kosowski +2
We consider the problem of deterministic load balancing of tokens in the discrete model. A set of processors is connected into a -regular undirected network. In every time s…
Palindrome Recognition In The Streaming Model
Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn +1
In the Palindrome Problem one tries to find all palindromes (palindromic substrings) in a given string. A palindrome is defined as a string which reads forwards the same as backwar…
Slow Down & Sleep for Profit in Online Deadline Scheduling
Peter Kling, Andreas Cord-Landwehr, Frederik Mallmann-Trenn
We present and study a new model for energy-aware and profit-oriented scheduling on a single processor. The processor features dynamic speed scaling as well as suspension to a slee…