2 papers
cs.DS2026
Approximation Algorithms for Action-Reward Query-Commit Matching
Mahsa Derakhshan, Andisheh Ghasemi, Calum MacRury
Matching problems under uncertainty arise in applications such as kidney exchange, hiring, and online marketplaces. A decision-maker must sequentially explore potential matches und…
cs.CC2025
One-way Communication Complexity of Minimum Vertex Cover in General Graphs
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman
We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the \(k\)-party one-way communication model. Edges of an arbitrary \(n\)-ve…