170056
20190812205547.0
978-3-642-25590-8
0302-9743
ISI
000308788400003
CONF
The School Bus Problem on Trees
Berlin
Springer-Verlag Berlin
2011
2011
10
Conference Papers
Lecture Notes in Computer Science
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 does not exceed the shortest distance from the child's home to the school by more than a given regret threshold. Subject to this constraint and bus capacity limit, the goal is to minimize the number of buses required. In this paper, we give a polynomial time 4-approximation algorithm when the children and school are located at vertices of a fixed tree. As a byproduct of our analysis, we show that the integrality gap of the natural set-cover formulation for this problem is also bounded by 4. We also present a constant approximation for the variant where we have a fixed number of buses to use, and the goal is to minimize the maximum regret.
Network design
Vehicle Routing
Approximation algorithms
243823
Bock, Adrian Aloysius
199692
Grant, Elyot
Könemann, Jochen
243827
Sanità, Laura
190471
22nd International Symposium on Algorithms and Computation (ISAAC 2011)
Yokohama, Japan
December 5-8, 2011
7074
10-19
Algorithms And Computation
146189
http://infoscience.epfl.ch/record/170056/files/sbp-isaac-final.pdf
n/a
n/a
252111
DISOPT
U11879
oai:infoscience.tind.io:170056
SB
conf
GLOBAL_SET
199692
EPFL-CONF-170056
EPFL
REVIEWED
PUBLISHED
CONF