2019/12/13 by Ananya Christman, Christine Chung, Christman, Ananya +9
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Smart Parking Systems Research #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.1912.06300
openalex publication_date 2019/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Online-Dial-a-Ride Problem (OLDARP) a server travels through a metric space to serve requests for rides. We consider a variant where each request specifies a source, destination, release time, and revenue that is earned for serving the request. The goal is to maximize the total revenue earned within a given time limit. We prove that no non-preemptive deterministic online algorithm for OLDARP can be guaranteed to earn more than twice the revenue earned by an optimal offline solution. We then investigate the segmented best path (SBP) algorithm of~\citeatmos17 for the general case of weighted graphs. The previously-established lower and upper bounds for the competitive ratio of SBP are 4 and 6, respectively, under reasonable assumptions about the input instance. We eliminate the gap by proving that the competitive ratio is 5 (under the same reasonable assumptions). We also prove that when revenues are uniform, SBP has competitive ratio 4. Finally, we provide a competitive analysis of SBP on complete bipartite graphs.