skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Improved Approximation Guarantees for Lower-Bounded Facility Location

Approximation and Online Algorithms, p.257-271 [Peer Reviewed Journal]

Springer-Verlag Berlin Heidelberg 2013 ;ISSN: 0302-9743 ;ISBN: 3642380158 ;ISBN: 9783642380150 ;EISSN: 1611-3349 ;EISBN: 9783642380167 ;EISBN: 3642380166 ;DOI: 10.1007/978-3-642-38016-7_21

Full text available

Citations Cited by
  • Title:
    Improved Approximation Guarantees for Lower-Bounded Facility Location
  • Author: Ahmadian, Sara ; Swamy, Chaitanya
  • Subjects: Approximation Ratio ; Demand Point ; Facility Location ; Facility Location Problem ; Network Design Problem
  • Is Part Of: Approximation and Online Algorithms, p.257-271
  • Description: We consider the lower-bounded facility location (LBFL) problem, which is a generalization of uncapacitated facility location (UFL), where each open facility is required to serve a certain minimum amount of demand. The current best approximation ratio for LBFL is 448 [17]. We substantially advance the state-of-the-art for LBFL by improving its approximation ratio from 448 [17] to 82.6. Our improvement comes from a variety of ideas in algorithm design and analysis, which also yield new insights into LBFL. Our chief algorithmic novelty is to present an improved method for solving a more-structured LBFL instance obtained from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\ensuremath{\mathcal I}$\end{document} via a bicriteria approximation algorithm for LBFL, wherein all clients are aggregated at a subset \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\ensuremath{\mathcal F}'$\end{document} of facilities, each having at least αM co-located clients (for some α ∈ [0,1]). The algorithm in [17] proceeds by reducing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\ensuremath{\mathcal I}_2(\ensuremath{\alpha})$\end{document} to CFL. One of our key insights is that one can reduce the resulting LBFL instance, denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\ensuremath{\mathcal I}_2(\ensuremath{\alpha})$\end{document}, to a problem we introduce, called capacity-discounted UFL (CDUFL), which is a structured special case of capacitated facility location (CFL). We give a simple local-search algorithm for CDUFL based on add, delete, and swap moves that achieves a significantly-better approximation ratio than the current-best approximation ratio for CFL, which is one of the reasons behind our algorithm’s improved approximation ratio.
  • Publisher: Berlin, Heidelberg: Springer Berlin Heidelberg
  • Language: English
  • Identifier: ISSN: 0302-9743
    ISBN: 3642380158
    ISBN: 9783642380150
    EISSN: 1611-3349
    EISBN: 9783642380167
    EISBN: 3642380166
    DOI: 10.1007/978-3-642-38016-7_21
  • Source: Alma/SFX Local Collection
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait