Semi-definite relaxation algorithm for single machine scheduling with controllable processing times

Feng Chen; Liansheng Zhang

doi:10.1142/S0252959905000142

Semi-definite relaxation algorithm for single machine scheduling with controllable processing times

Feng Chen^*, Liansheng Zhang

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	153-158
Number of pages	6
Journal	Chinese Annals of Mathematics. Series B
Volume	26
Issue number	1
DOIs	https://doi.org/10.1142/S0252959905000142
Publication status	Published - 2005
Externally published	Yes

Keywords

Approximation algorithm
Scheduling with controllable times
Semi-definite programming

Access to Document

10.1142/S0252959905000142

Cite this

@article{4e1f65df597d4d528d2cb668876a9575,

title = "Semi-definite relaxation algorithm for single machine scheduling with controllable processing times",

abstract = "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.",

keywords = "Approximation algorithm, Scheduling with controllable times, Semi-definite programming",

author = "Feng Chen and Liansheng Zhang",

year = "2005",

doi = "10.1142/S0252959905000142",

language = "English",

volume = "26",

pages = "153--158",

journal = "Chinese Annals of Mathematics. Series B",

issn = "0252-9599",

publisher = "Springer Verlag",

number = "1",

}

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 -

Semi-definite relaxation algorithm for single machine scheduling with controllable processing times

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this