We present a general model for the operation of a cloud computing server comprised of one or more speed-scalable processors. Typically, agents submit tasks to such a cloud computing server in an online fashion, and the server operator has to schedule the tasks and decide on payments without knowledge of tasks arriving in the future. Moreover, the operator should take the different incentives of the agents into account and aim to minimize the energy expenditure. For both the offline and the online setting we provide mechanisms with several desirable properties: The induced game admits a Nash equilibrium, the mechanism is budget balanced, has low communication complexity, is computationally tractable, is intuitive to explain, but above all, has a constant Price of Anarchy. Therefore, the total costs are not too far off from the social optimum. We extend our results to the case of multiple processors and to the Bayesian setting.

In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value. The most classic version of the problem is that in which the elements arrive in random order and their values are arbitrary. Here, the optimal algorithm picks the maximum value with probability at least 1/e. However, by varying the available information, new interesting problems arise. For instance, in the full information variant of the secretary problem the values are i.i.d. samples from a known distribution. Naturally, the best possible success probability increases and turns out to be approximately 0.58. Also, the case in which the arrival order is adversarial instead of random leads to interesting variants that have been considered in the literature. In this paper we study both the random order and adversarial order secretary problems with an additional twist. The values are arbitrary, but before starting the online sequence we independently sample each element with a fixed probability p. The sampled elements become our information or history set and the game is played over the remaining elements. We call these problems the random order secretary problem with p-sampling (ROSp for short) and the adversarial order secretary problem with p-sampling (AOSp for short). Our main result is to obtain best possible algorithms for both problems and all values of p. As p grows to 1 the obtained guarantees converge to the optimal guarantees in the full information case. In the adversarial order setting, the best possible algorithm turns out to be a simple fixed threshold algorithm in which the optimal threshold is a function of p only. Therefore, even knowledge of the total number of elements is unnecessary. Proving that this algorithm is optimal involves a novel technique, which boils down to analyzing a related game in a conflict graph over binary sequences. In the random order setting we prove that the best possible algorithm is characterized by a fixed sequence of time thresholds, dictating at which point in time we should start accepting a value that is both a maximum of the online sequence and has a given ranking within the sampled elements. Surprisingly, this sequence of time thresholds arises from a separable and convex optimization problem whose solution is independent of p.

Posted price mechanisms constitute a widely used way of selling items to strategic consumers. Although suboptimal, the attractiveness of these mechanisms comes from their simplicity and easy implementation. In this paper, we investigate the performance of posted price mechanisms when customers arrive in an unknown random order. We compare the expected revenue of these mechanisms to the expected revenue of the optimal auction in two different settings. Namely, the nonadaptive setting in which all offers are sent to the customers beforehand, and the adaptive setting in which an offer is made when a consumer arrives. For the nonadaptive case, we obtain a strategy achieving an expected revenue within at least a 1-1/e fraction of that of the optimal auction. We also show that this bound is tight, even if the customers have i.i.d. valuations for the item. For the adaptive case, we exhibit a posted price mechanism that achieves a factor 0.745 of the optimal revenue, when the customers have i.i.d. valuations for the item. Furthermore, we prove that our results extend to the prophet inequality setting and in particular our result for i.i.d. random valuations resolves a problem posed by Hill and Kertz. [13]

We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in $$[0,1]^d$$ , and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is $$n^{f(\epsilon ,d)}$$ where $$f(\epsilon ,d) = (1/\epsilon )^{\tilde{O}(d)}$$ ( $$\tilde{O}$$ suppresses polylogarithmic terms in d). In particular, the dependence on d is double exponential. In this paper we show that a double exponential dependence on d is necessary, and give an improved algorithm with essentially optimal running time. Specifically, we let $$\exp (x)$$ denote $$2^x$$ and show that: (1) For any $$\epsilon <1$$ , there is no $$(1+\epsilon )$$ -approximation with running time $$\exp \left( o(\lfloor 1/\epsilon \rfloor ^{d/3})\right) $$ unless the Exponential Time Hypothesis fails. (2) No $$(1+\epsilon )$$ -approximation with running time $$\exp \left( \lfloor 1/\epsilon \rfloor ^{o(d)}\right) $$ exists, unless NP has subexponential time algorithms. (3) Similar lower bounds also hold even if $$\epsilon m$$ extra machines are allowed (i.e. with resource augmentation), for sufficiently small $$\epsilon >0$$ . (4) We complement these lower bounds with a $$(1+\epsilon )$$ -approximation that runs in time $$\exp \left( (1/\epsilon )^{O(d \log \log d)}\right) + nd$$ . This gives the first efficient approximation scheme (EPTAS) for the problem.

Parsimony haplotyping is the problem of finding a set of haplotypes of minimum cardinality that explains a given set of genotypes, where a genotype is explained by two haplotypes if it can be obtained as a combination of the two. This problem is NP-complete in the general case, but polynomially solvable for (k, l)-bounded instances for certain k and l. Here, k denotes the maximum number of ambiguous sites in any genotype, and l is the maximum number of genotypes that are ambiguous at the same site. Only the complexity of the (*, 2)-bounded problem is still unknown, where * denotes no restriction. It has been proved that (*, 2)-bounded instances have compatibility graphs that can be constructed from cliques and circuits by pasting along an edge. In this paper, we give a constructive proof of the fact that (*, 2)-bounded instances are polynomially solvable if the compatibility graph is constructed by pasting cliques, trees and circuits along a bounded number of edges. We obtain this proof by solving a slightly generalized problem on circuits, trees and cliques respectively, and arguing that all possible combinations of optimal solutions for these graphs that are pasted along a bounded number of edges can be enumerated efficiently.