5 papers
Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
Yakov Nekrich, Saladi Rahul
Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set of points in 3-D,…
A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
Rachana Gusain, Saladi Rahul, Aditya Subramanian
We revisit the maximum range sum (MaxRS) problem: given a set of weighted points in and a range (typically axis-aligned -box or -ball), the goal is…
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…
Approximating Densest Subgraph in Geometric Intersection Graphs
Sariel Har-Peled, Rahul Saladi
$ \newcommand{\cardin}[1]{\left| {#1} \right|}% \newcommand{\Graph}{\Mh{\mathsf{G}}}% \providecommand{\G}{\Graph}% \renewcommand{\G}{\Graph}% \providecommand{\GA}{\Mh{H}}% \renewco…
Range Longest Increasing Subsequence and its Relatives
Karthik C. S., Saladi Rahul
In this work, we present a plethora of results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to RLIS is a sequence of real nu…