Abstract Power consumption is the major cost factor in data centers. It can be reduced by dynamically right-sizing the data center according to the currently arriving jobs. If there is a long period with low load, servers can be powered down to save energy. For identical machines, the problem has already been solved optimally by [25] and [1]. In this paper, we study how a data-center with heterogeneous servers can dynamically be right-sized to minimize the energy consumption. There areddifferent server types with various operating and switching costs. We present a deterministic online algorithm that achieves a competitive ratio of 2das well as a randomized version that is 1.58d-competitive. Furthermore, we show that there is no deterministic online algorithm that attains a competitive ratio smaller than 2d. Hence our deterministic algorithm is optimal. In contrast to related problems like convex body chasing and convex function chasing [17, 30], we investigate the discrete setting where the number of active servers must be an integral, so we gain truly feasible solutions.

Power consumption is a dominant and still growing cost factor in data centers. In time periods with low load, the energy consumption can be reduced by powering down unused servers. We resort to a model introduced by Lin, Wierman, Andrew and Thereska (23,24) that considers data centers with identical machines, and generalize it to heterogeneous data centers with d different server types. The operating cost of a server depends on its load and is modeled by an increasing, convex function for each server type. In contrast to earlier work, we consider the discrete setting, where the number of active servers must be integral. Thereby, we seek truly feasible solutions. For homogeneous data centers (d=1), both the offline and the online problem were solved optimally in (3,4)

Electricity cost is a dominant and rapidly growing expense in data centers. Unfortunately, much of the consumed energy is wasted because servers are idle for extended periods of time. We study a capacity management problem that dynamically right-sizes a data center, matching the number of active servers with the varying demand for computing capacity. We resort to a data-center optimization problem introduced by Lin, Wierman, Andrew and Thereska~\citeW1a,W1 that, over a time horizon, minimizes a combined objective function consisting of operating cost, modeled by a sequence of convex functions, and server switching cost. All prior work addresses a continuous setting in which the number of active servers, at any time, may take a fractional value. In this paper, we investigate for the first time the discrete data-center optimization problem where the number of active servers, at any time, must be integer valued. Thereby we seek truly feasible solutions. First, we show that the offline problem can be solved in polynomial time. Our algorithm relies on a new, yet intuitive graph theoretic model of the optimization problem and performs binary search in a layered graph. Second, we study the online problem and extend the algorithm \em Lazy Capacity Provisioning (LCP) by Lin et al. \citeW1a,W1 to the discrete setting. We prove that LCP is 3-competitive. Moreover, we show that no deterministic online algorithm can achieve a competitive ratio smaller than~3. Hence, while LCP does not attain an optimal competitiveness in the continuous setting, it does so in the discrete problem examined here. We prove that the lower bound of~3 also holds in a problem variant with more restricted operating cost functions, introduced by Lin et al. \citeW1a. Finally, we address the continuous setting and give a lower bound of~2 on the best competitiveness of online algorithms. This matches an upper bound by Bansal et al. \citeB+. A lower bound of~2 was also recently shown by Antoniadis and Schewior~\citeA2. We develop an independent proof that extends to the scenario with more restricted operating cost.

DNA read mapping has become a ubiquitous task in bioinformatics. New technologies provide ever longer DNA reads (several thousand basepairs), although at comparatively high error rates (up to 15%), and the reference genome is increasingly not considered as a simple string over ACGT anymore, but as a complex object containing known genetic variants in the population. Conventional indexes based on exact seed matches, in particular the suffix array based FM index, struggle with these changing conditions, so other methods are being considered, and one such alternative is locality sensitive hashing. Here we examine the question whether including single nucleotide polymorphisms (SNPs) in a min-hashing index is beneficial. The answer depends on the population frequency of the SNP, and we analyze several models (from simple to complex) that provide precise answers to this question under various assumptions. Our results also provide sensitivity and specificity values for min-hashing based read mappers and may be used to understand dependencies between the parameters of such methods. We hope that this article will provide a theoretical foundation for a new generation of read mappers.