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

online algorithms for page replication in rings

THEORETICAL COMPUTER SCIENCE 2001年第1期268卷 107-117页

作者： Glazek, W Gdansk Tech Univ Fdn Informat Dept PL-80952 Gdansk Poland

In the page replication problem for a distributed shared memory system one has to decide which subset of the processors should hold each read-only page in order to ensure low total access cost. Albers and Koga (J. algorithms 27 (1998) 75-96) studied the problem in rings with arbitrary node distances and showed a 4-competitive deterministic online algorithm and 2e/(e - 1) approximate to 3.16396-competitive randomized online algorithm against an oblivious adversary. In this paper we give new online algorithms for the page replication problem in equally spaced rings. We present a deterministic algorithm which is 3-competitive and a randomized algorithm which for sufficiently large page sizes attains a competitive ratio of roote/(roote - I) approximate to 2.5415 against an oblivious adversary. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： analysis of algorithms online algorithms competitive analysis memory management

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Prize-Collecting Optimization Problems 23rd

Online Algorithms for Prize-Collecting Optimization Problems

引用

23rd International Conference on Enterprise Information Systems (ICEIS)

作者： Markarian, Christine El-Kassar, Abdul Nasser Univ Dubai Dept Engn & Informat Technol Dubai U Arab Emirates Lebanese Amer Univ Dept Informat Technol & Operat Management Beirut Lebanon

ISBN: (纸本)9783031089657;9783031089640

Many real-world optimization problems are online by nature, requiring provably-good decisions that need to be made in the present without knowing the future. At the heart of such decisions are online algorithms. The input to an online algorithm is not given all at once but arrives in portions over time. The online algorithm reacts to each arriving portion while targeting the optimization objective against the entire input. In this paper, we consider a well-established branch of online optimization problems in which some input portions can be rejected by paying an associated penalty and these penalties are incorporated into the objective function. We study the online prize-collecting variants of three well-known optimization problems: Connected Dominating Set, Vertex Cover, and Non-metric Facility Location, and propose online algorithms for these variants, measured using the competitive analysis framework. The latter compares, in the worst case, the performance of the online algorithm to the optimal offline solution constructed given all the input sequence at once. Furthermore, we extend the study of prize-collecting optimizations problems to the leasing setting in which resources are leased, rather than bought, for different durations and prices.

关键词： Optimization online algorithms Competitive analysis Prize-collecting Penalties Facility location Vertex cover Connected dominating set Leasing

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints

Online Algorithms for Maximizing Weighted Throughput of Unit...

引用

Joint 5th International Frontiers in Algorithmics Workshop (FAW) / 7th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Birks, Martin Cole, Daniel Fung, Stanley P. Y. Xue, Huichao Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England Univ Pittsburgh Dept Comp Sci Pittsburgh PA 15260 USA

ISBN: (纸本)9783642212048

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We give an optimal randomized algorithm and another resource-augmented constant-competitive randomized algorithm for the problem. We also give almost tight upper and lower bounds for the multiple processor case.

关键词： online algorithms scheduling competitive analysis temperature resource augmentation

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Optimal Resource Management in Dynamic D2D Communications 10

Online Algorithms for Optimal Resource Management in Dynamic...

引用

10th International Conference on Mobile Ad-hoc and Sensor Networks MSN

作者： Kuhnle, Alan Li, Xiang Thai, My T. Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

ISBN: (纸本)9781479973941

Device-to-device (D2D) communications has recently emerged as a promising technology for boosting the capacity of cellular systems. D2D enables direct communication between mobile devices over the cellular band without utilizing infrastructure nodes such as base stations, thereby reducing the load on cellular base stations and increasing network throughput through spatial reuse of radio resources. Hence it is important to optimally allocate these radio resources. Furthermore, since the composition of a cellular macrocell is highly dynamic, it is critical to adaptively update the resource allocation for D2D communications rather than recomputing it from scratch. In this work, we develop the first online algorithm, namely ODSRA, for dynamic resource allocation while maximizing spatial reuse. At the core of the resource allocation problem is the online set multicover problem, for which we present the first deterministic O (log n log m)-competitive online algorithm, where n is the number of elements, and m the number of sets. By simulation, we show the efficacy of ODSRA by analyzing network throughput and other metrics, obtaining a large improvement in running time over offline methods.

关键词： D2D communications online algorithms resource allocation spatial reuse

来源：评论

学校读者我要写书评

暂无评论

Comparing online algorithms for bin packing problems

引用

JOURNAL OF SCHEDULING 2012年第1期15卷 13-21页

作者： Epstein, Leah Favrholdt, Lene M. Kohrt, Jens S. Univ Haifa Dept Math IL-31999 Haifa Israel Univ So Denmark Dept Math & Comp Sci Odense Denmark

The relative worst-order ratio is a measure of the quality of online algorithms. In contrast to the competitive ratio, this measure compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm. In this paper, we apply the relative worst-order ratio to online algorithms for several common variants of the bin packing problem. We mainly consider pairs of algorithms that are not distinguished by the competitive ratio and show that the relative worst-order ratio prefers the intuitively better algorithm of each pair.

关键词： online algorithms Relative worst-order ratio Bin packing Bin covering Bin coloring Class-constrained bin packing Open-end bin packing

来源：评论

学校读者我要写书评

暂无评论

online algorithms on Antipowers and Antiperiods 26th

Online Algorithms on Antipowers and Antiperiods

引用

26th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Alzamel, Mai Conte, Alessio Greco, Daniele Guerrini, Veronica Iliopoulos, Costas Pisanti, Nadia Prezza, Nicola Punzi, Giulia Rosone, Giovanna Univ Pisa Dept Comp Sci Pisa Italy Kings Coll London Dept Informat London England King Saud Univ Dept Comp Sci Riyadh Saudi Arabia

ISBN: (纸本)9783030326852;9783030326869

The definition of antipower introduced by Fici et al. (ICALP 2016) captures the notion of being the opposite of a power: a sequence of k pairwise distinct blocks of the same length. Recently, Alamro et al. (CPM 2019) defined a string to have an antiperiod if it is a prefix of an antipower, and gave complexity bounds for the offline computation of the minimum antiperiod and all the antiperiods of a word. In this paper, we address the same problems in the online setting. Our solutions rely on new arrays that compactly and incrementally store antiperiods and antipowers as the word grows, obtaining in the process this information for all the word's prefixes. We show how to compute those arrays online in O(n log n) space, O(n log n) time, and o(n(epsilon)) delay per character, for any constant epsilon > 0. Running times are worst-case and hold with high probability. We also discuss more space-efficient solutions returning the correct result with high probability, and small data structures to support random access to those arrays.

关键词： Antiperiod Antipower Power Periodicity Repetition Regularities online algorithms

来源：评论

学校读者我要写书评

暂无评论

online algorithms with Learned Predictions

Online Algorithms with Learned Predictions

引用

作者： Anand, Keerti Duke University

学位级别：Ph.D., Doctor of Philosophy

Optimization under uncertainty is a classic theme in the fields of algorithm design and machine learning. The traditional design of online algorithms have however proved to be insufficient for practical instances, since it only tries to optimize for the worst-case (but possibly highly unlikely) future scenarios. The availability of data and the advent of powerful machine learning paradigms has led to a promising approach of leveraging predictions about the future to aid in making decisions under uncertainty. This motivates us to explore whether algorithm design can go beyond the worst-case, i.e., is it possible to design efficient algorithms that perform well for the typical instances, while retaining a suitable robustness guarantee for the worst-case instance? This entails our vision of combining the power of Machine Learning and Algorithm design to get the best of both worlds. This can be categorized into two inter-dependent parts : (1) How to design the prediction pipeline to generate forecasts about the future unknowns and (2) Given such predictions, how to re-design the decision-making algorithm to best leverage them. In this thesis, we investigate both of these questions, and summarize the key contributions as follows: Rent or Buy Problem: We investigate the rent-or-buy problem and design a simple online algorithm that leverages predictions from classification black-box model whose performance is directly dependent on the prediction error of the classification task. We then demonstrate that by incorporating the optimization benchmarks in prediction model leads to significantly better performance, while maintaining a worst-case adversarial result. online Search: We define a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We then model the task of making predictions as a regression problem and show nearly tight bounds on the sample complexity of this regression problem.

关键词： online algorithms Learned predictions Machine Learning

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Leasing Vertex Cover and Leasing Non-metric Facility Location 8th

Online Algorithms for Leasing Vertex Cover and Leasing Non-m...

引用

8th International Conference on Operations Research and Enterprise Systems (ICORES)

作者： Markarian, Christine der Heide, Friedhelm Meyer auf Haigazian Univ Dept Math Sci Beirut Lebanon Univ Paderborn Heinz Nixdorf Inst Paderborn Germany

ISBN: (纸本)9789897583520

We consider leasing variants of two classical NP-hard optimization problems, Vertex Cover (VC) and nonmetric Facility Location (non-metric FL). These contain the well-known Parking Permit problem due to Meyerson [ROCS 2005] as a special sub-case and can be found as sub-problems in many operations research applications. We give the first online algorithms for these two problems, evaluated using the standard notion of competitive analysis in which the online algorithm whose input instance is revealed over time is compared to the optimal offline algorithm which knows the entire input sequence in advance and is optimal. Our algorithms have optimal and near-optimal competitive ratios for the leasing variants of VC and non-metric FL, respectively.

关键词： online algorithms Competitive Analysis Leasing Parking Permit Problem Randomized Rounding Primal-Dual algorithms Operations Research Resource Allocation

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Spectral Hypergraph Sparsification 25th

Online Algorithms for Spectral Hypergraph Sparsification

引用

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Soma, Tasuku Tung, Kam Chuen Yoshida, Yuichi Inst Stat Math Tokyo Japan Univ Waterloo Waterloo ON Canada Natl Inst Informat Tokyo Japan

ISBN: (纸本)9783031598340;9783031598357

We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (epsilon, delta)-spectral sparsifier with multiplicative error e and additive error delta that has O(epsilon(-2) n log n log r log(1+ epsilon W/delta n)) hyperedges with high probability, where epsilon, delta is an element of (0, 1), n is the number of nodes, r is the rank of the hypergraph, and W is the sum of edge weights. The space complexity of our algorithm is O(n(2)), while previous algorithms required space complexity Omega(m), where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.

关键词： online algorithms Hypergraph Sparsification Spectral algorithms Generic Chaining

来源：评论

学校读者我要写书评

暂无评论

Colored Bin Packing: online algorithms and Lower Bounds

引用

ALGORITHMICA 2018年第1期80卷 155-184页

作者： Bohm, Martin Dosa, Gyorgy Epstein, Leah Sgall, Jiri Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague Czech Republic Univ Pannonia Dept Math Veszprem Hungary Univ Haifa Dept Math Haifa Israel

In the Colored Bin Packing problem a sequence of items of sizes up to 1 arrives to be packed into bins of unit capacity. Each item has one of at least two colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins. In the important special case when all items have size zero, we characterize the optimal value to be equal to color discrepancy. As our main result, we give an (asymptotically) 1.5-competitive algorithm which is optimal. In fact, the algorithm always uses at most bins and we can force any deterministic online algorithm to use at least bins while the offline optimum is for any value of . In particular, the absolute competitive ratio of our algorithm is 5 / 3 and this is optimal. For items of arbitrary size we give a lower bound of 2.5 on the asymptotic competitive ratio of any online algorithm and an absolutely 3.5-competitive algorithm. When the items have sizes of at most 1 / d for a real the asymptotic competitive ratio of our algorithm is . We also show that classical algorithms First Fit, Best Fit and Worst Fit are not constant competitive, which holds already for three colors and small items. In the case of two colors-the Black and White Bin Packing problem-we give a lower bound of 2 on the asymptotic competitive ratio of any online algorithm when items have arbitrary size. We also prove that all Any Fit algorithms have the absolute competitive ratio 3. When the items have sizes of at most 1 / d for a real we show that the Worst Fit algorithm is absolutely -competitive.

关键词： online algorithms Bin packing Worst-case analysis Colored bin packing Black and white bin packing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：