1 citations · 5 across the 17 of their papers we have counts for
5 papers · 1 filter
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…