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

Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching

THEORETICAL COMPUTER SCIENCE 2015年 607卷 247-256页

作者： Ting, H. F. Xiang, Xiangzhong Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

This paper studies the online maximum edge-weighted b-matching problem. The input of the problem is a weighted bipartite graph G = (L, R, E, w). Vertices in R arrive online, and each vertex in L can be matched to at most b vertices in R. The objective is to maximize the total weight of the matching edges. We give a randomized algorithm GREEDY-RT for this problem, and show that its competitive ratio is Omega(1/Pi(log*wmax-1)(J=1) log((j)) w(max)) where w(max) is an upper bound on the edge weights, which may not be known ahead of time. We can improve the competitive ratio to Omega(1/logw(max)) if w(max) is known to the algorithm when it starts. We also derive an upper bound O(1/logw(max)) on the competitive ratio, suggesting that GREEDY-RT is near optimal. We also consider deterministic algorithms;we present a near optimal algorithm GREEDY-D which has competitive ratio 1/1+2 xi(w(max)+1)(1/xi) where xi = min{b, left perpendicular ln(1 + w(max))right perpendicular}. We also study a variant of the problem called online maximum two-sided vertex-weighted b-matching problem, and give a modification of the randomized algorithm GREEDY-RT called GREEDY-vRT for this variant. We show that the competitive ratio of GREEDY-vRT is also near optimal. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Maximum weighted matching online algorithms Competitive analysis Upper and lower bounds

来源：评论

学校读者我要写书评

暂无评论

algorithms better than LPT for semi-online scheduling with decreasing processing times

引用

OPERATIONS RESEARCH LETTERS 2012年第5期40卷 349-352页

作者： Cheng, T. C. E. Kellerer, Hans Kotov, Vladimir Graz Univ Inst Stat & Operat Res A-8010 Graz Austria Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Belarusian State Univ Fac Appl Math & Comp Sci Minsk 220030 BELARUS

We consider the semi-online multiprocessor scheduling problem with m identical, parallel machines to minimize the makespan, where the jobs arrive in decreasing order of processing times. The famous Longest Processing Time (LPT) algorithm by Graham (1966) [4] for the classical offline multiprocessor scheduling problem schedules the jobs in decreasing order of processing times and has a worst-case bound of 4/3-1/(3m). So far, no algorithm with a better competitive ratio than the LPT algorithm has been given for the semi-online scheduling problem with decreasing processing times. In this note, we present a 5/4-competitive algorithm for m >= 3 and an algorithm that is the best possible for m = 3, i.e. an algorithm with competitive ratio (1 + root 37)/6. (C) 2012 Elsevier B.V. All rights reserved.

关键词： online algorithms Semi-online algorithms Competitive ratio Multiprocessor scheduling

来源：评论

学校读者我要写书评

暂无评论

online graph exploration: New results on old and new algorithms

引用

THEORETICAL COMPUTER SCIENCE 2012年 463卷 62-72页

作者： Megow, Nicole Mehlhorn, Kurt Schweitzer, Pascal Australian Natl Univ Canberra ACT 0200 Australia Max Planck Inst Informat D-66123 Saarbrucken Germany

We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs (Constructing competitive tours from local information, Theoretical Computer Science 130, pp. 125-138, 1994) proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs. While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus. Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph exploration online algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Improved competitive algorithms for online scheduling with partial job values

引用

THEORETICAL COMPUTER SCIENCE 2004年第3期325卷 467-478页

作者： Chin, FYL Fung, SPY Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong Peoples R China

This paper considers an online scheduling problem arising from Quality-of-Service (QoS) applications. We are required to schedule a set of jobs, each with release time, deadline, processing time and weight. The objective is to maximize the total value obtained for scheduling the jobs. Unlike the traditional model of this scheduling problem, in our model unfinished jobs also get partial values proportional to their amounts processed. No non-timesharing algorithm for this problem with competitive ratio better than 2 is known. We give a new non-timesharing algorithm GAP that improves this ratio for bounded values of m, where m can be the number of concurrent jobs or the number of weight classes. The competitive ratio is improved from 2 to 1.618 (golden ratio) which is optimal for m = 2, and when applied to cases with in > 2 it still gives a competitive ratio better than 2, e.g. 1.755 when m = 3. We also give a new study of the problem in the multiprocessor setting, giving an upper bound of 2 and a lower bound of 1.25 for the competitiveness. Finally, we consider resource augmentation and show that O(log alpha) speedup or extra processors is sufficient to achieve optimality, where a is the importance ratio. We also give a tradeoff result, showing that in fact a small amount of extra resources is sufficient for achieving close-to-optimal competitiveness. (C) 2004 Elsevier B.V. All rights reserved.

关键词： online algorithms scheduling partial job values resource augmentation

来源：评论

学校读者我要写书评

暂无评论

The online Pause and Resume Problem: Optimal algorithms and An Application to Carbon-Aware Load Shifting

引用

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2023年第3期7卷 1-32页

作者： Lechowicz, Adam Christianson, Nicolas Zuo, Jinhang Bashir, Noman Hajiesmaili, Mohammad Wierman, Adam Shenoy, Prashant Univ Massachusetts Amherst MA 01003 USA CALTECH Pasadena CA 91125 USA

We introduce and study the online pause and resume problem. In this problem, a player attempts to find the k lowest (alternatively, highest) prices in a sequence of fixed length T, which is revealed sequentially. At each time step, the player is presented with a price and decides whether to accept or reject it. The player incurs a switching cost whenever their decision changes in consecutive time steps, i.e., whenever they pause or resume purchasing. This online problem is motivated by the goal of carbon-aware load shifting, where a workload may be paused during periods of high carbon intensity and resumed during periods of low carbon intensity and incurs a cost when saving or restoring its state. It has strong connections to existing problems studied in the literature on online optimization, though it introduces unique technical challenges that prevent the direct application of existing algorithms. Extending prior work on threshold-based algorithms, we introduce double-threshold algorithms for both the minimization and maximization variants of this problem. We further show that the competitive ratios achieved by these algorithms are the best achievable by any deterministic online algorithm. Finally, we empirically validate our proposed algorithm through case studies on the application of carbon-aware load shifting using real carbon trace data and existing baseline algorithms.

关键词： online pause and resume carbon-aware load shifting online algorithms switching costs k-search

来源：评论

学校读者我要写书评

暂无评论

Competitive algorithms for the online Multiple Knapsack Problem with Application to Electric Vehicle Charging

引用

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2020年第3期4卷 1–32页

作者： Sun, Bo Zeynali, Ali Li, Tongxin Hajiesmaili, Mohammad Wierman, Adam Tsang, Danny H. K. Hong Kong Univ Sci & Technol Hong Kong Peoples R China Univ Massachusetts Amherst Amherst MA USA CALTECH Pasadena CA 91125 USA

We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging.

关键词： online knapsack problems one-way trading online algorithms electric vehicle charging online primal dual analysis

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for online decision problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2005年第3期71卷 291-307页

作者： Kalai, A Vempala, S Toyota Technol Inst Dept Comp Sci Chicago IL 60637 USA MIT Cambridge MA 02139 USA

In an online decision problem, one makes a sequence of decisions without knowledge of the future. Each period, one pays a cost based on the decision and observed state. We give a simple approach for doing nearly as well as the best single decision, where the best is chosen with the benefit of hindsight. A natural idea is to follow the leader, i.e. each period choose the decision which has done best so far. We show that by slightly perturbing the totals and then choosing the best decision, the expected performance is nearly as good as the best decision in hindsight. Our approach, which is very much like Hannan's original game-theoretic approach from the 1950s, yields guarantees competitive with the more modern exponential weighting algorithms like Weighted Majority. More importantly, these follow-the-leader style algorithms extend naturally to a large class of structured online problems for which the exponential algorithms are inefficient. (c) 2004 Elsevier Inc. All rights reserved.

关键词： online algorithms Hannan's algorithm optimization decision theory

来源：评论

学校读者我要写书评

暂无评论

Robust algorithms for online k-means Clustering 31

Robust Algorithms for Online k-means Clustering

引用

31st International Conference on Algorithmic Learning Theory (ALT)

作者： Bhaskara, Aditya Ruwanpathirana, Aravinda Kanchana Univ Utah Sch Comp Salt Lake City UT 84112 USA

In the online version of the classic k-means clustering problem, the points of a dataset u(1), u(2),... arrive one after another in an arbitrary order. When the algorithm sees a point, it should either add it to the set of centers, or let go of the point. Once added, a center cannot be removed. The goal is to end up with set of roughly k centers, while competing in k-means objective value with the best set of k centers in hindsight. online versions of k-means and other clustering problem have received significant attention in the literature. The key idea in many algorithms is that of adaptive sampling: when a new point arrives, it is added to the set of centers with a probability that depends on the distance to the centers chosen so far. Our contributions are as follows: 1. We give a modified adaptive sampling procedure that obtains a better approximation ratio (improving it from logarithmic to constant). 2. Our main result is to show how to perform adaptive sampling when data has outliers (>> k points that are potentially arbitrarily far from the actual data, thus rendering distance-based sampling prone to picking the outliers). 3. We also discuss lower bounds for k-means clustering in an online setting.

关键词： online algorithms k-means clustering Robust algorithms

来源：评论

学校读者我要写书评

暂无评论

online Live VM Migration algorithms to Minimize Total Migration Time and Downtime 33

Online Live VM Migration Algorithms to Minimize Total Migrat...

引用

33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Tziritas, Nikos Loukopoulos, Thanasis Khan, Samee U. Xu, Cheng-Zhong Zomaya, Albert Y. Shenzhen Inst Adv Technol Cloud Comp Ctr Shenzhen Peoples R China Univ Thessaly Comp Sci & Biomed Informat Lamia Greece North Dakota State Univ Elect & Comp Engin Fargo ND USA Univ Macau Dept Comp & Informat Sci Macau Peoples R China Univ Sydney Sch Informat Technol Sydney NSW Australia

ISBN: (纸本)9781728112466

Virtual machine (VM) migration is a widely used technique in cloud computing systems to increase reliability. There are also many other reasons that a VM is migrated during its lifetime, such as reducing energy consumption, improving performance, maintenance, etc. During a live VM migration, the underlying VM continues being up until all or part of its data has been transmitted from source to destination. The remaining data are transmitted in an off-line manner by suspending the corresponding VM. The longer the off-line transmission time, the worse the performance of the respective VM. The above is because during the off-line data transmission, the VM service is down. Because a running VM's memory is subject to changes, already transmitted data pages may get dirtied and thus needing re-transmission. The decision of when suspending the VM is not a trivial task at all. The above is justified by the fact that when suspending the VM early we may result in transmitting off-line a significant amount of data degrading thus the VM's performance. On the other hand, a long waiting time to suspend the VM may result in re-transmitting a huge amount of dirty data, leading in that way to waste of resources. In this paper, we tackle the joint problem of minimizing both the total VM migration time (reflecting the resources spent during a migration) and the VM downtime (reflecting the performance degradation). The aforementioned objective functions are weighted according to the needs of the underlying cloud provider/user. To tackle the problem, we propose an online deterministic algorithm resulting in an strong competitive ratio, as well as a randomized online algorithm achieving significantly better results against the deterministic algorithm.

关键词： Live VM migration online algorithms

来源：评论

学校读者我要写书评

暂无评论

Preemptive online Scheduling: Optimal algorithms for All Speeds

引用

14th Annual European Symposium on algorithms (ESA 2006)

作者： Ebenlendr, Tomas Jawor, Wojciech Sgall, Jiri Acad Sci Czech Republic Inst Math CR-11567 Prague 1 Czech Republic Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA

ISBN: (纸本)3540388753

Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between 2.054 and e approximate to 2.718. We also give a complete analysis of the competitive ratio for three machines.

关键词： online algorithms Scheduling Makespan

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：