Airports and Railways: Facility Location Meets Network Design

Authors Anna Adamaszek, Antonios Antoniadis, Tobias Mömke



PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.6.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Anna Adamaszek
Antonios Antoniadis
Tobias Mömke

Cite AsGet BibTex

Anna Adamaszek, Antonios Antoniadis, and Tobias Mömke. Airports and Railways: Facility Location Meets Network Design. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.6

Abstract

We introduce a new framework of Airport and Railway Problems, which combines capacitated facility location with network design. In this framework we are given a graph with weights on the vertices and on the edges, together with a parameter k. The vertices of the graph represent cities, and weights denote respectively the costs of opening airports in the cities and building railways that connect pairs of cities. The parameter $k$ can be thought of as the capacity of an airport. The goal is to construct a minimum cost network of airports and railways connecting the cities, where each connected component in the network spans at most k vertices, contains an open airport, and the network satisfies some additional requirements specific to the problem in the framework. We consider two problems in this framework. In the AR_F problem there are no additional requirements for the network. This problem is related to capacitated facility location. In the AR_P problem, we require each component to be a path with airports at both endpoints. AR_P is a relaxation of the capacitated vehicle routing problem (CVRP). We consider the problems in the two-dimensional Euclidean setting. We show that both AR_F and AR_P are NP-hard, even for uniform vertex weights (i.e., when the cost of building an airport is the same for all cities). On the positive side, we provide polynomial time approximation schemes for AR_F and AR_P when vertex weights are uniform. We also investigate AR_F and AR_P for k = infinity. In this setting we present an exact polynomial time algorithm for AR_F with general vertex costs, which also works for general edge costs. In contrast to AR_F, AR_P remains NP-hard when k = infinity, and we present a polynomial time approximation scheme for general vertex weights. We believe that our PTAS for AR_P with uniform vertex weights and arbitrary k brings us closer towards a PTAS for Euclidean CVRP, for which the main difficulty is to deal with paths of length at most k.
Keywords
  • approximation algorithms
  • geometric approximation
  • facility location
  • network design
  • PTAS

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Anna Adamaszek, Artur Czumaj, and Andrzej Lingas. PTAS for k-tour cover problem on the plane for moderately large values of k. Int. J. Found. Comput. Sci., 21(6):893-904, 2010. URL: http://dx.doi.org/10.1142/S0129054110007623,
  2. Anna Adamaszek, Artur Czumaj, Andrzej Lingas, and Jakub Onufry Wojtaszczyk. Approximation schemes for capacitated geometric network design. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 25-36, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22006-7_3,
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, 1998. Google Scholar
  4. Sanjeev Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program., 97(1-2):43-69, 2003. Google Scholar
  5. Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 106-113, 1998. URL: http://doi.acm.org/10.1145/276698.276718, URL: http://dx.doi.org/10.1145/276698.276718.
  6. Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama. Covering points in the plane by k-tours: Towards a polynomial time approximation scheme for general k. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 275-283, 1997. URL: http://doi.acm.org/10.1145/258533.258602, URL: http://dx.doi.org/10.1145/258533.258602.
  7. Marshall Wayne Bern and David Eppstein. Approximation algorithms for geometric problems. In Dorit Hochbaum, editor, Approximation Algorithms for NP-hard Problems, chapter 8, pages 296-345. PWS Publishing, 1996. Google Scholar
  8. G.B. Dantzig and Ramser J.H. The truck dispatching problem. Management Science, 6(1):80-91, 1959. Google Scholar
  9. Aparna Das and Claire Mathieu. A quasipolynomial time approximation scheme for euclidean capacitated vehicle routing. Algorithmica, 73(1):115-142, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9906-4,
  10. Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, and Guido Schäfer. Connected facility location via random facility sampling and core detouring. J. Comput. Syst. Sci., 76(8):709-726, 2010. URL: http://dx.doi.org/10.1016/j.jcss.2010.02.001,
  11. Inge Li Gørtz and Viswanath Nagarajan. Locating depots for capacitated vehicle routing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 230-241, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22935-0_20,
  12. Tobias Harks, Felix G. König, and Jannik Matuschke. Approximation algorithms for capacitated location routing. Transportation Science, 47(1):3-22, 2013. URL: http://dx.doi.org/10.1287/trsc.1120.0423,
  13. Raja Jothi and Balaji Raghavachari. Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design. ACM Transactions on Algorithms (TALG), 1(2):265-282, 2005. Google Scholar
  14. Christos H Papadimitriou and Mihalis Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1-11, 1993. Google Scholar
  15. R. Ravi and Amitabh Sinha. Approximation algorithms for problems combining facility location and network design. Operations Research, 54(1):73-81, 2006. URL: http://dx.doi.org/10.1287/opre.1050.0228,
  16. Alexander Schrijver. Combinatorial Optimization. Springer, 2003. Google Scholar
  17. Chaitanya Swamy and Amit Kumar. Primal-dual algorithms for connected facility location problems. Algorithmica, 40(4):245-269, 2004. URL: http://dx.doi.org/10.1007/s00453-004-1112-3,
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail