Đăng nhập
 
Tìm kiếm nâng cao
 
Tên bài báo
Tác giả
Năm xuất bản
Tóm tắt
Lĩnh vực
Phân loại
Số tạp chí
 

Bản tin định kỳ
Báo cáo thường niên
Tạp chí khoa học ĐHCT
Tạp chí tiếng anh ĐHCT
Tạp chí trong nước
Tạp chí quốc tế
Kỷ yếu HN trong nước
Kỷ yếu HN quốc tế
Book chapter
Bài báo - Tạp chí
24 (2020) Trang: 501-522
Tạp chí: Taiwanese Journal of Mathematics

This paper concerns the problem of modifying edge lengths of a network at minimum total costs so as to make a prespecified vertex become an optimal location in the modified environment. Here, we focus on the ordered median objective function with respect to the vector of multipliers \lambda = (1,...,1,0,...,0) with k 1's. This problem is called the inverse anti-k-centrum problem. We first show that the inverse anti-kk-centrum problem is NP-hard even on tree networks. However, for the inverse anti-k-centrum problem on cycles, we formulate it as one or two linear programs, depending on odd or even integer k. Concerning the special cases with k=2,3, M, we develop combinatorial algorithms that efficiently solve the problem, where M is the number of vertices of the cycle.

Các bài báo khác
795 (2019) Trang: 119-127
Tạp chí: Theoretical Computer Science
 


Vietnamese | English






 
 
Vui lòng chờ...