Low-Resource Speech Recognition of 500-Word Vocabularies
Sabine Deligne, Ellen Eide, et al.
INTERSPEECH - Eurospeech 2001
We consider the open shop, job shop, and flow shop scheduling problems with integral processing times. We give polynomial-time algorithms to determine if an instance has a schedule of length at most 3, and show that deciding if there is a schedule of length at most 4 is NP-complete. The latter result implies that, unless P = NP, there does not exist a polynomial-time approximation algorithm for any of these problems that constructs a schedule with length guaranteed to be strictly less than 5/4 times the optimal length. This work constitutes the first nontrivial theoretical evidence that shop scheduling problems are hard to solve even approximately.
Sabine Deligne, Ellen Eide, et al.
INTERSPEECH - Eurospeech 2001
Indranil R. Bardhan, Sugato Bagchi, et al.
JMIS
David S. Kung
DAC 1998
John M. Boyer, Charles F. Wiecha
DocEng 2009