Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Vấn đề lập lịch trong mạng lưới vận tải có dạng tuyến tính
Tóm tắt
Trong bài báo này, chúng tôi xem xét các vấn đề lập lịch trực tuyến cho hình thức tuyến tính dưới nhiều hàm mục tiêu khác nhau: tối thiểu hóa thời gian hoàn thành tối đa, tối thiểu hóa độ trễ lớn nhất và tối thiểu hóa tổng thời gian hoàn thành. Chúng tôi đưa ra các giải pháp tối ưu cho phiên bản đơn hướng của vấn đề đối với từng mục tiêu và chỉ ra rằng đối với các phiên bản hai chiều của mỗi vấn đề, không có thuật toán trực tuyến nào có thể đạt được giải pháp tối ưu một cách xác định cho bất kỳ hàm mục tiêu đã xem xét nào. Chúng tôi cũng đề xuất các thuật toán trực tuyến xấp xỉ 2 cho các mục tiêu tối thiểu hóa MinMakespan và MinSum. Chúng tôi cũng chứng minh rằng không có thuật toán trực tuyến nào có thể đạt được giải pháp tối ưu một cách xác định cho bất kỳ hàm mục tiêu nào đã xem xét cho trường hợp có trọng số trong các kịch bản đơn hướng.
Từ khóa
#lập lịch trực tuyến #mạng lưới vận tải #hàm mục tiêu #tối thiểu hóa #thuật toán xấp xỉTài liệu tham khảo
Adler, M., Khanna, S., Rajaraman, R., Rosen, A.: Time-constrained scheduling of weighted packets on trees and meshes. Algorithmica 36, 123–152 (2003)
Adler, M., Rosenberg, A.L., Sitaraman, R.K., Unger, W.: Scheduling time-constrained communication in linear networks. In: Proceedings of 10th ACM Symposium on Parallel Algorithms and Architectures, pp. 269–278 (1998)
Bermond, J.-C., Nisse, N., Reyes, P., Rivano, H.: Minimum delay data gathering in radio networks. Ad-Hoc, Mobile and Wireless Networks, Lecture Notes in Computer Science, vol. 5793, pp. 69–82 (2009)
Klasing, R., Korteweg, P., Stougie, L., Marchetti-Spaccamela, A.: Data gathering in wireless networks. In: Graphs and Algorithms in Communication Networks, Springer Monograph, Springer, Berlin (2009)
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: An approximation algorithm for the wireless gathering problem. Oper. Res. Lett. 36(5), 605–608 (2008)
Busch, C., Magdon-Ismail, M., Mavronicolas, M., Wattenhofer, R.: Near-Optimal Hot-Potato Routing on Trees. Euro-Par, pp. 820–827 (2004)
Cidon, I., Kutten, S., Mansour, Y., Peleg, D.: Greedy Packet Scheduling. SIAM J. Comput. 24(1), 148–157 (1995)
Gargano, L.: Time optimal gathering in sensor networks. Proc. Struct. Inform. Commun. Complexity 4474, 7–10 (2007)
Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica 14(2), 167–180 (1994)
Li, C.-L., McCormick, S.T., Simchi-Levi, D.: The complexity of finding two disjoint paths with min-max objective function. Discrete Appl. Math. 26(1), 105–115 (1990)
Leighton, F.T., Maggs, B.M., Richa, A.: Fast algorithms for finding O(Congestion + Dilation) packet routing schedules. Combinatorica 19(3), 375–401 (1999)
Leung, Y-T, J., Tam, T., Young, G.: On-line routing of real-time messages. J. Parallel Distrib. Comput. 34, 211–217 (1996)
Liu, K.-S., Zaks, S.: Scheduling in synchronous networks and the greedy algorithm. Theor. Comput. Sci. 220(1), 157–183 (1999)
Mansour, Y., Patt-Shamir, B.: Greedy packet scheduling on shortest paths. J. Algorithms 14, 449–465 (1993)
Ostrovsky, R., Rabani, Y.: Universal \(O\)(congestion + dilation + \(\log ^{1+\varepsilon }N\)) local control packet switching algorithms. In: Proceedings of ACM Symposium on Theory of Computing, pp. 644–653 (1997)
Peis, B., Skutella, M., Wiese, A.: “Packet routing on the grid”, in LATIN 2010. LNCS 6034, 120–130 (2010)
Rabani, Y., Tardos, E.: Distributed packet switching in arbitrary networks. In: Proceedings of ACM Symposium on the Theory of Computing, pp. 366–375 (1996)
Revah, Y., Segal, M.: Improved algorithms for data-gathering time in sensor networks II: ring, tree, and grid Topologies. Int. J. Distri. Sens. Netw. 5, 463–479 (2009)