October 19, 2016
2:00 pm - 5:30 pm
Hall C

Track: ACM SRC
Type: Posters
Level: All

We propose a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan, based on the best existing PTAS. This is the first practical parallel approximation algorithm for the problem that maintains the approximation guarantees of the sequential PTAS and it is designed for execution on shared-memory parallel machines.

Speaker(s)