Generalized machine activation problems

Jian Li*, Samir Khuller

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

In this paper we consider a generalization of the machine activation problem introduced recently ["Energy efficient scheduling via partial shutdown" by Khuller, Li and Saha (ACM-SIAM 2010 Symp. on Discrete Algorithms)] where the unrelated parallel machine scheduling problem is studied with machine activation cost. This is the standard unrelated parallel machine scheduling problem with a machine dependent activation cost that is incurred, if any job is assigned to the machine. The problem asks for a choice of machines to activate, and a schedule of all jobs on the active machines subject to the makespan constraint. The goal is to minimize the total activation cost. Our main generalization consists of a general activation cost model, where the activation cost for a machine is a non-decreasing function of its load. We develop a greedy algorithm that yields a fractional assignment of jobs, such that at least n - ε jobs are assigned fractionally and the total cost is at most 1 + ln(n/ε) times the optimum. Combining with standard rounding methods yields improved bounds for several machine activation problems. In addition, we study the machine activation problem with d linear constraints (these could model makespan constraints, as well as other types of constraints). Our method yields a schedule with machine activation cost of O(1/εlogn) times the optimum and a constraint violation by a factor of 2d + ε. This result matches our previous bound for the case d = 1. As a by-product, our method also yields a In n + 1 approximation factor for the non-metric universal facility location problem for which the cost of opening a facility is an arbitrary noii-decreasing function of the number of clients assigned to it. This gives an affirmative answer to the open question posed in earlier work on universal facility location.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
Pages80-94
Number of pages15
StatePublished - May 12 2011
Event22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 - San Francisco, CA, United States
Duration: Jan 23 2011Jan 25 2011

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
CountryUnited States
CitySan Francisco, CA
Period1/23/111/25/11

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Generalized machine activation problems'. Together they form a unique fingerprint.

  • Cite this

    Li, J., & Khuller, S. (2011). Generalized machine activation problems. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 (pp. 80-94). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).