Guochuan Zhang (Zhejiang University)
31/01/14 12:00 Talks
Lower bounds on the classical scheduling problem
Speaker:
Guochuan Zhang (College of Computer Science, Zhejiang University)
Abstract:
We consider the classical scheduling problem on parallel machines to minimize the make-span, which is one of the first problems in the area of approximation algorithms dated back to 1960s. It is known that for identical or uniform machines, there exist polynomial time approximation schemes, while for unrelated machines no polynomial time approximation algorithms have an upper bound of $3/2-\epsilon$ unless P=NP. This talk is focused on two issues:
Joint work with Lin Chen, Klaus Jansen, and Deshi Ye
Date:
Friday, January 31, 2014
Time:
12:00 pm - 1:00 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Short Bio:
Guochuan got his PhD from Academia Sinica, Beijing in 1995. After his PhD he was a research fellow at department of Computer Science and Applied Mathematics, University of Kiel, Germany, where he held a guest professor position from 2002 to 2004. He has been a professor at the Department of Mathematics, Zhejiang University of China from 2000 to 2008 and since 2009 he has been a professor at the college of Computer Science, Zhejiang University. Guochan’s research interests are on-line algorithms, approximation algorithms, scheduling, sequencing and planning, network optimization, and algorithmic game theory. He has written many high quality papers in these areas. He is an associate editor of Asia-Pacific Journal of Operational Research, and he is on editorial board of Parallel Computing Journal.
Guochuan Zhang (College of Computer Science, Zhejiang University)
Abstract:
We consider the classical scheduling problem on parallel machines to minimize the make-span, which is one of the first problems in the area of approximation algorithms dated back to 1960s. It is known that for identical or uniform machines, there exist polynomial time approximation schemes, while for unrelated machines no polynomial time approximation algorithms have an upper bound of $3/2-\epsilon$ unless P=NP. This talk is focused on two issues:
- Under the exponential time hypothesis, we provide lower bounds on the running times of exact and approximation schemes for identical machines. Most of the lower bounds show that the currently best known algorithms are almost best possible in terms of running times.
- By investigating the matrix $P=(p_{ij})_{m x n}$, where $p_{ij}$ is the processing time of job j on machine i, we show the NP-hardness to approximate within a factor of $3/2-\epsilon$ in the case that P is of rank 4.
Joint work with Lin Chen, Klaus Jansen, and Deshi Ye
Date:
Friday, January 31, 2014
Time:
12:00 pm - 1:00 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Short Bio:
Guochuan got his PhD from Academia Sinica, Beijing in 1995. After his PhD he was a research fellow at department of Computer Science and Applied Mathematics, University of Kiel, Germany, where he held a guest professor position from 2002 to 2004. He has been a professor at the Department of Mathematics, Zhejiang University of China from 2000 to 2008 and since 2009 he has been a professor at the college of Computer Science, Zhejiang University. Guochan’s research interests are on-line algorithms, approximation algorithms, scheduling, sequencing and planning, network optimization, and algorithmic game theory. He has written many high quality papers in these areas. He is an associate editor of Asia-Pacific Journal of Operational Research, and he is on editorial board of Parallel Computing Journal.