1 citations · 5 across the 17 of their papers we have counts for
22 papers
Deterministic Stackelberg Strategies in Robotaxi Assignment Games
Ioannis Caragiannis, Kostas Kollias, Mohammad Roghani +2
In autonomous mobility duopolies, platforms compete for riders based on vehicle proximity. A critical operational challenge---faced by an incumbent proactively defending against a…
Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals
Sara Ahmadian, Edith Cohen, Mohammad Roghani
Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matchi…
The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
Ioannis Caragiannis, Kostas Kollias, Mohammad Roghani +2
Autonomous ride-hailing platforms must strategically position idle robotaxis to minimize the wait times of prospective riders. We formalize this as the robotaxi placement problem (…
Stochastic Matching via Local Sparsification
Sara Ahmadian, Edith Cohen, Mohammad Roghani
The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride…
Improved Approximation for Ranking on General Graphs
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian +1
In this paper, we study Ranking, a well-known randomized greedy matching algorithm, for general graphs. The algorithm was originally introduced by Karp, Vazirani, and Vazirani [STO…
Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani +1
How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an -vertex graph ? We study this fundamental questio…
Sublinear Metric Steiner Forest via Maximal Independent Set
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski +1
In this work we consider the Metric Steiner Forest problem in the sublinear time model. Given a set of points in a metric space where distances are provided by means of que…
A 0.51-Approximation of Maximum Matching in Sublinear Time
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski
We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bou…
Stable Matching with Interviews
Itai Ashlagi, Jiale Chen, Mohammad Roghani +1
In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in m…
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski +1
We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of points in a metric space given to us by means of query access to an $n\…
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein +1
Given a so called ''Sperner coloring'' of a triangulation of the -dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by a…
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocat…
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a ver…
Fully Dynamic Matching: -Approximation in Polylog Update Time
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
We study maximum matchings in fully dynamic graphs, which are graphs that undergo both edge insertions and deletions. Our focus is on algorithms that estimate the size of maximum m…
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…
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic…
Beating Greedy Matching in Sublinear Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a -approximation algorithm which can be implemented…
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Tristan Pollner, Mohammad Roghani, Amin Saberi +1
Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph between individu…
Sequential importance sampling for estimating expectations over the space of perfect matchings
Yeganeh Alimohammadi, Persi Diaconis, Mohammad Roghani +1
This paper makes three contributions to estimating the number of perfect matching in bipartite graphs. First, we prove that the popular sequential importance sampling algorithm wor…
Beating the Folklore Algorithm for Dynamic Matching
Mohammad Roghani, Amin Saberi, David Wajc
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/…
Some Results on Dominating Induced Matchings
Saieed Akbari, Hossein Baktash, Amin Behjati +2
Let be a graph, a dominating induced matching (DIM) of is an induced matching that dominates every edge of . In this paper we show that if a graph has a DIM, then $χ…