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


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+d3)) 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à


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


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.


  installment loans . The new drug with unique properties was developed to help men to get rid of all sexual disorders, and its name is Cialis Super Force. Now you do not have to buy two different medications to solve sexual problems.