12 citations · 17 across the 7 of their papers we have counts for
8 papers
Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani +2
Despite persistent efforts, there is no known technique for obtaining unconditional super-linear lower bounds for the computational complexity of the problems in P. Vassilevska Wil…
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…
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…
Faster and Simpler Algorithm for Optimal Strategies of Blotto Game
Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan +2
In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each b…
Price of Competition and Dueling Games
Sina Dehghani, MohammadTaghi Hajiaghayi, Hamid Mahini +1
We study competition in a general framework introduced by Immorlica et al. and answer their main open question. Immorlica et al. considered classic optimization problems in terms o…
From Duels to Battefields: Computing Equilibria of Blotto and Other Games
AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi +3
We study the problem of computing Nash equilibria of zero-sum games. Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in…
Revenue Maximization for Selling Multiple Correlated Items
MohammadHossein Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi +1
We study the problem of selling items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of th…