Non-approximability of the Bulk Synchronous Task Scheduling Problem
説明
The mainstream architecture of a parallel machine with more than tens of processors is a distributed-memory machine. The bulk synchronous task scheduling problem (BSSP, for short) is an task scheduling problem for distributed-memory machines. This paper shows that there does not exist a ?-approximation algorithm to solve the optimization counterpart of BSSP for any ? < 6/5 unless P = NP.