List Scheduling
- PDF / 173,632 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 111 Downloads / 261 Views
List Scheduling
Cross References Decoding Reed–Solomon Codes Learning Heavy Fourier Coefficients of Boolean Functions LP Decoding Recommended Reading 1. Elias, P.: List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics MIT (1957) 2. Elias, P.: Error-correcting codes for list decoding. IEEE Trans. Inf. Theory 37, 5–12 (1991) 3. Guruswami, V., Indyk, P.: Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Inf. Theory 51(10), 3393–3400 (2005) 4. Guruswami, V., Patthak, A.: Correlated Algebraic-Geometric codes: Improved list decoding over bounded alphabets. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 227–236, Berkley, October 2006 5. Guruswami, V., Rudra, A.: Explicit capacity-achieving listdecodable codes. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 1–10. Seattle, May 2006 6. Guruswami, V., Sudan, M.: Improved decoding of Reed–Solomon and algebraic-geometric codes. IEEE Trans. Inf. Theory 45, 1757–1767 (1999) 7. Parvaresh, F., Vardy, A.: Correcting errors beyond the GuruswamiSudan radius in polynomial time. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 285–294. Pittsburgh, 2005 8. Sudan, M.: Decoding of ReedSolomon codes beyond the error-correction bound. J Complex. 13(1), 180–193 (1997) 9. Wozencraft, J.M.: List Decoding. Quarterly Progress Report, Research Laboratory of Electronics. MIT 48, 90–95 (1958) 10. Zyablov, V.V., Pinsker, M.S.: List cascade decoding. Probl. Inf. Trans. 17(4), 29–34 (1981) (in Russian); pp. 236–240 (in English) (1982)
List Scheduling 1966; Graham LEAH EPSTEIN Department of Mathematics, University of Haifa, Haifa, Israel Keywords and Synonyms Online scheduling on identical machines Problem Definition The paper of Graham [8] was published in the 1960s. Over the years it served as a common example of online algorithms (though the original algorithm was designed as a simple approximation heuristic). The following basic setting is considered.
A sequence of n jobs is to be assigned to m identical machines. Each job should be assigned to one of the machines. Each job has a size associated with it, which can be seen as its processing time or its load. The load of a machine is the sum of sizes of jobs assigned to it. The goal is to minimize the maximum load of any machine, also called the makespan. We refer to this problem as JOB SCHEDULING. If jobs are presented one by one, and each job needs to be assigned to a machine in turn, without any knowledge of future jobs, the problem is called online. Online algorithms are typically evaluated using the (absolute) competitive ratio, which is similar to the approximation ratio of approximation algorithms. For an algorithm A, we denote its cost by A as well. The cost of an optimal offline algorithm that knows the complete sequence of jobs is denoted by OPT. The competitive ratio of an algorithm A is the infimum R 1 such that for any input, A R OPT. Key Results I
Data Loading...
