Nguyễn Đặng Ngọc Ngân * , Phan Minh Tâm Thái Đức Hưng

* Tác giả liên hệ (nganb2100137@student.ctu.edu.vn)

Abstract

This paper concerns the problem of finding a cut which partitions a connected network into two connected components so that the total weighted distance from any vertices of the network to the cut edge(s) is minimized. This problem is called the minisum cut problem. This paper shows that the problem is NP-hard on general networks by reducing the set cover problem to this problem and the problem on trees can be solved in linear time by dynamic programming. 

Keywords: Location problem, cut, median, complexity, dynamic programming

Tóm tắt

Bài báo này nghiên cứu vấn đề tìm một lát cắt phân chia một đồ thị liên thông thành hai thành phần liên thông rời nhau sao cho tổng khoảng cách có trọng số từ bất kỳ đỉnh nào của đồ thị đến lát cắt là nhỏ nhất. Bài toán này được gọi là bài toán lát cắt tổng tối tiểu. Bài báo sẽ chứng minh rằng bài toán này là NP-khó trên đồ thị tổng quát bằng cách quy giản bài toán phủ tập hợp về bài toán này và đồng thời chỉ ra rằng bài toán trên đồ thị cây có thể giải trong thời gian tuyến tính bằng quy hoạch động.

Từ khóa: Bài toán vị trí, lát cắt, trung vị, độ phức tạp, quy hoạch động

Article Details

Tài liệu tham khảo

Brimberg, J., Juel, H., & Schöbel, A. (2009). Locating a minisum circle in the plane. Discrete Applied Mathematics, 157(5), 901-912. https://doi.org/10.1016/j.dam.2008.03.017

Chen, D., Xia, B., Li, Z., & Huang, J. (2020). Application of P-median method in logistics node location. In IOP Conference Series: Earth and Environmental Science, 526(1). https://doi.org/10.1088/1755-1315/526/1/012175

Garey, M. R., & Johnson, D. S. (1990). Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman

İbrahim Miraç, E., & Eren, Ö. (2020). P-median and maximum coverage models for optimization of distribution plans: A case of United Nations Humanitarian response depots. Smart and Sustainable Supply Chain and Logistics–Trends, Challenges, Methods and Best Practices, (1), 225-246. https://doi.org/10.1007/978-3-030-61947-3_15

Kariv, O., & Hakimi, S. L. (1979a). An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics, 37(3), 513-538. https://doi.org/10.1137/0137040

Kariv, O., & Hakimi, S. L. (1979b). An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37(3), 536-560. https://doi.org/10.1137/0137040

Marianov, V., & Eiselt, H. A. (2024). Fifty Years of Location Theory - A Selective Review. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2024.01.036

Schöbel, A. (1999). Locating lines and hyperplanes: theory and algorithms (Vol. 25). Springer Science & Business Media.