Đă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í
245010 (2024) Trang: 1-16
Tạp chí: Asian-European Journal of Mathematics

The typical median subtree problem on trees is to locate a (continuous) tree-shaped facility (the leaves of this facility are not necessary vertices) with a specified length to minimize the total weighted distance of all vertices to the new facility. In this paper, each vertex weight can be any value within an interval and the total deviation of weights is limited within a threshold. We want to find a subtree that minimizes the median function in the worst-case scenario. This is the so-called minmax robust median subtree problem on trees. In order to solve the problem, we first consider the minmax robust 1-median problem on trees and solve the problem in O(n log n) time. Then, the nestedness property is coined, i.e., any optimal subtree must contain a robust 1-median in the tree. Based on this property, we develop a greedy algorithm that solves the corresponding problem in O(n^4) time.



Các bài báo khác
07 November (2024) Trang: 1-19
Tạp chí: Annals of Operations Research
43 (2024) Trang: 147
Tạp chí: omputational and Applied Mathematics
1 (2021) Trang: 1-13
Tạp chí: Discrete Mathematics, Algorithms and Applications
407 (2021) Trang: 126328
Tạp chí: Applied Mathematics and Computation
1 (2020) Trang: 1-12
Tạp chí: Journal of Industrial and Management Optimization
1 (2017) Trang: 1-12
Tạp chí: Central European Journal of Operations Research
1 (2016) Trang:
Tạp chí: Taiwanese Journal of Mathematics
1 (2016) Trang: 9-13
Tạp chí: IJCDM
13 (2014) Trang: 16-22
Tạp chí: Discrete Optimization
2 (2015) Trang:
Tạp chí: Journal of Optimization Theory and Applications
247 (2015) Trang: 774-781
Tạp chí: European Journal of Operational Research
4 (2015) Trang:
Tạp chí: Mathematical Methods of Operations Research
3 (2015) Trang:
Tạp chí: Central European Journal of Operations Research
10 (2015) Trang:
Tạp chí: Optimization: A Journal of Mathematical Programming and Operations Research
 


Vietnamese | English






 
 
Vui lòng chờ...