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


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.


Talk 2 of the contributed session Mon.3.H 3010
"Location and routing problems" [...]
Cluster 1
"Approximation & online algorithms" [...]


  online cash advance . Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Cheap Levitra, but also as part of its analogs.