Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006
We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an α-approximation for the case of two machines where α < 1.45, an improved approximation ratio of O(log m/ log log m) for an arbitrary number m of machines, and the first (2 + ε)-approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem that is of independent interest. © 2006 INFORMS.
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006
S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007