\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

An approximation algorithm for the $k$-level facility location problem with submodular penalties

Abstract Related Papers Cited by
  • In this paper, we consider the $k$-level facility location problem with submodular penalties ($k$-FLPSP). We propose a primal-dual $6$-approximation (combinatorial) algorithm for the $k$-FLPSP.
    Mathematics Subject Classification: Primary: 90C59; Secondary: 90C10.

    Citation:

    \begin{equation} \\ \end{equation}
  • [1]

    K. I. Aardal, F. A. Chudak and D. B. Shmoys, A $3$-approximation algorithm for the $k$-level uncapacitaed facility location problem, Information Processing Letters, 72 (1999), 161-167.doi: 10.1016/S0020-0190(99)00144-1.

    [2]

    A. Ageev, Y. Ye and J. Zhang, Improved combinatorial approximation algorithms for the $k$-level facility location problem, SIAM Journal on Discrete Mathmatics, 18 (2004), 207-217.doi: 10.1137/S0895480102417215.

    [3]

    A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem, in "Approximation, Randomization, and Combinatorial Optimization" (Berkeley, CA, 2001), Lecture Notes in Comput. Sci., 2129, Springer, Berlin, (2001), 55-62.

    [4]

    J. Byrka and K. I. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM Journal on Computing, 39 (2010), 2212-2231.doi: 10.1137/070708901.

    [5]

    M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers, in "Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms" (Washington, DC, 2001), SIAM, Philadelphia, PA, (2001), 642-651.

    [6]

    X. Chen and B. Chen, Approximation algorithms for soft-capacitated facility location in capacitated network design, Algorithmica, 53 (2009), 263-297.doi: 10.1007/s00453-007-9032-7.

    [7]

    F. A. Chudak and K. Nagano, Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization, in "Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2007), 79-88.

    [8]

    D. Du, R. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63 (2012), 191-200.doi: 10.1007/s00453-011-9526-1.

    [9]

    L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics, 131 (2003), 311-322.doi: 10.1016/S0166-218X(02)00458-4.

    [10]

    S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, in "Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms" (San Francisco, CA, 1998), ACM, New York, (1998), 649-657.

    [11]

    A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks, in "Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2005), 933-942.

    [12]

    K. Jain, M. Mahdian, E. Markakis, A. Saberi and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM, 50 (2003), 795-824.doi: 10.1145/950620.950621.

    [13]

    K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and $k$-median probelms using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48 (2001), 274-296.doi: 10.1145/375827.375845.

    [14]

    G. Li, Z. Wang and D. Xu, An approximation algorithm for the $k$-level facility location problem with submodular penalties, in "Global Optimization: Theory, Methods & Applications I, Lecture Notes in Decision Sciences'' (eds. C. Ma, L. Yu, D. Zhang and Z. Zhou), 12 (2009), 772-777.

    [15]

    S. Li, A 1.488-approximation algorithm for the uncapacitated facility location problem, in "Proceedings of Automata, Languages and Programming," Part II, Lecture Notes in Comput. Sci., 6756, Springer, Heidelberg, (2011), 77-88.

    [16]

    M. Mahdian, Y. Ye and J. Zhang, Approximation algorithms for metric facility location problems, SIAM Journal on Computing, 36 (2006), 411-432.doi: 10.1137/S0097539703435716.

    [17]

    J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization, Transportation Science, 44 (2010), 183-192.doi: 10.1287/trsc.1090.0302.

    [18]

    J. Shu, Q. Ma and S. Li, Integrated location and two-echelon inventory network design under uncertainty, Annals of Operations Research, 181 (2010), 233-241.doi: 10.1007/s10479-010-0732-z.

    [19]

    J. Shu, C.-P. Teo and Z.-J. Max Shen, Stochastic transportation-inventory network design problem, Operations Research, 53 (2005), 48-60.doi: 10.1287/opre.1040.0140.

    [20]

    D. B. Shmoys, E. Tardos and K. I. Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of STOC, (1997), 265-274.

    [21]

    G. Xu and J. Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, Information Processing Letters, 94 (2005), 119-123.doi: 10.1016/j.ipl.2005.01.005.

    [22]

    G. Xu and J. Xu, An improved approximation algorithm for uncapacitated facility location problem with penalties, Journal of Combinatorial Optimization, 17 (2009), 424-436.doi: 10.1007/s10878-007-9127-8.

    [23]

    J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach, Mathematical Programming, 108 (2006), 159-176.doi: 10.1007/s10107-006-0704-x.

    [24]

    J. Zhang, B. Chen and Y. Ye, A multiexchange local search algorithm for the capacitated facility location problem, Mathematics of Operations Research, 30 (2005), 389-403.doi: 10.1287/moor.1040.0125.

    [25]

    L. Zhang and S.-Y. Wu, Robust solutions to Euclidean facility location problems with uncertain data, Journal of Industrial and Management Optimization, 6 (2010), 751-760.

    [26]

    P. Zhang, A new approximation algorithm for the $k$-facility location problem, Theoretical Computer Science, 384 (2007), 126-135.doi: 10.1016/j.tcs.2007.05.024.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(76) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return