9 papers
The Knapsack Secretary Problem is Strictly Harder Than the Secretary Problem
Eric Balkanski, Jason Chatzitheodorou, Dimitris Fotakis +1
The knapsack secretary problem is a generalization of the classical secretary problem where the accepted items must satisfy a knapsack constraint. A line of work has developed cons…
Online Sorting with Our Eyes Wide Shut
Charalampos Platanos, Thanos Tolias
In Online Sorting, we are given an array of initially empty cells. At each time step , an element arrives and must be placed irrevocably into an empt…
Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis +1
The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether ther…
Repeated Descent: A Framework for Online Budget-Feasible Auctions
Andreas Charalampopoulos, Dimitris Fotakis, Thanos Tolias
We study budget feasible procurement auctions, in which agents, each with a privately held service cost, offer their services to an employer. The employer seeks to maximize a p…
Online Resource Allocation via Static Bundle Pricing
Dimitris Fotakis, Charalampos Platanos, Thanos Tolias
Online Resource Allocation addresses the problem of efficiently allocating limited resources to buyers with incomplete knowledge of future requests. In our setting, buyers arrive s…
A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
Andreas Kalavas, Charalampos Platanos, Thanos Tolias
In \emph{Online Sorting}, an array of initially empty cells is given. At each time step , an element arrives and must be placed irrevocably into an empty cel…