New Bounds for Maximizing Revenue in Online Dial-a-Ride.

In the Online-Dial-a-Ride Problem (OLDARP) a server travels 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 half the revenue earned by \(\textsc {opt}\). We then investigate the segmented best path (\(\textsc {sbp}\)) algorithm of [8] for the general case of weighted graphs. The previously-established lower and upper bounds for the competitive ratio of \(\textsc {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 assumptions). We also prove that when revenues are uniform, \(\textsc {sbp}\) has competitive ratio 4. Finally, we provide a competitive analysis of \(\textsc {sbp}\) on complete bipartite graphs.