检索结果-内蒙古大学图书馆

Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

作者： Linquan Zhang Zongpeng Li Chuan Wu Shaolei Ren University of Calgary Calgary AB Canada The University of Hong Kong Hong Kong Hong Kong Florida International University Miami FL USA

ISBN: (纸本)9781450334860

This work studies the online electricity cost minimization problem at a co-location data center. A co-location data center serves multiple tenants who rent the physical infrastructure within the data center to run their respective cloud computing services. Consequently, the co-location operator has no direct control over power consumption of its tenants, and an efficient mechanism is desired for eliciting desirable consumption patterns from the co-location tenants. Electricity billing faced by a data center is nowadays based on both the total volume consumed and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem, which also exhibits an online nature due to the definition of peak consumption. We model and solve the problem through two approaches: the pricing approach and the auction approach. For the former, we design an offline 2-approximation algorithm as well as an online algorithm with a small competitive ratio in most practical settings. For the latter, we design an efficient (2+c)-competitive online algorithm, where c is a system dependent parameter close to 1.49, and then convert it into an efficient mechanism that executes in an online fashion, runs in polynomial time, and guarantees truthful bidding and (2+2c)-competitive in social cost.

关键词： co-location data center approximation algorithms online algorithms mechanism design

来源：评论

学校读者我要写书评

暂无评论

online constrained optimization with recourse

引用

INFORMATION PROCESSING LETTERS 2013年第3期113卷 81-86页

作者： Avitabile, T. Mathieu, C. Parkinson, L. NYU Dept Comp Sci New York NY 10012 USA Brown Univ Dept Comp Sci Providence RI 02912 USA

We study online packing and covering problems, stated as zero-one linear programs. This class of problems includes maximum cut, bipartite matching, and set cover. In the packing problem, variables arrive in an online fashion. Upon arrival of v, the weight of v in the objective function and in any constraints involving v is revealed and the algorithm may update its solution. In the covering problem, constraints arrive in an online fashion. We allow the relaxation that the algorithm may change the value of each variable a constant number of times, k. We give an algorithm for onlinePacking(k) and prove that for any is an element of > 0, there exists some k equal to (O) over tilde (1/is an element of) such that the algorithm gives a (1 - is an element of) approximation for onlinePacking(k). We then show near-tightness for several cases. We also prove that no deterministic algorithm exists for onlineCovering(k) that achieves a competitive ratio less than 3/2. (C) 2012 Elsevier B.V. All rights reserved.

关键词： online algorithms Approximation algorithms Maximum cut Bipartite matching Ad-auctions

来源：评论

学校读者我要写书评

暂无评论

Fair online load balancing

引用

JOURNAL OF SCHEDULING 2013年第1期16卷 117-127页

作者： Buchbinder, Niv Naor, Joseph (Seffi) Open Univ Raanana Israel Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-a model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. (In: Symposium on discrete algorithms, pp. 384-390, 2005). These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg et al. (In: Proceedings of the 40th annual symposium on foundations of computer science, p. 568, 2001), as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness. We resolve a question posed by Goel et al. (In: Symposium on discrete algorithms, pp. 384-390, 2005) proving that the greedy strategy is globally O(log m)-fair, where m denotes the number of machines. This result improves upon the analysis of Goel et al. (In: Symposium on discrete algorithms, pp. 384-390, 2005) who showed that the greedy strategy is globally O(log n)-fair, where n is the number of jobs. Typically, na parts per thousand << m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness. The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in Azar et al. (J. algorithms 18:221-237, 1995). We provide an alternative bound which is not worse than the bounds of Azar et al. (J. algorithms 18:221-237, 1995), and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we find that the greedy algorithm results in an assignment that is globally O(log m)-balanced. The last result generalizes the previous result of Goel et al. (In: Symposium on discrete algorithms, pp. 384-390, 2005) who proved that the greedy algorithm yields an assignment that is globally O(l

关键词： online algorithms Scheduling Load balancing Restricted assignment Competitive analysis Fairness

来源：评论

学校读者我要写书评

暂无评论

online Service with Delay

引用

ACM TRANSACTIONS ON algorithms 2021年第3期17卷 1–31页

作者： Azar, Yossi Ganesh, Arun Ge, Rong Panigrahi, Debmalya Tel Aviv Univ Blavatnik Sch Comp Sci POB 39040 IL-6997801 Tel Aviv Israel Duke Univ Dept Comp Sci 308 Res Dr Durham NC 27708 USA

In this article, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and there is a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between hatching requests to improve locality and reducing delay to improve response time, which has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm. The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to k > 1 servers and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.

关键词： Paging weighted paging k-server online algorithms competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online facility location with mobile facilities

引用

THEORETICAL COMPUTER SCIENCE 2022年 907卷 45-61页

作者： Feldkord, Bjorn Knollmann, Till Heide, Friedhelm Meyer Auf der Paderborn Univ Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Paderborn Univ Dept Comp Sci Furstenallee 11 D-33102 Paderborn Germany

We examine the online Facility Location problem in an extended version. Fotakis showed a lower bound of Omega(log n/log log n) for the original online Facility Location problem, where n is the number of clients. This bound holds even on the real line and for randomized algorithms against oblivious adversaries. We propose randomized online algorithms in the following setting: We consider the Euclidean space of arbitrary dimension and allow the facilities to either move arbitrarily or to move at most a constant distance m in each time step. The costs for moving a facility from a to b is D . d(a, b) where D >= 1 is a constant. Clients are assigned to facilities instantly and irreversibly. The cost for serving the clients is either calculated as soon as a client arrives or at the end of the computation. The algorithms for these two cost models achieve the same competitiveness on the line, which, in contrast to the original online Facility Location problem, is independent of n. In the case of arbitrary movement, it only depends on D. In the case of a limited movement distance m, it additionally depends on m and the opening costs of the facilities. We show that our results are asymptotically tight on the real line. For the Euclidean space of higher dimensions, we give an algorithm for the model where costs for clients are evaluated immediately. The competitive ratio of our algorithm depends on the above parameters and additionally on the number of optimal facilities. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Facility location online algorithms Resource augmentation

来源：评论

学校读者我要写书评

暂无评论

online File Caching with Rejection Penalties

引用

ALGORITHMICA 2015年第2期71卷 279-306页

作者： Epstein, Leah Imreh, Csanad Levin, Asaf Nagy-Gyoergy, Judit Univ Haifa Dept Math IL-31905 Haifa Israel Univ Szeged Dept Informat H-6720 Szeged Hungary Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel Univ Szeged Dept Math H-6720 Szeged Hungary

In the file caching problem, the input is a sequence of requests for files out of a slow memory. A file has two attributes, a positive retrieval cost and an integer size. An algorithm is required to maintain a cache of size k such that the total size of files stored in the cache never exceeds k. Given a request for a file that is not present in the cache at the time of request, the file must be brought from the slow memory into the cache, possibly evicting other files from the cache. This incurs a cost equal to the retrieval cost of the requested file. Well-known special cases include paging (all costs and sizes are equal to 1), the cost model, which is also known as weighted paging, (all sizes are equal to 1), the fault model (all costs are equal to 1), and the bit model (the cost of a file is equal to its size). If bypassing is allowed, a miss for a file still results in an access to this file in the slow memory, but its subsequent insertion into the cache is optional. We study a new online variant of caching, called caching with rejection. In this variant, each request for a file has a rejection penalty associated with the request. The penalty of a request is given to the algorithm together with the request. When a file that is not present in the cache is requested, the algorithm must either bring the file into the cache, paying the retrieval cost of the file, or reject the file, paying the rejection penalty of the request. The objective function is the sum of total rejection penalty and the total retrieval cost. This problem generalizes both caching and caching with bypassing. We design deterministic and randomized algorithms for this problem. The competitive ratio of the randomized algorithm is O(logk), and this is optimal up to a constant factor. In the deterministic case, a k-competitive algorithm for caching, and a (k+1)-competitive algorithm for caching with bypassing are known. Moreover, these are the best possible competitive ratios. In contrast, we prese

关键词： Caching Paging online algorithms

来源：评论

学校读者我要写书评

暂无评论

online Constrained Forest and Prize-Collecting Network Design

引用

ALGORITHMICA 2018年第11期80卷 3335-3364页

作者： Qian, Jiawei Umboh, Seeun William Williamson, David P. JW Capital Beijing Peoples R China Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berman and Coulston (Proceedings of the 29th annual ACM symposium on theory of computing, pp 344-353, 1997) and one for (offline) general network design problems due to Goemans and Williamson (SIAM J Comput 24:296-317, 1995);we give an -competitive algorithm, where k is the number of nodes that must be connected. We also consider a further generalization of the problem that allows us to pay penalties in exchange for violating connectivity constraints;we give an online -competitive algorithm for this case as well.

关键词： online algorithms Competitive ratio Generalized Steiner tree Prize-collecting Steiner tree

来源：评论

学校读者我要写书评

暂无评论

online Regenerator Placement

引用

THEORY OF COMPUTING SYSTEMS 2017年第3期61卷 739-754页

作者： Mertzios, George B. Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel Univ Durham Sch Engn & Comp Sci Durham England TelHai Coll IL-12210 Upper Galilee Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Technion Dept Comp Sci Haifa Israel

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one lightpath. The placement of regenerators has become an active area of research during recent years, and various optimization problems have been studied. The first such problem is the Regeneration Location Problem (Rlp), where the goal is to place the regenerators so as to minimize the total number of nodes containing them. We consider two extreme cases of online Rlp regarding the value of d and the number k of regenerators that can be used in any single node. (1) d is arbitrary and k unbounded. In this case a feasible solution always exists. We show an O(log|X|ai... logd)-competitive randomized algorithm for any network topology, where X is the set of paths of length d. The algorithm can be made deterministic in some cases. We show a deterministic lower bound of , where E is the edge set. (2) d = 2 and k = 1. In this case there is not necessarily a solution for a given input. We distinguish between feasible inputs (for which there is a solution) and infeasible ones. In the latter case, the objective is to satisfy the maximum number of lightpaths. For a path topology we show a lower bound of for the competitive ratio (where l is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs.

关键词： online algorithms Competitive ratio Optical networks Regenerators

来源：评论

学校读者我要写书评

暂无评论

Max-Coloring and online Coloring with Bandwidths on Interval Graphs

引用

ACM TRANSACTIONS ON algorithms 2011年第3期7卷 1–21页

作者： Pemmaraju, Sriram V. Raman, Rajiv Varadarajan, Kasturi Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Iowa Dept Comp Sci Iowa City IA 52240 USA

Given a graph G = (V, E) and positive integral vertex weights w : V -> N, the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C-1, C-2,C- ... , C-k, minimize Sigma(k)(i=1) max(v epsilon Ci) w(v). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system. Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 . chi(G) colors, significantly improving the bound of 26 . chi(G) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard. The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i epsilon I having an associated bandwidth b(i) epsilon (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r, the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different

关键词： Approximation algorithms buffer minimization coloring online algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

online Battery Storage Management via Lyapunov Optimization in Active Distribution Grids

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2021年第2期29卷 672-690页

作者： Stai, Eleni Wang, Cong Le Boudec, Jean-Yves Ecole Polytech Fed Lausanne EPFL Lab Commun & Applicat CH-1015 Lausanne Switzerland Ecole Polytech Fed Lausanne EPFL CH-1015 Lausanne Switzerland

We consider low run-time complexity power management in distribution grids with renewable energy sources (RESs) and batteries, where forecasts are unavailable. We propose iterative Lyapunov Real-time Control (iLypRC), a fast online algorithm, which does not need forecasts, for the real-time battery control. iLypRC is designed via Lyapunov optimization and applies either to follow a previously computed dispatch plan or to optimize the monetary cost, while it satisfies look-ahead state-of-energy constraints. iLypRC requires only bounds on the uncertain quantities for each real-time interval. iLypRC efficiently accounts for grid losses, battery efficiency, and grid constraints via iterative linearizations of the power flow equations. We compute a theoretical upper bound on the difference between the cost of iLypRC and the cost of an oracle. Finally, numerical evaluations (using real data) on a 4-bus distribution grid and a 34-bus real Swiss grid show that iLypRC achieves a cost very close to that of a model predictive control (MPC) with a good forecast, but iLypRC needs no forecast and has much lower run-time complexity. Also, when the MPC forecast is inaccurate, iLypRC outperforms MPC.

关键词： Batteries Real-time systems Mathematical model Uncertainty Cost function Complexity theory Battery storage systems grid losses Lyapunov optimization online algorithms real-time control

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：