4 papers
Stochastic scheduling with Bernoulli-type jobs through policy stratification
Antonios Antoniadis, Ruben Hoeksma, Kevin Schewior +1
This paper addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of jobs with stochastic processing times on par…
Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs
Lukas Drexler, Jan Höckendorff, Joshua Könen +1
We consider the following natural problem that generalizes min-sum-radii clustering: Given is as well as some metric space where for facilities…
Trading Prophets
José Correa, Andrés Cristi, Paul Dütting +3
In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm…
Knapsack Secretary Through Boosting
Andreas Abels, Leon Ladewig, Kevin Schewior +1
We revisit the knapsack-secretary problem (Babaioff et al.; APPROX 2007), a generalization of the classic secretary problem in which items have different sizes and multiple items m…