On speed scaling via integer programming

DOI10.1016/J.ORL.2015.08.002MaRDI QIDQ1785426zbMATH OpenOpenAlexFDO

Authors Serdar Karademir, Oleg A. Prokopyev

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2015.08.002

zbMATH Keywords

FPTASouter approximationspeed scalingenergy minimizationconvex MINLP

Mathematics Subject Classification ID

Convex programming (90C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Mixed integer programming (90C11)

Recommendations

• Speed scaling on parallel processors
• Speed-scaling with no preemptions
• On the complexity of speed scaling
• Speed scaling on parallel processors with migration
• Race to idle: new algorithms for speed scaling with a sleep state

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• scientific article; zbMATH DE number 544186 (Why is no real title available?)
• scientific article; zbMATH DE number 2079319 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A nonlinear knapsack problem
• Algorithms and Software for Convex Mixed Integer Nonlinear Programs
• Algorithms for dynamic speed scaling
• An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs
• An algorithmic framework for convex mixed integer nonlinear programs
• An outer-approximation algorithm for a class of mixed-integer nonlinear programs
• Deadline scheduling and power management for speed bounded processors
• Energy-efficient algorithms for flow time minimization
• Heuristic algorithms for the general nonlinear separable knapsack problem
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• Mixed-integer nonlinear programs featuring ``on/off constraints
• Perspective reformulation and applications
• Perspective reformulations of mixed integer nonlinear programs with indicator variables
• Scheduling heterogeneous processors isn't as easy as you think
• Solving mixed integer nonlinear programs by outer approximation
• Speed scaling for stretch plus energy
• Speed scaling with an arbitrary power function
• The Nonlinear Resource Allocation Problem
• The nonlinear knapsack problem - algorithms and applications

Cited in

(2)

• The Effect of Time Constraints on Scaled Speedup
• Machine speed scaling by adapting methods for convex optimization with submodular constraints

Describes a project that uses

Uses Software

• Bonmin
• CPLEX

This page was built for publication: On speed scaling via integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785426)