# Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

Shakhlevich, Natalia V., Shioura, Akiyoshi and Strusevich, Vitaly A. (2008) Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach. In: Algorithms – ESA 2008 : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings. Lecture Notes in Computer Science (5193). Springer Verlag, Berlin/Heidelberg, Germany, pp. 756-767. ISBN 978-3-540-87743-1 (doi:10.1007/978-3-540-87744-8_63)

Full text not available from this repository.

## Abstract

We consider a variety of preemptive scheduling problems with controllable processing times on a single machine and on identical/uniform parallel machines, where the objective is to minimize the total compression cost. In this paper, we propose fast divide-and-conquer algorithms for these scheduling problems. Our approach is based on the observation that each scheduling problem we discuss can be formulated as a polymatroid optimization problem. We develop a novel divide-and-conquer technique for the polymatroid optimization problem and then apply it to each scheduling problem. We show that each scheduling problem can be solved in $\O({\rm T}_{\rm feas}(n) \times\log n)$ time by using our divide-and-conquer technique, where n is the number of jobs and Tfeas(n) denotes the time complexity of the corresponding feasible scheduling problem with n jobs. This approach yields faster algorithms for most of the scheduling problems discussed in this paper.

Item Type: Conference Proceedings Algorithms – ESA 2008 : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings [1] This paper was first presented at the 16th Annual European Symposium on Algorithms (ESA 2008), held from 15-17 September 2008 in Karlsruhe, Germany. polymatroid optimization, divide-and-conquer algorithm, scheduling Q Science > QA Mathematics > QA75 Electronic computers. Computer science School of Computing & Mathematical SciencesSchool of Computing & Mathematical Sciences > Department of Mathematical SciencesSchool of Computing & Mathematical Sciences > Statistics & Operational Research Group 14 Oct 2016 09:03 None None None http://gala.gre.ac.uk/id/eprint/1214