Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
Tóm tắt
Từ khóa
Tài liệu tham khảo
BALINSKI , M. L. 1966 . On finding integer solutions to linear programs . In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. IBM , New York , pp. 225 - 248 .]] BALINSKI, M. L. 1966. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. IBM, New York, pp. 225-248.]]
CHARIKAR , M. , KHULLER , S. , MOUNT , D.M. , AND NARSHIMHAN , G. 2001 . Algorithms for facility location problems with outliers . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 642 - 651 .]] CHARIKAR, M., KHULLER, S., MOUNT,D.M.,AND NARSHIMHAN, G. 2001. Algorithms for facility location problems with outliers. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 642-651.]]
CHUDAK , F. 1998. Improved approximation algorithms for uncapacitated facility location . In Integer Programming and Combinatorial Optimization, R. E. Bixby, E. A. Boyd, and R. Z. Rios-Mercado, eds. Lecture Notes in Computer Science ; vol. 1412 . Springer-Verlag , New York , pp. 180 - 194 .]] CHUDAK, F. 1998. Improved approximation algorithms for uncapacitated facility location. In Integer Programming and Combinatorial Optimization, R. E. Bixby, E. A. Boyd, and R. Z. Rios-Mercado, eds. Lecture Notes in Computer Science; vol. 1412. Springer-Verlag, New York, pp. 180-194.]]
CHUDAK F. AND SHMOYS D. 1998. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript.]] CHUDAK F. AND SHMOYS D. 1998. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript.]]
CORNUEJOLS , G. , NEMHAUSER , G.L. , AND WOLSEY , L. A. 1990 . The uncapacitated facility location problem. In Discrete Location Theory. P. Mirchandani and R. Francis, eds . Wiley , New York , pp. 119 - 171 .]] CORNUEJOLS, G., NEMHAUSER,G.L.,AND WOLSEY, L. A. 1990. The uncapacitated facility location problem. In Discrete Location Theory. P. Mirchandani and R. Francis, eds. Wiley, New York, pp. 119-171.]]
DRINEAS , P. , FRIEZE , A. , KANNAN , R. , VEMPALA , S. , AND VINAY , V. 1999 . Clustering in large graphs and matrices . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms ( Baltimore, Md., Jan. 17-19). ACM, New York , pp. 291 - 299 .]] DRINEAS, P., FRIEZE, A., KANNAN, R., VEMPALA, S., AND VINAY, V. 1999. Clustering in large graphs and matrices. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 291-299.]]
GOEMANS , M.X. , GOLDBERG , A.V. , PLOTKIN , S. , SHMOYS , D. , TARDOS , E . , AND WILLIAMSON , D.P. 1994 . Improved approximation algorithms for network design problems . In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, Va., Jan. 23-25) . ACM, New York , pp. 223 - 232 .]] GOEMANS,M.X.,GOLDBERG,A.V.,PLOTKIN, S., SHMOYS, D., TARDOS,E ., AND WILLIAMSON,D.P. 1994. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, Va., Jan. 23-25). ACM, New York, pp. 223-232.]]
GOEMANS , M.X. , AND WILLIAMSON , D. P. 1997 . The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed . PWS , pp. 144 - 191 .]] GOEMANS,M.X.,AND WILLIAMSON, D. P. 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed. PWS, pp. 144-191.]]
GUHA , S. , AND KHULLER , S. 1998 . Greedy strikes back: Improved facility location algorithms . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms ( San Francisco, Calif., Jan.). ACM, New York , pp. 649 - 657 .]] GUHA, S., AND KHULLER, S. 1998. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan.). ACM, New York, pp. 649-657.]]
JAIN , K. , MA cN DOIU , I., VAZIRANI , V.V. , AND WILLIAMSON , D. P. 1999 . A primal-dual schema based approximation algorithm for the element connectivity problem . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms ( Baltimore, Md., Jan. 17-19). ACM, New York , pp. 484 - 489 .]] JAIN, K., MA cNDOIU, I., VAZIRANI,V.V.,AND WILLIAMSON, D. P. 1999. A primal-dual schema based approximation algorithm for the element connectivity problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 484-489.]]
JAIN , K. , AND VAZIRANI , V. V. 2000. An approximation algorithm for the fault tolerant metric facility location problem . In Proceedings of the 3rd Annual APPROX Conference . Lecture Notes in Computer Science , vol. 1671 . Springer-Verlag , New York .]] JAIN, K., AND VAZIRANI, V. V. 2000. An approximation algorithm for the fault tolerant metric facility location problem. In Proceedings of the 3rd Annual APPROX Conference. Lecture Notes in Computer Science, vol. 1671. Springer-Verlag, New York.]]
KORUPOLU , M.R. , PLAXTON , C.G. , AND RAJARAMAN , R. 1998 . Analysis of a local search heuristic for facility location problems . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms ( San Francisco, Calif., Jan.) ACM, New York , pp. 1 - 10 .]] KORUPOLU,M.R.,PLAXTON,C.G.,AND RAJARAMAN, R. 1998. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan.) ACM, New York, pp. 1-10.]]
KUEHN , A.A. , AND HAMBURGER , M. J. 1963 . A heuristic program for locating warehouses. Manage . Sci. 9 , 643 - 666 .]] KUEHN,A.A.,AND HAMBURGER, M. J. 1963. A heuristic program for locating warehouses. Manage. Sci. 9, 643-666.]]
NEMHAUSER , G.L. , AND WOLSEY , L. A. 1990. Integer and Combinatorial Optimization . Wiley , New York .]] NEMHAUSER,G.L.,AND WOLSEY, L. A. 1990. Integer and Combinatorial Optimization. Wiley, New York.]]
RAJAGOPALAN , S. , AND VAZIRANI , V. V. 1999 . On the bidirected cut relaxation for the metric Steiner tree problem . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms ( Baltimore, Md., Jan. 17-19). ACM, New York , pp. 742 - 751 .]] RAJAGOPALAN, S., AND VAZIRANI, V. V. 1999. On the bidirected cut relaxation for the metric Steiner tree problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 742-751.]]