3 papers
cs.DS2026
Competitive Random-Order Correlation k-Clustering
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman +2
Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is t…
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…