IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v35y2018i2d10.1007_s10878-017-0192-3.html
   My bibliography  Save this article

An approximation algorithm for soft capacitated k-facility location problem

Author

Listed:
  • Yanjun Jiang

    (Beijing University of Technology)

  • Dachuan Xu

    (Beijing University of Technology)

  • Donglei Du

    (University of New Brunswick)

  • Chenchen Wu

    (Tianjin University of Technology)

  • Dongmei Zhang

    (Shandong Jianzhu University)

Abstract

We present a $$(20+{5}/{n})$$ ( 20 + 5 / n ) -approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal–dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.

Suggested Citation

  • Yanjun Jiang & Dachuan Xu & Donglei Du & Chenchen Wu & Dongmei Zhang, 2018. "An approximation algorithm for soft capacitated k-facility location problem," Journal of Combinatorial Optimization, Springer, vol. 35(2), pages 493-511, February.
    • Handle: RePEc:spr:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0192-3
    DOI: 10.1007/s10878-017-0192-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-017-0192-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-017-0192-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Alfred A. Kuehn & Michael J. Hamburger, 1963. "A Heuristic Program for Locating Warehouses," Management Science, INFORMS, vol. 9(4), pages 643-666, July.
    2. Jiawei Zhang & Bo Chen & Yinyu Ye, 2005. "A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem," Mathematics of Operations Research, INFORMS, vol. 30(2), pages 389-403, May.
    3. Aardal, Karen & van den Berg, Pieter L. & Gijswijt, Dion & Li, Shanfei, 2015. "Approximation algorithms for hard capacitated k-facility location problems," European Journal of Operational Research, Elsevier, vol. 242(2), pages 358-368.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lu Han & Dachuan Xu & Donglei Du & Dongmei Zhang, 2018. "A local search approximation algorithm for the uniform capacitated k-facility location problem," Journal of Combinatorial Optimization, Springer, vol. 35(2), pages 409-423, February.
    2. Aardal, Karen & van den Berg, Pieter L. & Gijswijt, Dion & Li, Shanfei, 2015. "Approximation algorithms for hard capacitated k-facility location problems," European Journal of Operational Research, Elsevier, vol. 242(2), pages 358-368.
    3. Fengmin Wang & Dachuan Xu & Chenchen Wu, 2016. "Combinatorial approximation algorithms for the robust facility location problem with penalties," Journal of Global Optimization, Springer, vol. 64(3), pages 483-496, March.
    4. Faiz, Tasnim Ibn & Noor-E-Alam, Md, 2019. "Data center supply chain configuration design: A two-stage decision approach," Socio-Economic Planning Sciences, Elsevier, vol. 66(C), pages 119-135.
    5. Dongmei Zhang & Dachuan Xu & Yishui Wang & Peng Zhang & Zhenning Zhang, 2018. "A local search approximation algorithm for a squared metric k-facility location problem," Journal of Combinatorial Optimization, Springer, vol. 35(4), pages 1168-1184, May.
    6. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    7. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    8. Lu Han & Dachuan Xu & Donglei Du & Dongmei Zhang, 0. "An approximation algorithm for the uniform capacitated k-means problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-12.
    9. Antunes, Antonio & Peeters, Dominique, 2000. "A dynamic optimization model for school network planning," Socio-Economic Planning Sciences, Elsevier, vol. 34(2), pages 101-120, June.
    10. Davood Shishebori & Lawrence Snyder & Mohammad Jabalameli, 2014. "A Reliable Budget-Constrained FL/ND Problem with Unreliable Facilities," Networks and Spatial Economics, Springer, vol. 14(3), pages 549-580, December.
    11. R. Suárez-Vega & D. Santos-Peñate & P. Dorta-González, 2004. "Discretization and resolution of the (r|X p )-medianoid problem involving quality criteria," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 111-133, June.
    12. Zvi Drezner & Jack Brimberg & Nenad Mladenović & Said Salhi, 2016. "New local searches for solving the multi-source Weber problem," Annals of Operations Research, Springer, vol. 246(1), pages 181-203, November.
    13. Antunes, Antonio & Peeters, Dominique, 2001. "On solving complex multi-period location models using simulated annealing," European Journal of Operational Research, Elsevier, vol. 130(1), pages 190-201, April.
    14. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    15. Mohammad Ehsanifar & David A. Wood & Arezoo Babaie, 2021. "UTASTAR method and its application in multi-criteria warehouse location selection," Operations Management Research, Springer, vol. 14(1), pages 202-215, June.
    16. Mauricio Resende & Renato Werneck, 2007. "A fast swap-based local search procedure for location problems," Annals of Operations Research, Springer, vol. 150(1), pages 205-230, March.
    17. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    18. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    19. Wenjun Ni & Jia Shu & Miao Song & Dachuan Xu & Kaike Zhang, 2021. "A Branch-and-Price Algorithm for Facility Location with General Facility Cost Functions," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 86-104, January.
    20. Li‐Lian Gao & E. Powell Robinson, 1992. "A dual‐based optimization procedure for the two‐echelon uncapacitated facility location problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 191-212, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0192-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.