Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Average-Distortion Sketching
Yiqiao Bao, Anubhav Baweja, Nicolas Menand +3
We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwis…
cs.DS2021
An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes
Anubhav Baweja, Justin Jia, David P. Woodruff
We present the first semi-streaming PTAS for the minimum feedback arc set problem on directed tournaments in a small number of passes. Namely, we obtain a -appro…
cs.DS2016
A Constant Optimization of the Binary Indexed Tree Query Operation
Anubhav Baweja
There are several data structures which can calculate the prefix sums of an array efficiently, while handling point updates on the array, such as Segment Trees and Binary Indexed T…