Energy-efficient scheduling and routing via randomized rounding
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 127985974
- Type
- D - Journal article
- DOI
-
10.1007/s10951-016-0500-2
- Title of journal
- JOURNAL OF SCHEDULING
- Article number
- -
- First page
- 35
- Volume
- 21
- Issue
- 1
- ISSN
- 1094-6136
- Open access status
- Deposit exception
- Month of publication
- October
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
-
- Citation count
- 5
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Using novel configuration linear programs and randomized rounding, the paper designs and analyses approximation algorithms for energy optimization problems, significantly improving the previous state-of-the-art approaches. The paper provides a general framework for designing algorithms with provable performance guarantees and efficient running times, for reducing the power of heterogeneous computer systems by exploiting the nonlinear nature of energy as a computational resource. Subsequent work extended these ideas to more general, non-uniform demand resource allocation problems and reduced running times (e.g., Makarychev et al. Journal of ACM 2018).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -