TY - JOUR
T1 - Semi-definite relaxation algorithm for single machine scheduling with controllable processing times
AU - Chen, Feng
AU - Zhang, Liansheng
PY - 2005
Y1 - 2005
N2 - The authors present a semi-definite relaxation algorithm for the scheduling problem with controllable times on a single machine. Their approach shows how to relate this problem with the maximum vertex-cover problem with kernel constraints (MKVC). The established relationship enables to transfer the approximate solutions of MKVC into the approximate solutions for the scheduling problem. Then, they show how to obtain an integer approximate solution for MKVC based on the semi-definite relaxation and randomized rounding technique.
AB - The authors present a semi-definite relaxation algorithm for the scheduling problem with controllable times on a single machine. Their approach shows how to relate this problem with the maximum vertex-cover problem with kernel constraints (MKVC). The established relationship enables to transfer the approximate solutions of MKVC into the approximate solutions for the scheduling problem. Then, they show how to obtain an integer approximate solution for MKVC based on the semi-definite relaxation and randomized rounding technique.
KW - Approximation algorithm
KW - Scheduling with controllable times
KW - Semi-definite programming
UR - http://www.scopus.com/inward/record.url?scp=15544364043&partnerID=8YFLogxK
U2 - 10.1142/S0252959905000142
DO - 10.1142/S0252959905000142
M3 - Article
AN - SCOPUS:15544364043
SN - 0252-9599
VL - 26
SP - 153
EP - 158
JO - Chinese Annals of Mathematics. Series B
JF - Chinese Annals of Mathematics. Series B
IS - 1
ER -