Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Optimal Single-Choice Prophet Inequalities from Samples
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of can be achieved with a single…
cs.DS2024
Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
Aviad Rubinstein
We study generalizations of the "Prophet Inequality" and "Secretary Problem", where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we giv…
cs.DS2024
Sublinear Algorithms for TSP via Path Covers
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related {\em maximum path cover} problem, which asks for a collection of…