We present approximation algorithms for some variants of \(k\)-center clustering and diversity maximization in a fully dynamic setting, where the active pointset evolves through arbitrary insertions and deletions. All...
详细信息
We present approximation algorithms for some variants of \(k\)-center clustering and diversity maximization in a fully dynamic setting, where the active pointset evolves through arbitrary insertions and deletions. All algorithms employ a coreset-based strategy and rely on the use of the cover tree data structure, which we crucially augment to maintain, at any time, some additional information enabling the efficient extraction of the solution for the specific problem. For all the problems under consideration, our algorithms compute \((\alpha+\varepsilon)\)-approximate solutions, where \(\alpha\) is the best known approximation attainable in polynomial time in the standard static setting, and \(\varepsilon>0\) is a user-provided accuracy parameter. Remarkably, and unlike previous works, the (cover tree) data structure used by our algorithms and the running times of the update procedures are both independent of the accuracy parameter \(\varepsilon\) and, for the \(k\)-center variants, also of parameter \(k\). The analysis is performed in terms of the doubling dimension of the metric space which the points belong to, and it shows that, for spaces of bounded doubling dimension, the times required to extract solutions to the above problems are dramatically smaller than those that would be required to recompute solutions on the entire active pointset from scratch. To the best of our knowledge, ours are the first solutions for the matroid-center and diversity maximization problems in the fully dynamic setting. The theoretical results are complemented by an extensive set of experiments, which demonstrate the efficiency and effectiveness of our algorithms for \(k\)-center without and with outliers against previously known ones.
The emerging federated cloud paradigm advocates sharing of resources among cloud providers, to exploit temporal availability of resources and diversity of operational costs for job serving. While extensive studies exi...
详细信息
ISBN:
(纸本)9781467359443
The emerging federated cloud paradigm advocates sharing of resources among cloud providers, to exploit temporal availability of resources and diversity of operational costs for job serving. While extensive studies exist on enabling interoperability across different cloud platforms, a fundamental question on cloud economics remains unanswered: When and how should a cloud trade VMs with others, such that its net profit is maximized over the long run? In order to answer this question by the federation, a number of important, correlated decisions, including job scheduling, server provisioning and resource pricing, need to be dynamically made, with long-term profit optimality being a goal. In this work, we design efficient algorithms for inter-cloud resource trading and scheduling in a federation of geo-distributed clouds. For VM trading among clouds, we apply a double auction-based mechanism that is strategyproof, individual rational, and ex-post budget balanced. Coupling with the auction mechanism is an efficient, dynamic resource trading and scheduling algorithm, which carefully decides the true valuations of VMs in the auction, optimally schedules stochastic job arrivals with different SLAs onto the VMs, and judiciously turns on and off servers based on the current electricity prices. Through rigorous analysis, we show that each individual cloud, by carrying out our dynamic algorithm, can achieve a time-averaged profit arbitrarily close to the offline optimum.
暂无评论