61 citations · 66 across the 7 of their papers we have counts for
5 papers · 1 filter
Prophet Secretary for Combinatorial Auctions and Matroids
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim +1
The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items…
Stochastic k-Server: How Should Uber Work?
Sina Dehghani, Soheil Ehsani, MohammadTaghi HajiAghayi +2
In this paper, we study a stochastic variant of the celebrated k-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are servi…
Beating 1-1/e for Ordered Prophets
Melika Abolhasani, Soheil Ehsani, Hosein Esfandiari +3
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of on the approximation factor…
Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi +3
We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We o…
Online Degree-Bounded Steiner Network Design
Sina Dahghani, Soheil Ehsani, MohammadTaghi Hajiaghayi +2
We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem { which asks for a subgraph with minimum degree that…