Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Xấp xỉ thời gian hoàn thành có trọng số thông qua tương quan âm mạnh mẽ hơn
Journal of Scheduling - Trang 1-10 - 2023
Tóm tắt
Việc tối thiểu hóa thời gian hoàn thành có trọng số của các công việc trong mô hình máy song song không liên quan là một bài toán lập lịch cơ bản. Thuật toán xấp xỉ đầu tiên $$(3/2 - c)$$ cho bài toán này, với một hằng số $$c > 0$$, đã được đề xuất trong công trình của Bansal và cộng sự (SIAM J Comput, 2021). Một thành phần chính trong công trình này là thuật toán làm tròn phụ thuộc đầu tiên với một lượng tương quan âm nhất định được đảm bảo. Chúng tôi đã cải thiện lượng đảm bảo này từ 1/108 lên 1/27, từ đó cũng cải thiện hằng số c trong các thuật toán của Bansal và cộng sự, cũng như Li (SIAM J Comput, 2020) cho thời gian hoàn thành có trọng số. Do vai trò hiện tại phổ biến của làm tròn phụ thuộc trong lập lịch và tối ưu hóa tổ hợp, việc cải thiện làm tròn phụ thuộc của chúng tôi cũng gây được sự quan tâm độc lập.
Từ khóa
#lập lịch #tối ưu hóa tổ hợp #thời gian hoàn thành có trọng số #tương quan âm #thuật toán làm tròn phụ thuộcTài liệu tham khảo
Afrati, F.N., Bampis, E., Chekuri, C., Karger, D.R., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., & Sviridenko, M. (1999). Approximation schemes for minimizing average weighted completion time with release dates (pp. 32–44). FOCS: In Foundations of Computer Science.
Ageev, A. A., & Sviridenko, M. (2004). Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8(3), 307–328.
Anil Kumar, V. S., Marathe, M. V., Parthasarathy, S., & Srinivasan, A. (2009). A unified approach to scheduling on unrelated parallel machines. Journal of the ACM (JACM), 56(5), 28:1-28:31.
Bansal, N. (2019). On a generalization of iterated and randomized rounding. In M. Charikar and E. Cohen (Eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23–26, 2019, (pp. 1125–1135). ACM.
Bansal, N., Aravind, S., & Ola, S. (2021). Lift-and-round to improve weighted completion time on unrelated machines. In SIAM Journal on Computing, 50(3):STOC16–138–STOC16–159, 2021. https://doi.org/10.1137/16M1099583. Conference version: Proc. ACM Symposium on Theory of Computing, (pp. 156–167). 2016
Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., & Pruhs, K. (2016). Flow time minimization. In Encyclopedia of Algorithms, (pp. 766–768).
Chekuri, C., & Khanna, S. (2001). A PTAS for minimizing weighted completion time on uniformly related machines. In F. Orejas, P. G. Spirakis, & J. van Leeuwen (Eds.), Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8–12, 2001, Proceedings, volume 2076 of Lecture Notes in Computer Science, (pp. 848–861). Springer.
Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23, 493–509.
Hoogeveen, H., Schuurman, P., & Woeginger, G. J. (2001). Non-approximability results for scheduling problems with minsum criteria. INFORMS Journal on Computing, 13(2), 157–168.
Im, S., & Shadloo, M. (2020). Weighted completion time minimization for unrelated machines via iterative fair contention resolution. In S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, Jan 5–8, 2020, (pp. 2790–2809). SIAM.
Li, S. (2020). Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. SIAM Journal on Computing, 49(4). Published online April 2020.
Li, Y., Jin, D., Hui, P., & Han, Z. (2016). Optimal base station scheduling for device-to-device communication underlaying cellular networks. IEEE Journal on Selected Areas in Communications, 34(1), 27–40.
Phillips, C. A., Stein, C., & Wein, J. (1998). Minimizing average completion time in the presence of release dates. Mathematical Programming, 82, 199–223.
Pruhs, K. (2019). Green computing algorithmics. In B. Steffen & G. J. Woeginger (Eds.), Computing and Software Science-State of the Art and Perspectives, volume 10000 of Lecture Notes in Computer Science, (pp. 161–183). Springer.
Saha, B., & Srinivasan, A. (2018). A new approximation technique for resource-allocation problems. Random Structures & Algorithms, 52(4), 680–715.
Sethuraman, J., & Squillante, M. S. (1999). Optimal scheduling of multiclass parallel machines (pp. 963–964). SODA: In ACM-SIAM Symposium on Discrete Algorithms.
Shmoys, D. B., & Tardos, É. (1993). An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62, 461–474.
Singh, M. (2016). Personal communication through Nikhil Bansal.
Skutella, M. (2001). Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the ACM, 48(2), 206–242.
Skutella, M., & Woeginger, G. J. (1999). A PTAS for minimizing the weighted sum of job completion times on parallel machines (pp. 400–407). STOC: In Symposium on Theory of Computing.
Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics, 3, 59–66.