Computer Science ›› 2021, Vol. 48 ›› Issue (4): 37-42.doi: 10.11896/jsjkx.200600064
• Computer Science Theory • Previous Articles Next Articles
GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin
CLC Number:
[1]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and Approximation in Determini-stic Sequencing and Sche-duling:A Survey[J].Annals of Discrete Mathematics,1979,5(1):287-326. [2]GRAHAM R L.Bounds for Certain Multiprocessing Anomalies[J].Bell System Technical Journal,1966,45(9):1563-1581. [3]GRAHAM R.L.Bounds on multiprocessing time anomalies[J].SIAM Journal on Applied Mathematics,1969,17(2):416-429. [4]DEUERMEYER B L,FRIESEN D K,LANGSTON M A.Scheduling to Maximize the Minimum Processor Finish Time in a Multi-processor System[J].Siam Journal on Algebraic Discrete Methods,1982,3(2):190-196. [5]KAO T Y,ELSAYED E A.Performance of the LPT algorithm in multiprocessor scheduleing[J].Computers & Operations Research,1990,17(4):365-373. [6]CSIRIK J,KELLERER H,WOEGINGER G.The exact LPT-bound for maximizing the minimum completion time[J].Operations Research Letters,1992,11(5):281-287. [7]WOEGINGER G J.A polynomial-time approximation schemefor maximizing the minimum machine completion time[J].Operations Research Letters,1997,20(4):149-154. [8]COFFMAN E G,GAREY M R,JOHNSON D S.An Application of Bin-Packing to Multiprocessor Scheduling[J].Siam Journal on Computing,19787(1):1-17. [9]LANGSTON M A.Processor scheduling with improved heuristic algorithms[M].Texas A&M University,1981. [10]FRIESEN D K.Tighter Bounds for the Multifit ProcessorScheduling Algorithm[J].Siam Journal on Computing,1984,13(1):170-181. [11]YUE M.On the exact upper bound for the multifit processor scheduling algorithm[J].Annals of Operations Research,1990,24(1):233-259. [12]SAHN I,SARTAJ K.Algorithms for Scheduling Independent Tasks[J].Journal of the ACM,1976,23(1):116-127. [13] HOCHBAUM D S,SHMOYS D B.Using dual approximation algorithms for scheduling problems theoretical and practical results[J].Journal of the ACM(JACM),1987,34(1):144-162. [14]VEL H V D,SHIJIE S.A modification of Hochbaum andShmoys’ algorithm for scheduling problems[J].BIT Numerical Mathematics,1991,31(1):50-52. [15]JANSEN K.An EPTAS for scheduling jobs on uniform processors:using an MILP relaxation with a constant number of integral variables[J].SIAM Journal on Discrete Mathematics,2010,24:457-485. [16]KLEIN K M,JANSEN K,VERSCHAE J.Closing the gap for makespan scheduling via sparsification techniques[C]//Procee-dings of the 43rd International Colloquium on Automata,Languages,and Programming.2016,55(72):1-13. [17]CHEN L,JANSEN K,ZHANG G.On the optimality of exact and approximation algorithms for scheduling problems[J].Journal of Computer and System Sciences,2018,96(2):89-99. [18]IMPAGLIAZZO R,PATURI R,ZANE F.Which problems have strongly exponential complexity?[J].Journal of Computer and System Science,2001,63:512-530. [19]YUE X R,GAO J J,CHEN Z B.A polynomial time algorithm for scheduling on processing time constraints[C]//ACM International Conference Proceeding Series,2019 the 9th Internatio-nal Conference on Communication and Network Security.2019:109-113. [20]近似算法[M].郭效江,方志奇,农庆琴,译.北京:北京高等教育出版社,2010:74-75. |
[1] | JIANG Xin-wen. Polynomial Time Algorithm for Hamilton Circuit Problem [J]. Computer Science, 2020, 47(7): 8-20. |
[2] | ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem [J]. Computer Science, 2018, 45(4): 83-88. |
[3] | LUO Wei-dong, WANG Jian-xin and FENG Qi-long. Survey of Cycle Packing Problem [J]. Computer Science, 2017, 44(1): 1-6. |
[4] | LIU Yun-long. Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k [J]. Computer Science, 2016, 43(9): 23-26. |
[5] | LIU Yun-long and CUI Meng-tian. Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems [J]. Computer Science, 2016, 43(8): 7-12. |
[6] | JIA Jian-wei and CHEN Ling. Set Similarity Approximation Algorithm Based on Parity of Data Sketch [J]. Computer Science, 2016, 43(6): 254-256. |
[7] | LI Wei-dong LI Jian-ping. Cardinality-constrained Load Balancing Problem [J]. Computer Science, 2015, 42(7): 74-77. |
[8] | JIANG Shun-liang, XU Qing-yong, HUANG Wei, YE Fa-mao and XU Shao-ping. Randomized Power Tree Method for Shortest Addition Chains [J]. Computer Science, 2015, 42(3): 228-232. |
[9] | HUANG Qu-zhi and ZHANG Jun-chao. Approximating Triangle Counting Based on Sampling in Complex Networks [J]. Computer Science, 2015, 42(11): 188-190. |
[10] | . Tree Decomposition and its Applications in Algorithms:Survey [J]. Computer Science, 2012, 39(3): 14-18. |
[11] | . Bounded Clustering on Bounded Tree-width Graphs [J]. Computer Science, 2011, 38(11): 241-244. |
[12] | ZHENG Ying,WANG Jian-xin,CHEN Jian-er. Survey of Steiner Tree Problem [J]. Computer Science, 2011, 38(10): 16-22. |
[13] | WANG Jian-xin,Jiang Guo-hong,LI Wen-jun,CHEN Jian-er. Algorithms for Feedback Set Problems:A Survey [J]. Computer Science, 2011, 38(1): 40-47. |
[14] | FENG Wang-sen,ZHANG Bei,CHEN Ping,CUI Jian. Transport Sub-network Selection:Approaching with Bounded Maximum Spanning Sub-graphs [J]. Computer Science, 2010, 37(3): 42-45. |
[15] | WANG Jian-xin,CHEN Bei-wei,CHEN Jian-er. Algorithms for Dominating Problems:A Survey [J]. Computer Science, 2010, 37(2): 7-11. |
|