𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling Unrelated Machines by Randomized Rounding

✍ Scribed by Schulz, Andreas S.; Skutella, Martin

Book ID
118199610
Publisher
Society for Industrial and Applied Mathematics
Year
2002
Tongue
English
Weight
240 KB
Volume
15
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An optimal rounding gives a better appro
An optimal rounding gives a better approximation for scheduling unrelated machines
✍ Evgeny V. Shchepin; Nodari Vakhania πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 218 KB

A polynomial-time algorithm is suggested for non-preemptive scheduling of n-independent jobs on m-unrelated machines to minimize the makespan. The algorithm has a worst-case performance ratio of 2 -1=m. This is better than the earlier known best performance bound 2. Our approach gives the best possi

Approximation Algorithms || Scheduling o
Approximation Algorithms || Scheduling on Unrelated Parallel Machines
✍ Vazirani, Vijay V. πŸ“‚ Article πŸ“… 2003 πŸ› Springer Berlin Heidelberg 🌐 English βš– 684 KB

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed conΒ­ jecture that P -=/= NP, their