Demand response (DR) is not only a crucial solution to the demand side management but also a vital means of electricity market in maintaining power grid reliability, sustainability and stability. DR can enable consumers (e.g. data centers) to reduce their electricity consumption when the supply of electricity is a shortage. The consumers will be rewarded in the case of DR if they reduce or shift some of their energy usage during peak hours. Aiming at solving the efficiency of DR, in this paper, we present MEDR, a mechanism on emergency DR in colocation data center. First, we formalize the MEDR problem and propose a dynamic programming to solve the optimization version of the problem. We then design a deterministic mechanism as a solution to solve the MEDR problem. We show that our proposed mechanism is truthful. Next, we prove that our mechanism is an FPTAS, i.e., it can be approximated within @math for any given @math , while the running time of our mechanism is polynomial in @math and @math , where @math is the number of tenants in the datacenter. Furthermore, we also give an auction system covering the efficient FPTAS algorithm as bidding decision program for DR in colocation datacenter. Finally, we choose a practical smart grid dataset to build a large number of datasets for simulation in performance evaluation. By evaluating metrics of the approximation ratio of our mechanism, the non-negative utility of tenants and social cost of colocation datacenter, the results demonstrate the effectiveness of our work.
@cite_2: This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.
@cite_2 presented a truthful FPTAS for the max-knapsack problem. Our problem differs from the min-knapsack in which we have BES such that the capacity of the knapsack we need to cover is soft.