Skip to main content
Springer Nature Link
Log in

A Parameterized Approximation Algorithm for the Multiple Allocation k-Hub Center

  • Conference paper
  • First Online:
LATIN 2022: Theoretical Informatics (LATIN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13568))

Included in the following conference series:

  • 808 Accesses

  • 2 Citations

Abstract

In the Multiple Allocation \(k\) -Hub Center, we are given a connected edge-weighted graph G, sets of clients \(\mathcal {C}\) and hub locations \(\mathcal {H}\), where \({V(G) = \mathcal {C}\cup \mathcal {H}}\), a set of demands \({\mathcal {D}\subseteq \mathcal {C}^2}\) and a positive integer k. A solution is a set of hubs \({H \subseteq \mathcal {H}}\) of size k such that every demand (a, b) is satisfied by a path starting in a, going through some vertex of H, and ending in b. The objective is to minimize the largest length of a path. We show that finding a \((3-\epsilon )\)-approximation is NP-hard already for planar graphs. For arbitrary graphs, the approximation lower bound holds even if we parameterize by k and the value r of an optimal solution. An exact FPT  algorithm is also unlikely when the parameter combines k and various graph widths, including pathwidth. To confront these hardness barriers, we give a \((2+\epsilon )\)-approximation algorithm parameterized by treewidth, and, as a byproduct, for unweighted planar graphs, we give a \((2+\epsilon )\)-approximation algorithm parameterized by k and r. Compared to classical location problems, computing the length of a path depends on non-local decisions. This turns standard dynamic programming algorithms impractical, thus our algorithm approximates this length using only local information.

Research supported by São Paulo Research Foundation (FAPESP), grants #2015/11937-9 and #2019/10400-2 and National Council for Scientific and Technological Development (CNPq), grants #422829/2018-8 and #312186/2020-7.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 74.89
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 96.29
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

References

  1. Alumur, S., Kara, B.Y.: Network hub location problems: the state of the art. Eur. J. Oper. Res. 190(1), 1–21 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ando, R., Matsui, T.: Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane. In: Algorithms and Computation, pp. 474–483 (2011)

    Google Scholar 

  3. Benedito, M.P.L., Pedrosa, L.L.C.: Approximation algorithms for median hub location problems. J. Comb. Optim. 38(2), 375–401 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  4. Benedito, M.P.L., Pedrosa, L.L.C.: An efficient parameterized approximation scheme for the star \(k\)-hub center. Procedia Comput. Sci. 195, 49–58 (2021)

    Article  Google Scholar 

  5. Blum, J.: W[1]-hardness of the \(k\)-center problem parameterized by the skeleton dimension. J. Comb. Optim. 44, 2762–2781 (2022). https://doi.org/10.1007/s10878-021-00792-4

    Article  MathSciNet  MATH  Google Scholar 

  6. Bodlaender, H.L., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. 27(6), 1725–1746 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bordini, C.F., Vignatti, A.L.: An approximation algorithm for the \(p\)-hub median problem. Electron. Notes Disc. Math. 62, 183–188 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  8. Campbell, J., Ernst, A., Krishnamoorthy, M.: Hub location problems. Facility location: application and theory (2002)

    Google Scholar 

  9. Campbell, J.F.: Hub location and the \(p\)-Hub median problem. Oper. Res. 44(6), 923–935 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  10. Charikar, M., Guha, S., Tardos, É., Shmoys, D.B.: A constant-factor approximation algorithm for the \(k\)-median problem. J. Comput. Syst. Sci. 65(1), 129–149 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chen, L.H., Cheng, D.W., Hsieh, S.Y., Hung, L.J., Lee, C.W., Wu, B.Y.: Approximation Algorithms for the Star \(k\)-Hub Center Problem in Metric Graphs, pp. 222–234. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-42634-1_18

  12. Cornuéjols, G., Nemhauser, G., Wolsey, L.: The uncapacitated facility location problem. Cornell University Operations Research and Industrial Engineering, Technical report (1983)

    Google Scholar 

  13. Cygan, M., et al.: Parameterized Algorithms. Springer (2015). https://doi.org/10.1007/978-3-319-21275-3

  14. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameter algorithms for \((k, r)\)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33–47 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  15. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameter algorithms for the \((k, r)\)-center in planar graphs and map graphs. In: International Colloquium on Automata, Languages, and Programming, pp. 829–844. Springer (2003). https://doi.org/10.1007/3-540-45061-0_65

  16. Farahani, R.Z., Hekmatfar, M., Arabani, A.B., Nikbakhsh, E.: Hub location problems: a review of models, classification, solution techniques, and applications. Comput. Ind. Eng. 64(4), 1096–1109 (2013)

    Article  Google Scholar 

  17. Feldmann, A.E.: Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs. Algorithmica 81(3), 1031–1052 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  18. Feldmann, A.E., Karthik, C., Lee, E., Manurangsi, P.: A survey on approximation in parameterized complexity: hardness and algorithms. Algorithms 13(6), 146 (2020)

    Article  MathSciNet  Google Scholar 

  19. Feldmann, A.E., Marx, D.: The parameterized hardness of the \(k\)-center problem in transportation networks. Algorithmica 82(7), 1989–2005 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  20. Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 493–502. SIAM (2010)

    Google Scholar 

  21. Ge, D., He, S., Ye, Y., Zhang, J.: Geometric rounding: a dependent randomized rounding scheme. J. Comb. Optim. 22(4), 699–725 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gelareh, S., Pisinger, D.: Fleet deployment, network design and hub location of liner shipping companies. Transp. Res. Part E: Logist. Transp. Rev. 47(6), 947–964 (2011)

    Article  Google Scholar 

  23. Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38, 293–306 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  24. Goyal, D., Jaiswal, R.: Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier. arXiv preprint arXiv:2110.14242 (2021)

  25. Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the \(k\)-center problem. Math. Oper. Res. 10(2), 180–184 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  27. Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for Bottleneck problems. J. ACM 33(3), 533–550 (1986)

    Article  MathSciNet  Google Scholar 

  28. Iwasa, M., Saito, H., Matsui, T.: Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems. Discret. Appl. Math. 157(9), 2078–2088 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  29. Jaillet, P., Song, G., Yu, G.: Airline network design and hub location problems. Locat. Sci. 4(3), 195–212 (1996)

    Article  MATH  Google Scholar 

  30. Kara, B.Y., Tansel, B.: On the single-assignment \(p\)-hub center problem. Eur. J. Oper. Res. 125(3), 648–655 (2000)

    Article  MATH  Google Scholar 

  31. Karimi, H., Bashiri, M.: Hub covering location problems with different coverage types. Scientia Iranica 18(6), 1571–1578 (2011)

    Article  Google Scholar 

  32. Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for \((k, r)\)-center. Discret. Appl. Math. 264, 90–117 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  33. Kloks, T.: Treewidth: Computations and Approximations, vol. 842. Springer Science & Business Media (1994). https://doi.org/10.1007/BFb0045388

  34. Lampis, M.: Parameterized approximation schemes using graph widths. In: International Colloquium on Automata, Languages, and Programming, pp. 775–786. Springer (2014). https://doi.org/10.1007/978-3-662-43948-7_64

  35. Liang, H.: The hardness and approximation of the star \(p\)-hub center problem. Oper. Res. Lett. 41(2), 138–141 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  36. Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60–78 (2008)

    Article  Google Scholar 

  37. O’Kelly, M.E.: The location of interacting hub facilities. Transp. Sci. 20(2), 92–106 (1986)

    Article  Google Scholar 

  38. O’Kelly, M.E.: A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32(3), 393–404 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  39. Pedrosa, L.L.C., dos Santos, V.F., Schouery, R.C.S.: Uma aproximação para o problema de alocação de terminais. In: Anais do CSBC, ETC (2016)

    Google Scholar 

  40. Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)

    Google Scholar 

  41. Yaman, H., Elloumi, S.: Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths. Comput. Oper. Res. 39(11), 2725–2732 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  42. Yang, T.H.: Stochastic air freight hub location and flight routes planning. Appl. Math. Model. 33(12), 4424–4430 (2009)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computing, University of Campinas, Campinas, Brazil

    Marcelo P. L. Benedito, Lucas P. Melo & Lehilton L. C. Pedrosa

Authors
  1. Marcelo P. L. Benedito
    View author publications

    Search author on:PubMed Google Scholar

  2. Lucas P. Melo
    View author publications

    Search author on:PubMed Google Scholar

  3. Lehilton L. C. Pedrosa
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Marcelo P. L. Benedito .

Editor information

Editors and Affiliations

  1. Universidad Nacional Autónoma de México, Mexico City, Mexico

    Armando Castañeda

  2. Centro de investigación y de Estudios Avanzados, Mexico City, Mexico

    Francisco Rodríguez-Henríquez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Benedito, M.P.L., Melo, L.P., Pedrosa, L.L.C. (2022). A Parameterized Approximation Algorithm for the Multiple Allocation k-Hub Center. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-20624-5_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-20623-8

  • Online ISBN: 978-3-031-20624-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics