Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 23 Issue 5
September  2008
Turn off MathJax
Article Contents
References
Related Articles
Wei-Lin Li, Peng Zhang, Da-Ming Zhu. On Constrained Facility Location Problems[J]. Journal of Computer Science and Technology, 2008, 23(5): 740-748.
Citation: Wei-Lin Li, Peng Zhang, Da-Ming Zhu. On Constrained Facility Location Problems[J]. Journal of Computer Science and Technology, 2008, 23(5): 740-748.
shu

On Constrained Facility Location Problems

  • 1State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China2Graduate University of Chinese Academy of Sciences, Beijing 100190, China3School of Computer Science and Technology, Shandong University, Jinan 250101, China

More Information
  • Revised Date: July 07, 2008
  • Published Date: September 09, 2008
    Abstract
    • FullText(HTML)
    • References (18)
  • [1] Love R, Morris J, Wesolowsky G. Facilities Location: Models and Methods. North Holland, New York: Appleton \& Lange, 1988.
    [2]
    } Mirchandani P, Francis R (eds). Discrete Location Theory. New York: John Wiley \& Sons, 1990.
    [3]
    } Shmoys D. Approximation algorithms for facility location problems. In {\it Proc. the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization}, {\it LNCS 1913}, Saarbr\"ucken, Germany, September 5--8, 2000, pp.27--33.
    [4]
    } Hochbaum D. Heuristic for the fixed cost median problem. {\it Mathematical Programming}, 1982, 22(2): 148--162.
    [5]
    } Chudak F. Improved approximation algorithms for uncapitated facility location. In {\it Proc. the 6th International Conference on Integer Programming and Combinatorial Optimization}, {\it LNCS 1412}, Houston, Texas, June 22--24, 1998, pp.180--194.
    [6]
    } Jain K, Vazirani V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. {\it Journal of the ACM}, 2001, 48(2): 274--296.
    [7]
    } Jain K, Mahdian M, Markakis E, Saberi A, Vazirani V. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. {\it Journal of the ACM}, 2003, 50(6): 795--824.
    [8]
    } Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V. Local search heuristic for k-median and facility location problem. {\it SIAM Journal on Computing}, 2004, 33(3): 544--562.
    [9]
    } Pan R, Zhu D M, Ma S H, Xiao J J. Approximated computational hardness and local search approximated algorithm analysis for k-median problem. {\it Journal of Software}, 2005, 16(3): 392--399. (in Chinese)
    [10]
    } Pan R, Zhu D M, Ma S H. Research on computational complexity and approximation algorithm for general facility location problem. {\it Journal of Computer Research and Development}, 2007, 44(5): 790--797. (in Chinese)
    [11]
    } Mahdian M, Ye Y Y, Zhang J W. Improved approximation algorithms for metric facility location problems. In {\it Proc. the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization}, {\it LNCS} 2462, Rome, Italy, September 17--21, 2002, pp.229--242.
    [12]
    } Zhang P. A new approximation algorithm for the k-Facility Location problem. {\it Theoretical Computer Science}, 2007, 384(1): 126--135.
    [13]
    } Arora S, Raghavan P, Rao S. Approximation schemes for Euclidean k-Median and related problems. In {\it Proc. the 30th Annual ACM Symposium on Theory of Computing}, Dallas, Texas, United States, May 24--26, 1998, pp.106--113.
    [14]
    } Beasley J. Operations research library, 2007, Available at http://people.brunel.ac.uk/∼mastjjb/\\jeb/orlib/uncapinfo.html.
    [15]
    } Guha S, Khuller S. Greedy strikes back: Improved facility location algorithms. {\it Journal of Algorithms}, 1999, 31(1): 228--248.
    [16]
    } Charikar M, Guha S. Improved combinatorial algorithms for the facility location and k-median problems. In {\it Proc. the 40th IEEE Annual Symposium on Foundations of Computer Science}, New York, United States, October 17--19, 1999, pp.378--388.
    [17]
    } Korupolu M, Plaxton C, Rajaraman R. Analysis of a local search heuristic for facility location problems. {\it Journal of Algorithms}, 2000, 37(1): 146--188.
    [18]
    } Feige U. A threshold of lnn for approximating set cover. {\it Journal of the ACM}, 1998, 45(4): 634--652.
    • Relative Articles

  • Related Articles

    [1]Zhi-Han Chen, Shao-Wei Cai, Jian Gao, Shi-Ke Ge, Chan-Juan Liu, Jin-Kun Lin. Heuristic Search with Cut Point Based Strategy for Critical Node Problem[J]. Journal of Computer Science and Technology, 2024, 39(6): 1328-1340. DOI: 10.1007/s11390-024-2850-0
    [2]Wen-Sheng Guo, Guo-Wu Yang, William N. N. Hung, Xiaoyu Song. Complete Boolean Satisfiability Solving Algorithms Based on Local Search[J]. Journal of Computer Science and Technology, 2013, 28(2): 247-254. DOI: 10.1007/s11390-013-1326-4
    [3]Jian-Xin Wang, Xiao-Shuang Xu, Jian-Er Chen. Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs[J]. Journal of Computer Science and Technology, 2008, 23(5): 763-768.
    [4]Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Th&oumlle, Henning Thomas. Approximation Algorithms for 3D Orthogonal Knapsack[J]. Journal of Computer Science and Technology, 2008, 23(5): 749-762.
    [5]Ya-Feng Wu, Yin-Long Xu, Guo-Liang Chen. Approximation Algorithms for Steiner Connected Dominating Set[J]. Journal of Computer Science and Technology, 2005, 20(5): 713-716.
    [6]Zi-Mao Li, Da-Ming Zhu, Shao-Han Ma. Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [7]JING Tong, HONG XianLong, BAO HaiYun, XU JingYu, GU Jun. SSTT: Efficient Local Search for GSI Global Routing[J]. Journal of Computer Science and Technology, 2003, 18(5).
    [8]HE Yong, CHEN Ting. A New Approximation Algorithm for Sorting of Signed Permutations[J]. Journal of Computer Science and Technology, 2003, 18(1).
    [9]HUANG Wenqi, ZHANG Defu, WANG Houxiang. An Algorithm Based on Tabu Search for Satisfiability Problem[J]. Journal of Computer Science and Technology, 2002, 17(3).
    [10]ZHANG Li'ang, ZHANG Yin. Approximation for- Knapsack Problemswith Multiple Constraints[J]. Journal of Computer Science and Technology, 1999, 14(4): 289-297.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (22) PDF downloads (1988) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return