3 papers
cs.GT2024
Settling the Competition Complexity of Additive Buyers over Independent Items
Mahsa Derakhshan, Emily Ryu, S. Matthew Weinberg +1
The competition complexity of an auction setting is the number of additional bidders needed such that the simple mechanism of selling items separately (with additional bidders) ach…
cs.DS2023
Stochastic Minimum Vertex Cover in General Graphs: a -Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab
Our main result is designing an algorithm that returns a vertex cover of with size at most times the expected size of the minimum vertex cover, using…
cs.DS2021
Stochastic Vertex Cover with Few Queries
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
We study the minimum vertex cover problem in the following stochastic setting. Let be an arbitrary given graph, a parameter of the problem, and let be a ra…