Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Randomized Binary and Tree Search under Pressure
Agustín Caracci, Christoph Dürr, José Verschae
We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in queries in the wors…
cs.DS2024
Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
Christoph Dürr, Arturo Merino, José A. Soto +1
We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element.…