61 citations · 206 across the 60 of their papers we have counts for
8 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…
On the Complexity of Chore Division
Alireza Farhadi, MohammadTaghi Hajiaghayi
We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among different players. The goal is to find an allocatio…
A Polynomial Time Algorithm for Spatio-Temporal Security Games
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +1
An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The "defender" can rarely af…
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…