Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Bipartite Matching with Few Rounds of Demand Queries
Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah
We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisa…
cs.DS2026
The Power of the Score Sequence of a Tournament
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra +1
What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs…
cs.DS2024
Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones
L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra +1
The focus of this paper is to increase our understanding of the Longest Processing Time First (LPT) heuristic. LPT is a classical heuristic for the fundamental problem of uniform m…