计算机科学 ›› 2015, Vol. 42 ›› Issue (7): 74-77.doi: 10.11896/j.issn.1002-137X.2015.07.016
李伟东 李建平
LI Wei-dong LI Jian-ping
摘要： 考虑了具有数目约束的负载平衡问题的一种特殊情形,称之为2-半匹配问题。分析了此问题在3种目标函数下的计算复杂性,并设计了相应的近似算法。
| [1] Graham R L.Bounds for certain multiprocessing anomalies [J].Bell System Technical Journal,1966,45(9),1563-1581 [2] Lenstra J K,Shmoys D B,Tardos E.Approximation algorithms for scheduling unrelated parallel machines [J].Mathematical Programming,1990,46(3):259-271 [3] Chakrabarty D,Chuzhoy J,Khanna S.On allocating goods tomaximize fairness [C]∥Proceedings of 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS).2009:107-116 [4] Asadpour A,Saberi A.An approximation algorithm for max-min fair allocation of indivisible goods [J].SIAM Journal on Computing,2010,39(7):2970-2989 [5] Azar Y,Epstein A.Convex programming for scheduling unrelatedparallel machines [C]∥Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC).2005:331-337 [6] Kumar V S A,Marathe M V,Parthasarathy S,et al.A unified approach to scheduling on unrelated parallel machines [J].Journal of the ACM,2009,56(5):28 [7] Bansal N,Vredeveld T,Zwaan R.Approximating vector scheduling:Almost matching upper and lower bounds [C]∥Lecture Notes in Computer Science 8392.2014:47-59 [8] Papadimitriou C,Yannakakis M.Optimization,approximation,and complexity classes [J].Journal of Computer and System Sciences,1991,43(3):425-440 [9] Babel L,Kellerer H,Kotov V.The k-partitioning problem [J].Mathematical Methods of Operations Research,1998,47(1):59-82(下转第90页)(上接第77页) [10] Dell’Amico M,Martello S.Bounds for the cardinality constrai-ned P｜Cmax problem [J].Journal of Scheduling,2001,4(3):123-138 [11] Dell’Amico M,Iori M,Martello S.Heuristic algorithms andscatter search for the cardinality constrained P｜Cmax problem [J].Journal of Heuristics,2004,10(2):169-204 [12] Dell’Amico M,Iori M,Martello S,et al.Lower bound and heuristic algorithms for the ki partitioning problem [J].European Journal of Operational Research,2006,171(3):725-742 [13] He Y,Tan Z,Zhu J,et al.k-Partitioning problems for maximizing the minimum load [J].Computers and Mathematics with Applications,2003,46(10/11):1671-1681 [14] Bruglieri M,Ehrgott M,Hamacher H W,et al.An annotatedbibliography of combinatorial optimization problems with fixed cardinality constraints [J].Discrete Applied Mathematics,2006,154(9):1344-1357 [15] Kellerer H,Woeginger G.A tight bound for 3-partitioning [J].Discrete Applied Mathematics,1993,45(3):249-259 [16] Kellerer H,Kotov V A.7/6-approximation algorithm for 3-partitioning and its application to multiprocessor scheduling [J].INFOR:Information Systems and Operational Research,1999,37(1):48-56 [17] Chen S P,He Y,Lin G H.3-partitioning for maximizing the minimum load [J].Journal of Combinatorial Optimization,2002,6(1):67-80 [18] Garey M R,Johnson D S.Computer and Intractability:A Guide to The Theory of NP-Completeness [D].San Francisco:W.H.Freeman and Company,1979 [19] Ahuja R K,Magnanti T L,Orlin J B.Network Flows:Theory,Algorithms,and Applications [M].Prentice Hall,NJ,1993 [20] Petrank E.The hardness of approximation:gap location[J].Computational Complexity,1994,4(2):133-157 |
| No related articles found! |
|
||
首页