id: 05938274
dt: a
an: 05938274
au: Chen, Danny Z.; Wang, Haitao
ti: New algorithms for 1-D facility location and path equipartition problems.
so: Dehne, Frank (ed.) et al., Algorithms and data structures. 12th
    international symposium, WADS 2011, New York, NY, USA, August 15‒17,
    2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22299-3/pbk).
    Lecture Notes in Computer Science 6844, 207-218 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-22300-6_18
ab: Summary: We study the one-dimensional facility location problems. Given a
    set of $n$ customers on the real line, each customer having a cost for
    setting up a facility at its position, and an integer $k$, we seek to
    find at most $k$ of the customers to set up facilities for serving all
    $n$ customers such that the total cost for facility set-up and service
    transportation is minimized. We consider several problem variations
    including $k$-median and $k$-coverage and a linear model. We also study
    a related path equipartition problem: Given a vertex-weighted path and
    an integer $k$, remove $k - 1$ edges so that the weights of the
    resulting $k$ sub-paths are as equal as possible. Based on new problem
    modeling and observations, we present improved algorithms for these
    problems over the previous work.
rv: