000170056 001__ 170056
000170056 005__ 20190812205547.0
000170056 020__ $$a978-3-642-25590-8
000170056 022__ $$a0302-9743
000170056 02470 $$2ISI$$a000308788400003
000170056 037__ $$aCONF
000170056 245__ $$aThe School Bus Problem on Trees
000170056 269__ $$a2011
000170056 260__ $$bSpringer-Verlag Berlin$$c2011$$aBerlin
000170056 300__ $$a10
000170056 336__ $$aConference Papers
000170056 490__ $$aLecture Notes in Computer Science
000170056 520__ $$aThe 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.
000170056 6531_ $$aNetwork design
000170056 6531_ $$aVehicle Routing
000170056 6531_ $$aApproximation algorithms
000170056 700__ $$0243823$$g199692$$aBock, Adrian Aloysius
000170056 700__ $$aGrant, Elyot
000170056 700__ $$aKönemann, Jochen
000170056 700__ $$0243827$$aSanità, Laura$$g190471
000170056 7112_ $$dDecember 5-8, 2011$$cYokohama, Japan$$a22nd International Symposium on Algorithms and Computation (ISAAC 2011)
000170056 773__ $$j7074$$tAlgorithms And Computation$$q10-19
000170056 8564_ $$zn/a$$yn/a$$uhttps://infoscience.epfl.ch/record/170056/files/sbp-isaac-final.pdf$$s146189
000170056 909C0 $$xU11879$$pDISOPT$$0252111
000170056 909CO $$ooai:infoscience.tind.io:170056$$qGLOBAL_SET$$pconf$$pSB
000170056 917Z8 $$x199692
000170056 937__ $$aEPFL-CONF-170056
000170056 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000170056 980__ $$aCONF