Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as : One is given a ground set @math , a collection @math of subsets thereof such that @math , and an objective (profit) function @math . The task is to choose a set @math that maximizes @math . We consider the version (, , both ICALP 2014) of such problems: The profit function @math (and possibly the set of feasible solutions @math ) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the trade-off between good per-time solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of @math and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the setting, that is, @math (along with possibly @math ) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future. We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constant-competitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.
The Multistage Max-Min Fair Allocation problem has been studied in the offline and the online settings in @cite_12 . This problem corresponds to a multistage variant of the Santa Klaus problem. For the off-line setting, the authors showed that the multistage version of the problem is much harder than the static one. They provided constant factor approximation algorithms for the off-line setting. For the online setting they proposed a constant competitive ratio for SSFS-type evolving instances and they proved that it is not possible to find an online algorithm with bounded competitive ratio for GE-type evolving instances. Finally, they showed that in the 1-lookahead case, where at time step @math we know the instance of time step @math , it is possible to get a constant approximation ratio.
@cite_12
2808191361
We consider the over-time version of the Max-Min Fair Allocation problem. Given a time horizon @math , with at each time t a set of demands and a set of available resources that may change over the time defining instance @math , we seek a sequence of solutions @math that (1) are near-optimal at each time t , and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k -lookahead setting where at time t , the instances at times @math are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the over-time version of the problem is much harder than the static one, since it becomes @math -hard even for families of instances for which the static problem is trivial. Then, we provide a @math -approximation algorithm for the off-line setting using as subroutine a ρ-approximation algorithm for the static version. We also give a @math -competitive algorithm for the online setting using also as subroutine a ρ-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a @math -approximation algorithm using as subroutine a ρ-approximation algorithm for the static version. This paper investigates the problem of scheduling jobs on multiple speed-scaled processors without migration, i.e., we have constant α > 1 such that running a processor at speed s results in energy consumption s#945; per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines and flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βBα-approximation algorithm for multiple processors, where Bα is the αth Bell number, that is, the number of partitions of a set of size α. Analogously, we show that any β-competitive online algorithm for a single processor yields a βBα-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βBα-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. All algorithms are based on the surprising fact that we can remove migration with a blowup of Bα in expectation. We consider a significant generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable. The problem considers a sequence of items arriving online that have to be allocated to agents, with different agents bidding different amounts. The objective function is the sum, over each agent i, of a monotonically non-decreasing concave function Mi : R+ -> R+ of the total amount allocated to i. All variants of online matching problems (including the Adwords problem) studied in the literature consider the special case of budgeted linear functions, that is, functions of the form Mi(ui) = min ui,Bi for some constant Bi. The distinguishing feature of this paper is in allowing arbitrary concave returns. The main result of this paper is that for each concave function M, there exists a constant F(M) ≤ 1 such that: there exists an algorithm with competitive ratio of miniF(Mi), independent of the sequence of items. No algorithm has a competitive ratio larger than F(M) over all instances with Mi= M for all i. Our algorithm is based on the primal-dual paradigm and makes use of convex programming duality. The upper bounds are obtained by formulating the task of finding the right counterexample as an optimization problem. This path takes us through the calculus of variations which deals with optimizing over continuous functions. The algorithm and the upper bound are related to each other via a set of differential equations, which points to a certain kind of duality between them. We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of @math , a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the @math bound.Our main result is a @math -approximation online algorithm for stochastic bipartite matching, breaking this @math barrier. Furthermore, we show that no online algorithm can produce a @math approximation for an arbitrarily small @math for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-) matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application. We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b=0 corresponds to the classical online model, and b=@?log|A|@?, where A is the algorithm's action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones. In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k-server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1@?b@?@Q(logn), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio @W(log(n) b) and we present a deterministic online algorithm for MTS with competitive ratio O(log(n) b). For the k-server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k^O^(^1^ ^b^) for any choice of @Q(1)@?b@?logk. We consider the online stochastic matching problem proposed by [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1 e. Annual IEEE Sympos. Foundations Comput. Sci. 117--126] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins, and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the number of allocations. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than 1-1 e were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that our algorithm achieves a competitive ratio of 0.705 when the rates are integral. On the hardness side, we prove that no online algorithm can have a competitive ratio better than 0.823 under the known distribution model (and henceforth under the permutation model). This improves upon the 5 6 hardness result proved by Goel and Mehta [Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. ACM-SIAM Symposium Discrete Algorithms 982--991] for the permutation model. We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k)-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O(log(k (k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k. Our solution is based on a two-step approach. We first obtain an O(log k)-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O(log N)-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves. We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMix with competitive ratio of e (e-1) 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf"@a, whose competitive ratio on s-bounded instances is 2-2 s+o(1 s). For 3-bounded instances its ratio is @f 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of 4-22 1.172. Also, in the 2-uniform case, we prove a lower bound of 2 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1 (1-(mm+1)^m)-competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases. We consider an online facility location problem where clients arrive over time and their demands have to be served by opening facilities and assigning the clients to opened facilities. When opening a facility we must choose one of K different lease types to use. A lease type k has a certain lease length lk. Opening a facility i using lease type k causes a cost of @math and ensures that i is open for the next lk time steps. In addition to costs for opening facilities, we have to take connection costs cij into account when assigning a client j to facility i. We develop and analyze the first online algorithm for this problem that has a time-independent competitive factor. This variant of the online facility location problem was introduced by [7] and is strongly related to both the online facility problem by [5] and the parking permit problem by [6]. Nagarajan and Williamson gave a 3-approximation algorithm for the offline problem and an O (Klogn)-competitive algorithm for the online variant. Here, n denotes the total number of clients arriving over time. We extend their result by removing the dependency on n (and thereby on the time). In general, our algorithm is @math -competitive. Here @math denotes the maximum lease length. Moreover, we prove that it is @math -competitive for many "natural" cases. Such cases include, for example, situations where the number of clients arriving in each time step does not vary too much, or is non-increasing, or is polynomially bounded in @math . We consider the problem of scheduling jobs that are given as groups of non-intersecting segments on the real line. Each job J j is associated with an interval, I j , which consists of up to t segments, for some t ≥ 1, a positive weight, w j , and two jobs are in conflict if any of their segments intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g. bandwidth in linear processor arrays), and in computational biology geometry. The objective is to schedule a subset of non-conflicting jobs of maximum total weight.In a single machine environment, our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of t = 1 is an ordinary interval graph). We show that, for t ≥ 2, this problem is APX-hard, even for highly restricted instances. Our main result is a 2t-approximation algorithm for general instances, based on a novel fractional version of the Local Ratio technique. Previously, the problem was considered only for proper union graphs, a restricted subclass of t-interval graphs, and the approximation factor achieved was (2t - 1 + 1 2t). A bi-criteria polynomial time approximation scheme (PTAS) is developed for the subclass of t-union graphs.In the online case, we consider uniform weight jobs that consist of at most two segments. We show that when the resulting 2-interval graph is proper, a simple greedy algorithm is 3-competitive, while any randomized algorithm has competitive ratio at least 2.5. For general instances, we give a randomized O(log2 R)-competitive (or O((log R)2+e)-competitive) algorithm, where R is the known (unknown) ratio between the longest and the shortest segment in the input sequence. Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one-by-one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is to maximize a submodular function over the set of elements in the solution. We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a @math -competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most @math elements in its solution. Given a set S of radio stations located on a line and an integer h (1 ≤ h ≤ |S| - 1), the Min Assignment problem is to find a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem were known only when h = |S| - 1 (i.e. the unbounded case) or when the stations are equally spaced (i.e. the uniform chain). In particular, Kirousis, Kranakis, Krizanc and Pelc (1997) provided an efficient exact solution for the unbounded case and efficient approximated solutions for the uniform chain, respectively. This paper presents the first polynomial time, approximation algorithm for the Min Assignment problem. The algorithm guarantees an approximation ratio of 2 and runs in time O(hn3). We also prove that, for constant h and for "well spread" instances (a broad generalization of the uniform chain case), we can find a solution in time O(hn3) whose cost is at most an (1 + Ɛ(n)) factor from the optimum, where Ɛ(n) = o(1) and n is the number of stations. This result significantly improves the approximability result by on uniform chains. Both of our approximation results are obtained by new algorithms that exactly solves two natural variants of the Min Assignment problem that might have independent interest: the All-To-One problem (in which every station must reach a fixed one in at most h hops) and the Base Location problem (in which the goal is to select a set of Basis among the stations and all the other stations must reach one of them in at most h -1 hops). Finally, we show that for h = 2 the Min Assignment problem can be solved in O(n3)-time. We study approximation algorithms for several variants of the MaxCover problem, with the focus on algorithms that run in FPT time. In the MaxCover problem we are given a set N of elements, a family S of subsets of N, and an integer K. The goal is to find up to K sets from S that jointly cover (i.e., include) as many elements as possible. This problem is well-known to be NP-hard and, under standard complexitytheoretic assumptions, the best possible polynomial-time approximation algorithm has approximation ratio (1 − 1 ). We first consider a variant of MaxCover with bounded element frequencies, i.e., a variant where there is a constant p such that each element belongs to at most p sets in S. For this case we show that there is an FPT approximation scheme (i.e., for each β there is a β-approximation algorithm running in FPT time) for the problem of maximizing the number of covered elements, and a randomized FPT approximation scheme for the problem of minimizing the number of elements left uncovered (we take K to be the parameter). Then, for the case where there is a constant p such that each element belongs to at least p sets from S, we show that the standard greedy approximation algorithm achieves approximation ratio exactly 1 − e −max(pK kSk,1) . We conclude by considering an unrestricted variant of MaxCover, and show approximation algorithms that run in exponential time and combine an exact algorithm with a greedy approximation. Some of our results improve currently known results for MaxVertexCover. In the online minimum-cost metric matching problem, we are given an instance of a metric space with k servers, and must match arriving requests to as-yet-unmatched servers to minimize the total distance from the requests to their assigned servers. We study this problem for the line metric and for doubling metrics in general. We give O(logk)-competitive randomized algorithms, which reduces the gap between the current O(log2k)-competitive randomized algorithms and the constant-competitive lower bounds known for these settings. We first analyze the "harmonic" algorithm for the line, that for each request chooses one of its two closest servers with probability inversely proportional to the distance to that server; this is O(logk)-competitive, with suitable guess-and-double steps to ensure that the metric has aspect ratio polynomial in k. The second algorithm embeds the metric into a random HST, and picks a server randomly from among the closest available servers in the HST, with the selection based upon how the servers are distributed within the tree. This algorithm is O(1)-competitive for HSTs obtained from embedding doubling metrics, and hence gives a randomized O(logk)-competitive algorithm for doubling metrics. Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by [1995], and we adopt their setting. We assume that the power required to run at speed s is P(s) e sα for some constant α > 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2α − 1 αα-competitive with respect to energy. We provide a tight αα bound on the competitive ratio of OA with respect to energy. We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1 b, where b is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is e-competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for α ≥5. Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm. We consider the online problem of non-preemptive queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. This corresponds to the well known and strongly motivated Naor's model in operations research. We give a queue management algorithm with a competitive ratio equal to the golden ratio (φ a 1.618) in the case that all packets have the same value, along with a matching lower bound. We also derive Θ(1) upper and lower bounds on the competitive ratio when packets have different intrinsic values (in the case of differentiated services). We can extend our results to deal with more general models for loss of value over time. Finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor. A Fixed-Parameter Tractable ( ) @math -approximation algorithm for a minimization (resp. maximization) parameterized problem @math is an FPT algorithm that, given an instance @math computes a solution of cost at most @math (resp. @math ) if a solution of cost at most (resp. at least) @math exists; otherwise the output can be arbitrary. For well-known intractable problems such as the W[1]-hard Clique and W[2]-hard Set Cover problems, the natural question is whether we can get any -approximation. It is widely believed that both Clique and Set-Cover admit no FPT @math -approximation algorithm, for any increasing function @math . Assuming standard conjectures such as the Exponential Time Hypothesis (ETH) eth-paturi and the Projection Games Conjecture (PGC) r3 , we make the first progress towards proving this conjecture by showing that 1. Under the ETH and PGC, there exist constants @math such that the Set Cover problem does not admit an FPT approximation algorithm with ratio @math in @math time, where @math is the size of the universe and @math is the number of sets. 2. Unless @math , for every @math there exists a constant @math such that Clique has no FPT cost approximation with ratio @math in @math time, where @math is the number of vertices in the graph. In the second part of the paper we consider various W[1]-hard problems such as , , Directed Steiner Network and . For all these problem we give polynomial time @math -approximation algorithms for some small function @math (the largest approximation ratio we give is @math ). We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procacciafirst (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1- @math allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a @math - @math allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a @math - @math allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of ! to a @math factor in the additive setting. The main idea for our @math - @math allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time. We consider the online competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. Our work examines this model when parameterizing an instance by a new value which we term the patience. This parameter measures each job's willingness to endure a delay before starting, relative to this same job's processing time. Specifically, the slack of a job is defined as the gap between its release time and the last possible time at which it may be started while still meeting its deadline. We say that a problem instance has patience κ, if each job with length ||J|| has a slack of at least κ ċ ||J||.Without any restrictions placed on the job characteristics, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee a constant bound on the competitiveness of a resulting schedule. Previous researchers have analyzed a problem instance by parameterizing based on the ratio between the longest job's processing time and the shortest job's processing time. Our main contribution is to provide a fine-grained analysis of the problem when simultaneously parameterized by patience and the range of job lengths. We are able to give tight or almost tight bounds on the deterministic competitiveness for all parameter combinations.If viewing the analysis of each parameter individually, our evidence suggests that parameterizing solely on patience provides a richer analysis than parameterizing solely on the ratio of the job lengths. For example, in the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any κ ≥ 0 is exactly 1 + 1 (⌊κ⌋ + 1). Without any bound on the job lengths, a simple greedy algorithm is (2+ 1 κ)- competitive for any κ > 0. More generally we will find that for any fixed ratio of job lengths, the competitiveness of the problem tends towards 1 as the patience is increased. The converse is not true, as for any fixed κ > 0 we find that the competitiveness is bounded away from 1, no matter what further restrictions are placed on the ratio of job lengths. Existing work on scheduling with energy concern has focused on minimizing the energy for completing all jobs or achieving maximum throughput [19, 2,7,13,14]. That is, energy usage is a secondary concern when compared to throughput and the schedules targeted may be very poor in energy efficiency. In this paper, we attempt to put energy efficiency as the primary concern and study how to maximize throughput subject to a user-defined threshold of energy efficiency. We first show that all deterministic online algorithms have a competitive ratio at least Δ, where Δ is the max-min ratio of job size. Nevertheless, allowing the online algorithm to have a slightly poorer energy efficiency leads to constant (i.e., independent of Δ) competitive online algorithm. On the other hand, using randomization, we can reduce the competitive ratio to O(logΔ) without relaxing the efficiency threshold. Finally we consider a special case where no jobs are "demanding" and give a deterministic online algorithm with constant competitive ratio for this case.