**Monday, 15:15 - 15:40 h, Room: H 3010**

**Tim Nonner**

Polynomial-time approximation schemes for shortest path with alternatives

**Abstract:**

Consider the generic situation that we have to select *k* alternatives from a given ground set, where each element in the ground set has a random arrival time and cost. Once we have done our selection, we will greedily select the first arriving alternative, and the total cost is the time we had to wait for this alternative plus its random cost. Our motivation to study this problem comes from public transportation, where each element in the ground set might correspond to a bus or train, and the usual user behavior is to greedily select the first option from a given set of alternatives at each stop. First, we give an *O(n(**log* n+d^{3})) time algorithm for exponentially distributed arrival times, where *n* is the number of stops in the transportation network and *d* is the maximal number of buses or trains leaving any stop, making this approach practicable for large networks if *d* is relatively small, and second, for uniformly distributed arrival times, we give a PTAS under reasonable assumptions. These results are obtained by combining methods from low-rank quasi-concave optimization with fractional programming. We finally complement them by showing that general distributions are NP-hard.

Talk 1 of the contributed session Mon.3.H 3010

**"Location and routing problems"** [...]

Cluster 1

**"Approximation & online algorithms"** [...]