Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 109: | Строка 109: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основными нерешенными вопросами являются определение точного порога аппроксимируемости для задачи UFL и сокращение разрыва между верхней границей 1,5 [10] и нижней границей 1,463 [20]. Еще одна важная задача заключается в поиске лучших алгоритмов аппроксимации для задачи о k-медианах. В частности, любопытно было бы найти алгоритм аппроксимации для этой задачи с коэффициентом 2 на базе LP-подхода. Такой алгоритм помог бы определить разрыв целостности естественной LP-релаксации этой задачи, поскольку существуют простые примеры, доказывающие, что этот разрыв составляет не менее 2. | |||
== Экспериментальные результаты == | |||
Джейн и др. [28] опубликовали результаты экспериментального сравнения различных прямо-двойственных алгоритмов. Более комплексное экспериментальное исследование нескольких алгоритмов – прямо-двойственных, на базе локального поиска и эвристических – было выполнено Хефером [27]. Коллекцию наборов данных для UFL и некоторых других задач о размещении объектов можно найти в библиотеке OR-library под руководством Бизли [9]. | |||
== См. также == | |||
* [[Задача присваивания]] | |||
* [[Упаковка контейнеров (задача о размещении объектов с жесткими ограничениями на пропускную способность без возможности разделения спроса)]] | |||
* [[Компоновка схемы]] | |||
* [[Жадные алгоритмы покрытия множества (вариант UFL с жесткими ограничениями, в котором объекты могут строиться в любых местоположениях по одной и той же стоимости)]] | |||
* [[Локальные аппроксимации задач упаковки и покрытия]] | |||
* [[Локальный поиск для задачи о k-медианах и задачи о размещении объектов]] | |||
== Литература == | |||
1. Aardal, K., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inf. Process. Lett. 72,161-167 (1999) | |||
2. Ageev, A.A., Sviridenko, M.I.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discret.Appl. Math. 93,149-156 (1999) | |||
3. Anagnostopoulos, A., Bent, R., Upfal, E., van Hentenryck, P.: A simple and deterministic competitive algorithm for online facility location. Inf. Comput. 194(2), 175-202 (2004) | |||
4. Andrews, M., Zhang, L.:The access network design problem. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 40-49. IEEE Computer Society, Los Alamitos, CA, USA (1998) | |||
5. Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 106-113. ACM, New York (1998) | |||
6. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 21 -29. ACM, New York (2001) | |||
7. Balinski, M.L.: On finding integer solutions to linear programs. In: Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pp. 225-248 IBM, White Plains, NY (1966) | |||
8. Balinski, M.L., Wolfe, P.: On Benders decomposition and a plant location problem. In ARO-27. Mathematica Inc. Princeton (1963) | |||
9. Beasley, J.E.: Operations research library. http://people.brunel.ac.uk/~mastjjb/jeb/info.html. Accessed 2008 | |||
10. Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Computer Science, vol. 4627, pp. 29-43. Springer, Berlin (2007) | |||
11. Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: Proceedings of the 31 st Annual ACM Symposium on Theory of Computing (STOC), pp. 1-10. ACM, New York (1999) | |||
12. Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Facility location with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 642-651. SIAM, Philadelphia (2001) | |||
13. Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM JComput.33(1), 1-25(2003) | |||
14. Chudak, F.A., Wiliamson, D.P.: Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th Conference on Integer Programing and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 1610, pp. 99-113. Springer, Berlin (1999) | |||
15. Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Manag. Sci.8, 789-810 (1977) | |||
16. Erlenkotter, D.: A dual-based procedure for uncapacitated facility location problems. Oper. Res. 26,992-1009 (1978) | |||
17. Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45,634-652 (1998) | |||
18. Fotakis, D.: On the competitive ratio for online facility location. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719, pp. 637-652. Springer, Berlin (2003) | |||
19. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 228-248. SIAM, Philadelphia (1998) | |||
20. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31, 228-248 (1999) | |||
21. Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 383-388. ACM Press, New York (2001) | |||
22. Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 603-612. IEEE Computer Society, Los Alamitos, CA, USA (2000) | |||
23. Gupta, A., Pal, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36st Annual ACM Symposium on Theory of Computing (STOC), pp. 417-426. ACM, New York (2004) | |||
24. Hajiaghayi, M., Mahdian, M., Mirrokni, V.S.: The facility location problem with general cost functions. Netw. 42(1), 42-47 (2003) | |||
25. Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22(2), 148-162(1982) | |||
26. Hochbaum, D.S., Shmoys, D.B.: A best possible approximation algorithm for the k-center problem. Math. Oper. Res. 10, 180-184(1985) | |||
27. Hoefer, M.: Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location. In: Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA). Lecture Notes in Computer Science, vol. 2647, pp. 165-178. Springer, Berlin (2003) | |||
28. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Approximation algorithms for facility location via dual fitting with factor-revealing LP. J. ACM 50(6), 795-824 (2003) | |||
29. Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34st Annual ACM Symposium on Theory of Computing (STOC) pp. 731-740, ACM Press, New York (2002) | |||
30. Jain, K., Vazirani, V.V.: An approximation algorithm for the fault tolerant metric facility location problem. In: Approximation Algorithms for Combinatorial Optimization, Proceedings of APPROX (2000), vol. (1913) of Lecture Notes in Computer Science, pp. 177-183. Springer, Berlin (2000) | |||
31. Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., Zhang, L.: On the placement of internet instrumentations. In: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 1, pp. 295-304. IEEE Computer Society, Los Alamitos, CA, USA (2000) | |||
32. Karger, D., Minkoff, M.: Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, pp. 613-623. Los Alamitos (2000) | |||
33. Krarup, J., Pruzan, P.M.: Ingredients of locational analysis. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 1-54.Wiley,NewYork(1990) | |||
34. Krarup, J., Pruzan, P.M.:The simple plant location problem: Survey and synthesis. Eur. J.Oper. Res. 12, 38-81 (1983) | |||
35. Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manag. Sci.9, 643-666 (1963) | |||
36. Li, B., Golin, M., Italiano, G., Deng, X., Sohraby, K.: On the optimal placement of web proxies in the internet. In: Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1282—1290. IEEE Computer Society, Los Alamitos (1999) | |||
37. Mahdian, M.: Facility Location and the Analysis of Algorithms through Factor-Revealing Programs. Ph.D. thesis, MIT, Cambridge (2004) | |||
38. Mahdian, M., Pal, M.: Universal facility location. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2832, pp. 409-421. Springer, Berlin (2003) | |||
39. Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411-432 (2006) | |||
40. Manne, A.S.: Plant location under economies-of-scale - decentralization and computation. Manag. Sci.11,213-235 (1964) | |||
41. Meyerson, A.: Online facility location. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 426-431. IEEE Computer Society, Los Alamitos (2001) | |||
42. Mirchandani, P.B., Francis, R.L.: Discrete Location Theory. Wiley, New York (1990) | |||
43. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1990) | |||
44. Pal, M., Tardos, E., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 329-338. IEEE Computer Society, Los Alamitos (2001) | |||
45. Qiu, L., Padmanabhan, V.N., Voelker, G.: On the placement of web server replicas. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ), pp. 1587-1596. IEEE Computer Society, Los Alamitos (2001) | |||
46. Ravi, R., Sinha, A.: Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Math. Program. 108(1),97-114(2006) | |||
47. Ravi, R., Sinha, A.: Integrated logistics: Approximation algorithms combining facility location and network design. In: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 2337, pp. 212-229. Springer, Berlin (2002) | |||
48. Ravi, R., Sinha, A.: Multicommodity facility location. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 342-349. SIAM, Philadelphia (2004) | |||
49. Shmoys, D.B.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) Approximation Algorithms for Combinatorial Optimization. Lecture Notes in Computer Science, vol. 1913, pp. 27-33. Springer, Berlin (2000) | |||
50. Shmoys, D.B.: The design and analysis of approximation algorithms: Facility location as a case study. In: Thomas, R.R., Hosten, S., Lee, J. (eds) Proceedings of Symposia in Appl. Mathematics, vol. 61, pp. 85-97. AMS, Providence, RI, USA (2004) | |||
51. Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 265-274. ACM Press, New York (1997) | |||
52. Svitkina, Z., Tardos, E.: Facility location with hierarchical facility costs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 153-161. SIAM, Philadelphia, PA, USA (2006) | |||
53. Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245-269 (2004) | |||
54. Swamy, C., Shmoys, D.B.: Fault-tolerant facility location. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 735-736. SIAM, Philadelphia (2003) | |||
55. Vygen, J.: Approximation algorithms for facility location problems (lecture notes). Technical report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005) http://www.or.uni-bonn.de/~vygen/fl.pdf | |||
56. Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 808-817. SIAM, Philadelphia (2004). Also, Math. Program. 108,159-176(2006) | |||
57. Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30(2), 389-403 (2005) | |||