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. 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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Hifi, Mhand & M'Hallah, Rym, 2006. "Strip generation algorithms for constrained two-dimensional two-staged cutting problems," European Journal of Operational Research, Elsevier, vol. 172(2), pages 515-527, July.
    11. Filipe Rodrigues & Agostinho Agra & Lars Magnus Hvattum & Cristina Requejo, 2021. "Weighted proximity search," Journal of Heuristics, Springer, vol. 27(3), pages 459-496, June.
    12. Lan, Guanghui & DePuy, Gail W. & Whitehouse, Gary E., 2007. "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1387-1403, February.
    13. Song, Zhe & Kusiak, Andrew, 2010. "Mining Pareto-optimal modules for delayed product differentiation," European Journal of Operational Research, Elsevier, vol. 201(1), pages 123-128, February.
    14. Seona Lee & Sang-Ho Lee & HyungJune Lee, 2020. "Timely directional data delivery to multiple destinations through relay population control in vehicular ad hoc network," International Journal of Distributed Sensor Networks, , vol. 16(5), pages 15501477209, May.
    15. Zhong, Weiya & Dosa, Gyorgy & Tan, Zhiyi, 2007. "On the machine scheduling problem with job delivery coordination," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1057-1072, November.
    16. Esaignani Selvarajah & Rui Zhang, 2014. "Supply chain scheduling to minimize holding costs with outsourcing," Annals of Operations Research, Springer, vol. 217(1), pages 479-490, June.
    17. Zhuang, Yanling & Zhou, Yun & Yuan, Yufei & Hu, Xiangpei & Hassini, Elkafi, 2022. "Order picking optimization with rack-moving mobile robots and multiple workstations," European Journal of Operational Research, Elsevier, vol. 300(2), pages 527-544.
    18. Randeep Bhatia & Sudipto Guha & Samir Khuller & Yoram J. Sussmann, 1998. "Facility Location with Dynamic Distance Functions," Journal of Combinatorial Optimization, Springer, vol. 2(3), pages 199-217, September.
    19. Menghong Li & Yingli Ran & Zhao Zhang, 2022. "A primal-dual algorithm for the minimum power partial cover problem," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1913-1923, October.
    20. Briskorn, Dirk & Choi, Byung-Cheon & Lee, Kangbok & Leung, Joseph & Pinedo, Michael, 2010. "Complexity of single machine scheduling subject to nonnegative inventory constraints," European Journal of Operational Research, Elsevier, vol. 207(2), pages 605-619, December.

    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.