Showing 2024Show all
3 papers · 1 filter
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…
cs.CG2024
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…
cs.DS2024
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…