The school bus problem on trees

Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)


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.

Originele taal-2Engels
TitelAlgorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Aantal pagina's10
StatusGepubliceerd - 2011
Extern gepubliceerdJa
Evenement22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
Duur: 5 dec 20118 dec 2011

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7074 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres22nd International Symposium on Algorithms and Computation, ISAAC 2011


Duik in de onderzoeksthema's van 'The school bus problem on trees'. Samen vormen ze een unieke vingerafdruk.

Citeer dit