Garg, Naveen ; Jain, Sachin ; Swamy, Chaitanya (1999) A randomized algorithm for flow-shop scheduling In: Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, December 13-15, 1999, Chennai, India.
Full text not available from this repository.
Official URL: https://link.springer.com/chapter/10.1007/3-540-46...
Abstract
Shop scheduling problems are known to be notoriously intractable, both in theory and practice. In this paper we give a randomized approximation algorithm for flow shop scheduling where the number of machines is part of the input problem. Our algorithm has a multiplicative factor of 2(1 + δ) and an additive term of O(mln(m+ n)pmax)/δ2).
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Springer Verlag. |
| ID Code: | 101322 |
| Deposited On: | 31 Jan 2018 09:34 |
| Last Modified: | 31 Jan 2018 09:34 |
Repository Staff Only: item control page
