IDEAS home Printed from https://ideas.repec.org/p/ebg/essewp/dr-05003.html
   My bibliography  Save this paper

Improved Approximation of the General Soft-Capacitated Facility Location Problem

Author

Listed:

Abstract

An NP-hard variant of the single-source Capacitated Facility Location Problem is studied, where each facility is composed of a variable number of fixed-capacity production units. This problem, especially the metric case, has been recently studied in several papers. In this paper, we only consider the general problem where connection costs do not systematically satisfy the triangle inequality property. We show that an adaptation of the set covering greedy heuristic, where the sub-problem is approximately solved by a Fully Polynomial-Time Approximation Scheme based on cost scaling and dynamic programming, achieves a logarithmic approximation ratio of (1+ƒÕ)H(n) for the problem, where n is the number of clients to be served, and H is the harmonic series. This improves the previous bound of 2H(n) for this problem.

Suggested Citation

  • Alfandari, Laurent, 2005. "Improved Approximation of the General Soft-Capacitated Facility Location Problem," ESSEC Working Papers DR 05003, ESSEC Research Center, ESSEC Business School.
    • Handle: RePEc:ebg:essewp:dr-05003
    as

    Download full text from publisher

    File URL: http://www.essec.fr/faculty/showDeclFileRes.do?declId=3996&key=__workpaper__
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. V. Chvatal, 1979. "A Greedy Heuristic for the Set-Covering Problem," Mathematics of Operations Research, INFORMS, vol. 4(3), pages 233-235, August.
    2. Refael Hassin, 1992. "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 36-42, February.
    3. Eugene L. Lawler, 1979. "Fast Approximation Algorithms for Knapsack Problems," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 339-356, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Turken, Nazli & Carrillo, Janice & Verter, Vedat, 2017. "Facility location and capacity acquisition under carbon tax and emissions limits: To centralize or to decentralize?," International Journal of Production Economics, Elsevier, vol. 187(C), pages 126-141.

    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. Jenkins , Alan, 2005. "Performance Appraisal Research: A Critical Review of Work on “The Social Context and Politics of Appraisal”," ESSEC Working Papers DR 05004, ESSEC Research Center, ESSEC Business School.
    2. Larry W. Jacobs & Michael J. Brusco, 1995. "Note: A local‐search heuristic for large set‐covering problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(7), pages 1129-1140, October.
    3. Dolgui, Alexandre & Kovalev, Sergey & Pesch, Erwin, 2015. "Approximate solution of a profit maximization constrained virtual business planning problem," Omega, Elsevier, vol. 57(PB), pages 212-216.
    4. Bretthauer, Kurt M. & Shetty, Bala, 2002. "The nonlinear knapsack problem - algorithms and applications," European Journal of Operational Research, Elsevier, vol. 138(3), pages 459-472, May.
    5. Raka Jovanovic & Antonio P. Sanfilippo & Stefan Voß, 2022. "Fixed set search applied to the multi-objective minimum weighted vertex cover problem," Journal of Heuristics, Springer, vol. 28(4), pages 481-508, August.
    6. 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.
    7. Haris Aziz & Sujit Gujar & Manisha Padala & Mashbat Suzuki & Jeremy Vollen, 2022. "Coordinating Monetary Contributions in Participatory Budgeting," Papers 2206.05966, arXiv.org, revised Feb 2023.
    8. Imran Khan & Naveed Riaz, 2015. "A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI)," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 25(4), pages 5-18.
    9. Pál Pusztai, 2008. "An application of the greedy heuristic of set cover to traffic checks," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 16(4), pages 407-414, December.
    10. Daria Dzyabura & Srikanth Jagabathula, 2018. "Offline Assortment Optimization in the Presence of an Online Channel," Management Science, INFORMS, vol. 64(6), pages 2767-2786, June.
    11. Li, Jianping & Ge, Yu & He, Shuai & Lichen, Junran, 2014. "Approximation algorithms for constructing some required structures in digraphs," European Journal of Operational Research, Elsevier, vol. 232(2), pages 307-314.
    12. Shisheng Li & T.C.E. Cheng & C.T. Ng & Jinjiang Yuan, 2017. "Two‐agent scheduling on a single sequential and compatible batching machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 628-641, December.
    13. Hanif D. Sherali & Seong‐In Kim & Edna L. Parrish, 1991. "Probabilistic partial set covering problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(1), pages 41-51, February.
    14. Strehler, Martin & Merting, Sören & Schwan, Christian, 2017. "Energy-efficient shortest routes for electric and hybrid vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 111-135.
    15. Michael Zabarankin & Stan Uryasev & Robert Murphey, 2006. "Aircraft routing under the risk of detection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(8), pages 728-747, December.
    16. Rui Diao & Ya-Feng Liu & Yu-Hong Dai, 2017. "A new fully polynomial time approximation scheme for the interval subset sum problem," Journal of Global Optimization, Springer, vol. 68(4), pages 749-775, August.
    17. Jia Shu, 2010. "An Efficient Greedy Heuristic for Warehouse-Retailer Network Design Optimization," Transportation Science, INFORMS, vol. 44(2), pages 183-192, May.
    18. Zhenbo Wang & Wenxun Xing, 2009. "A successive approximation algorithm for the multiple knapsack problem," Journal of Combinatorial Optimization, Springer, vol. 17(4), pages 347-366, May.
    19. Davidov, Sreten & Pantoš, Miloš, 2017. "Planning of electric vehicle infrastructure based on charging reliability and quality of service," Energy, Elsevier, vol. 118(C), pages 1156-1167.
    20. Li Guan & Jianping Li & Weidong Li & Junran Lichen, 2019. "Improved approximation algorithms for the combination problem of parallel machine scheduling and path," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 689-697, October.

    More about this item

    Keywords

    Facility Location; Combinatorial optimization; Set Covering; Dynamic Programming; Approximation;
    All these keywords.

    JEL classification:

    • C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory
    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    Statistics

    Access and download statistics

    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:ebg:essewp:dr-05003. 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: Sophie Magnanou (email available below). General contact details of provider: https://edirc.repec.org/data/essecfr.html .

    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.