Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142122 | Operations Research Letters | 2015 | 8 Pages |
Abstract
We consider a class of convex mixed-integer nonlinear programs motivated by speed scaling of heterogeneous parallel processors with sleep states and convex power consumption curves. We show that the problem is NPNP-hard and identify some polynomially solvable classes. Furthermore, a dynamic programming and a greedy approximation algorithms are proposed to obtain a fully polynomial-time approximation scheme for a special case. For the general case, we implement an outer approximation algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Serdar Karademir, Oleg A. Prokopyev,