Ebrahim Ghorbani

activity

20232026

collaborators

Showing 2026Show all

2 papers · 1 filter

cs.DS2026

A $2.8 1^{n}$ upper bound on the number of stable matchings

Ebrahim Ghorbani, Matthias Mnich

We study the maximum number $SM (n)$ of stable matchings in an instance with $n$ men and $n$ women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponen…

cs.DS2026

A deterministic $(2 + ε)$ -approximation for directed feedback vertex sets in tournaments

Ebrahim Ghorbani, Matthias Mnich

We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \va…

A 2.81n upper bound on the number of stable matchings

A deterministic (2+ε)-approximation for directed feedback vertex sets in tournaments

A $2.8 1^{n}$ upper bound on the number of stable matchings

A deterministic $(2 + ε)$ -approximation for directed feedback vertex sets in tournaments