부산대학교 도서관

Summary: ``We consider a variant of the offline Dial-a-Ride problemwith a single server where each request has a source, destination, anda prize earned for serving it. The goal for the server is to serverequests within a given time limit so as to maximize the total prizemoney. We consider the variant where prize amounts are uniform which isequivalent to maximizing the number of requests served. This setting isapplicable when all rides may have equal importance such as paratransitservices. We first prove that no polynomial-time algorithm can beguaranteed to serve the optimal number of requests, even when the timelimit for the algorithm is augmented by any constant factor $c \geq 1$.We also show that if $\lambda = t_{max}/t_{min}$, where $t_{max}$ and$t_{min}$ denote the largest and smallest edge weights in the graph,the approximation ratio for a reasonable class of algorithms for thisproblem is unbounded, unless $\lambda$ is bounded. We then show thatthe segmented best path (SBP) algorithm from [8] is a 4-approximation.We then present our main result, an algorithm, $k$-Sequence, thatrepeatedly serves the fastest set of $k$ remaining requests, andprovide upper and lower bounds on its performance. We show $k$-Sequencehas approximation ratio at most $2+\lceil \lambda\rceil/k$ and at least$1+\lambda/k$ and that $1 + \lambda/k$ is tight when $1 + \lambda/k\geq k$. Thus, for the case of $k = 1$, i.e., when the algorithmrepeatedly serves the quickest request, it has approximation ratio $1 +\lambda$, which is tight for all $\lambda$. We also show that even as kgrows beyond the size of $\lambda$, the ratio never improves below9/7.''