V. V. Narayan

activity

20182023

most citedBreaking the Envy Cycle: Best-of-Both-Worlds Guarantees for Subadditive Valuations

7 citations · 8 across the 5 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

math.CO2020

The Speed and Threshold of the Biased Hamilton Cycle Game

Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3

We show that there is a constant C such that for any $b < \frac{n}{l n n} - \frac{C n}{( l n n ) ^{3/2}}$ , Maker wins the Maker-Breaker Hamilton cycle game in $n+\frac{Cn}{\sqrt{\ln{n}}}…

math.CO2020★ 1 cited

The Speed and Threshold of the Biased Perfect Matching Game

Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3

We show that Maker wins the Maker-Breaker perfect matching game in $\frac{n}{2} + o (n)$ turns when the bias is at least $\frac{n}{l o g n} - \frac{f ( n ) n}{( l o g n ) ^{5/4}}$ , for any $f$ …

cs.DS2020

Online Coloring and a New Type of Adversary for Online Graph Problems

Yaqiao Li, Vishnu V. Narayan, Denis Pankratov

We introduce a new type of adversary for online graph problems. The new adversary is parameterized by a single integer $κ$ , which upper bounds the number of connected components th…