Title
Moderately exponential approximation for makespan minimization on related machines
Abstract
We consider in this paper the classical Q||C"m"a"x scheduling problem. The objective is to minimize the maximum completion time (called makespan) while scheduling independent jobs in parallel on machines that have different speeds. While several approximation schemes has been proposed (and in particular a recent EPTAS, Jansen, 2010 [12]), the current best ''direct'' algorithm (i.e. an algorithm specifically designed for reaching a given approximation ratio) is still due to Chen (1991) [4] with a 1.382 ratio. Our objective in this work is not to provide yet another improvement of the asymptotic dependencies in 1@e (ensuring a (1+@e) ratio), but to design faster direct algorithms by targeting respectively 43 and 54 ratios. Indeed, instantiating any of the existing approximation scheme for @e=13 (respectively 14) leads to polynomial complexities, but not to practical algorithms because of the hidden large constants in the computational complexity. Thus, our approach focuses on a moderately exponential algorithm and provides a (43+@e) dual approximation algorithm running in O(m^(^1^+^1^3^@e^)^l^o^g^(^3^(^@b^+^1^)^)(m+n)), where m is the number of machines, n the number of jobs, @b an integer lower than m depending on the instance. This result is obtained through an oracle framework, where the algorithm guesses possible answers from an oracle. The terseness of the answers points out the critical information needed while solving any instance. Such an approach leads to a better comprehension of the problem. Similarly, we obtain the same kind of results for a 54+@e ratio. Moreover, the proposed techniques seem promising for tackling classical specific cases (like scheduling on identical machines), as the complexity becomes a low degree polynomial when the speeds are non arbitrary.
Year
DOI
Venue
2013
10.1016/j.tcs.2013.03.020
Theor. Comput. Sci.
Keywords
DocType
Volume
makespan minimization,existing approximation scheme,algorithm guess,classical Q,approximation ratio,approximation scheme,practical algorithm,exponential algorithm,direct algorithm,dual approximation algorithm,answers point,exponential approximation,related machine
Journal
511,
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
8
3
Name
Order
Citations
PageRank
Marin Bougeret111313.35
Pierre-françois Dutot216613.95
Denis Trystram31120160.57