## Contributed Session Mon.3.H 3010

#### Monday, 15:15 - 16:45 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Location and routing problems

**Chair: Artem Panin**

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

**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.

**Monday, 15:45 - 16:10 h, Room: H 3010, Talk 2**

**Adrian Bock**

The school bus problem

**Coauthors: Elyot Grant, Jochen Könemann, Laura Sanità**

**Abstract:**

The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus relative to the shortest distance from the child's home to the school does not exceed a given regret threshold. Subject to this constraint and bus capacity limit, the goal is to minimize the number of buses required. We also consider the variant where we have a fixed number of buses to use and the goal is to minimize the maximum regret.

We present logarithmic factor approximation algorithms as well as constant factor approximations for the special case where all children and the school are located on a fixed tree.

**Monday, 16:15 - 16:40 h, Room: H 3010, Talk 3**

**Artem Panin**

On approximability some location and pricing problems

**Abstract:**

We consider location and pricing problems based on different pricing strategies: mill, uniform and discriminatory pricing. We suggest the bilevel mixed integer formulations. We proof that these problems are NP-hard in the strong sense. We present the polynomial time poly-approximate algorithms for these problems.