Name
Abstract | ||
|---|---|---|
In a k-server routing problem k=1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour (k-Traveling Salesman Problem or k-tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-trp). Both problems, the k-tsp and the k-trp have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k1, in particular for randomized algorithms against an oblivious adversary. We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound for the k-Dial-a-Ride-Problem (the k-trp when objects need to be carried) from 4e-52e-3~2.4104 to 3 which is currently also the best lower bound for deterministic algorithms. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ipl.2009.01.024 | Inf. Process. Lett. |
Keywords | Field | DocType |
competitive ratio,deterministic algorithm,k-traveling salesman,new lower bound,competitive analysis point,routing,competitive analysis,randomized algorithm,on-line algorithms,k-traveling repairman problem,online algorithm,online k-server,online version request,corresponding lower bound,metric space,lower bound,traveling salesman problem | Online algorithm,Randomized algorithm,Mathematical optimization,Job shop scheduling,Upper and lower bounds,K-server problem,Server,Travelling salesman problem,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
109 | 11 | 0020-0190 |
Citations | PageRank | References |
5 | 0.47 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irene Fink | 1 | 5 | 0.47 |
| Sven O. Krumke | 2 | 308 | 36.62 |
| Stephan Westphal | 3 | 97 | 13.41 |