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

31st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Komm, Dennis Kralovic, Rastislav Kralovic, Richard Moemke, Tobias Swiss Fed Inst Technol Zurich Switzerland Comenius Univ Bratislava Slovakia Google Inc Zurich Switzerland Saarland Univ Saarbrucken Germany

ISBN: (纸本)9783939897651

We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we define a broad class of online problems that includes some of the well-studied problems like paging, k-server and metrical task systems on finite metrics, and show that for these problems it is possible to obtain, given an algorithm with constant expected competitive ratio, another algorithm that achieves the same solution quality up to an arbitrarily small constant error with high probability;the "high probability" statement is in terms of the optimal cost. Furthermore, we show that our assumptions are tight in the sense that removing any of them allows for a counter-example to the theorem.

关键词： online algorithms Randomization High Probability

来源：评论

学校读者我要写书评

暂无评论

Selling Ad Campaigns: online algorithms with Cancellations 09

Selling Ad Campaigns: Online Algorithms with Cancellations

引用

10th ACM Conference on Electronic Commerce (EC-2009)

作者： Babaioff, Moshe Hartline, Jason D. Kleinberg, Robert D. Microsoft Res Mountain View CA 94043 USA

ISBN: (纸本)9781605584584

We study online pricing problems in markets with cancellations, i.e., markets in which prior allocation decisions can be revoked, but at a cost. In our model, a seller receives requests online and chooses which requests to accept, subject to constraints on the subsets of requests which may be accepted simultaneously. A request, once accepted, can be canceled at a cost which is a fixed fraction of the request value. This scenario models a market for web advertising campaigns, in which the buyback cost represents the cost of canceling an existing contract. We analyze a simple constant-competitive algorithm for a single-item auction in this model, and we prove that its competitive ratio is optimal among deterministic algorithms, but that the competitive ratio can be improved using a randomized algorithm. We then model ad campaigns using knapsack domains, in which the requests differ in size as well as in value. We give a deterministic online algorithm that achieves a bi-criterion approximation in which both approximation factors approach 1 as the buyback factor and the size of the maximum request approach 0. We show that the bi-criterion approximation is unavoidable for deterministic algorithms, but that a randomized algorithm is capable of achieving a constant competitive ratio. Finally, we discuss an extension of our randomized algorithm to matroid domains (in which the sets of simultaneously satisfiable requests constitute the independent sets of a matroid) as well as present results for domains in which the buyback factor of different requests varies.

关键词： Selling Advertisements online algorithms Costly Decision Revocation Knapsack Matroids

来源：评论

学校读者我要写书评

暂无评论

On online algorithms with Advice for the k-Server Problem

On Online Algorithms with Advice for the <i>k</i>-Server Pro...

引用

9th International Workshop on Approximation and online algorithms (WAOA 2011)

作者： Renault, Marc P. Rosen, Adi Univ Paris 07 LIAFA Paris France UPMC Paris France CNRS Paris France Univ Paris 07 Paris France

ISBN: (纸本)9783642291159

We consider the model of online computation with advice (Emek et al., Theor. Comput. Sci. 412(24): 2642-2656, 2011). In particular, we study the k-server problem under this model. We prove three upper bounds for this problem. First, we show a -competitive online algorithm for general metric spaces with b bits of advice per request, where 3a parts per thousand currency signba parts per thousand currency signlogk. This improves upon the result of Bockenhauer et al. (ICALP (1), Lecture Notes in Computer Science, vol. 6755, pp. 207-218, 2011). Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of Bockenhauer et al. Second, we give a 1-competitive online algorithm for finite trees which uses 2+2aOElog(p+1)aOE parts per thousand bits of advice per request, where p is the caterpillar dimension of the tree. Lastly, we present a variant of the algorithm for the tree that is optimal for the line with 1-bit of advice.

关键词： online computation with advice k-server problem online algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Robust online algorithms for Dynamic Choosing Problems 1

引用

17th Conference on Computability in Europe (CiE)

作者： Berndt, Sebastian Grage, Kilian Jansen, Klaus Johannsen, Lukas Kosche, Maria Univ Lubeck D-23562 Lubeck Germany Univ Kiel D-24118 Kiel Germany Gottingen Univ D-37073 Gottingen Germany

ISBN: (数字)9783030800499

ISBN: (纸本)9783030800499;9783030800482

Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous works focused on minimization problems that aim to minimize some costs. In this work, we study maximization problems that aim to maximize their profit. We mostly focus on a class of problems that we call choosing problems, where a maximum profit subset of a set objects has to be maintained. Many known problems, such as KNAPSACK, MAXIMUMINDEPENDENTSET and variations of these, are part of this class. We present a framework for choosing problems that allows us to transfer offline ca-approximation algorithms into (alpha - epsilon)-competitive semi-online algorithms with amortized migration O(1/epsilon). Moreover we complement these positive results with lower bounds that show that our results are tight in the sense that no amortized migration of o(1/epsilon) is possible.

关键词： online algorithms Dynamic algorithms Competitive ratio Migration Knapsack Maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Parallel online algorithms for the Bin Packing Problem 1

引用

17th International Workshop on Approximation and online algorithms (WAOA)

作者： Fekete, Sandor P. Grosse-Holz, Jonas Keldenich, Phillip Schmidt, Arne TU Braunschweig Dept Comp Sci Braunschweig Germany

ISBN: (数字)9783030394790

ISBN: (纸本)9783030394790;9783030394783

We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization;they are also related to optimization with advice on future events, i.e., a number of bits available in advance. We develop PREDICTIVE HARMONIC 3 (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that k = 6 suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm ADVANCED HARMONIC, while k = 11 suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits.

关键词： online algorithms Bin packing Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Sharing-Aware online algorithms for Virtual Machine Packing in Cloud Environments 8

Sharing-Aware Online Algorithms for Virtual Machine Packing ...

引用

IEEE 8th International Conference on Cloud Computing

作者： Rampersaud, Safraz Grosu, Daniel Wayne State Univ Dept Comp Sci Detroit MI 48202 USA

ISBN: (纸本)9781467372879

Cloud service providers offer services to a large number of users by employing virtualization technologies. One of the challenges faced by the cloud providers using virtualized environments is the development of efficient algorithms for assigning Virtual Machine (VM) instances to servers such that the number of hosting servers is minimized. This is also known as the problem of VM Packing. In this paper, we design a family of sharing-aware online algorithms for solving the VM Packing problem that take into account the sharing of memory among collocated VMs. We introduce a new server resource scarcity metric which establishes an order among servers that are suitable for hosting an arriving VM request and use it in the design of the algorithms. We evaluate the performance of our sharing-aware online algorithms by performing an extensive set of experiments comparing them against several existing sharing-oblivious VM packing algorithms.

关键词： online algorithms sharing-aware VM packing vector bin packing virtual machines

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds on the Performance of online algorithms for Relaxed Packing Problems 33rd

Lower Bounds on the Performance of Online Algorithms for Rel...

引用

33rd International Workshop on Combinatorial algorithms (IWOCA)

作者： Balogh, Janos Dosa, Gyorgy Epstein, Leah Jez, Lukasz Univ Szeged Inst Informat Szeged Hungary Univ Pannonia Dept Math Veszprem Hungary Univ Haifa Dept Math Haifa Israel Univ Wroclaw Inst Comp Sci Wroclaw Poland

ISBN: (纸本)9783031066788;9783031066771

We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minimum peak appointment scheduling problem. The high level objective in both problems is to pack arriving items of sizes at most 1 into bins of capacity 1 as efficiently as possible, but the exact formalizations differ. In the appointment scheduling problem, every item has to be assigned to a position, which can be seen as a time interval during a workday of length 1. That is, items are not assigned to bins, but only once all the items are processed, the optimal number of bins subject to chosen positions is determined, and this is the cost of the online algorithm. On the other hand, in the removable knapsack problem there is a fixed number of bins, and the goal of packing items, which consists in choosing a particular bin for every packed item (and nothing else), is to pack as valuable a subset as possible. In this last problem it is possible to reject items, that is, deliberately not pack them, as well as to remove packed items at any later point in time, which adds flexibility to the problem.

关键词： Bin packing online algorithms Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Multiple Choice online algorithms for Technology-Assisted Reviews 23

Multiple Choice Online Algorithms for Technology-Assisted Re...

引用

38th Annual ACM Symposium on Applied Computing (ACM SAC)

作者： Piramuthu, Otto B. UIUC Comp Sci Urbana IL 61801 USA

ISBN: (纸本)9781450395175

Exhaustive manual review of documents to determine their relevancy for a given purpose is error-prone and resource intensive. This has led to the consideration of computer-aided processes where only a small subset of the entire set of documents is manually reviewed with comparable performance as exhaustive manual review, resulting in the reduction of human-introduced error and allocated resources. As more evidence for the superiority of Technology-Assisted Reviews (TAR) becomes available, researchers and practitioners have resorted to the exploration of various methods to improve process efficiency without significant degradation in output quality. Of particular interest in this process is the decision on when to stop reviewing additional documents. We consider and evaluate online algorithms, specifically a solution to the multiple choice secretary problem, which is a natural fit for this purpose. Unlike in extant TAR methods, only the relative ranking among the documents that have already been retrieved is needed for this algorithm. Our results indicate that online algorithms are a competitive choice for TAR applications.

关键词： multiple choice secretary problems online algorithms stopping criteria technology assisted reviews

来源：评论

学校读者我要写书评

暂无评论

online algorithms with Advice: A Survey

引用

ACM COMPUTING SURVEYS 2017年第2期50卷 19-19页

作者： Boyar, Joan Favrholdt, Lene M. Kudahl, Christian Larsen, Kim S. Mikkelsen, Jesper W. Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark

In online scenarios requests arrive over time, and each request must be serviced in an irrevocable manner before the next request arrives. online algorithms with advice is an area of research where one attempts to measure how much knowledge of future requests is necessary to achieve a given performance level, as defined by the competitive ratio. When this knowledge, the advice, is obtainable, this leads to practical algorithms, called semi-online algorithms. On the other hand, each negative result gives robust results about the limitations of a broad range of semi-online algorithms. This survey explains the models for online algorithms with advice, motivates the study in general, presents some examples of the work that has been carried out, and includes an extensive set of references, organized by problem studied.

关键词： online algorithms advice complexity competitive analysis approximation

来源：评论

学校读者我要写书评

暂无评论

Robust online algorithms for Certain Dynamic Packing Problems 1

引用

17th International Workshop on Approximation and online algorithms (WAOA)

作者： Berndt, Sebastian Dreismann, Valentin Grage, Kilian Jansen, Klaus Knof, Ingmar Univ Kiel Dept Comp Sci Kiel Germany Univ Warwick Coventry W Midlands England

ISBN: (数字)9783030394790

ISBN: (纸本)9783030394790;9783030394783

online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for dynamic problems, where objects can also depart from the instance. In this work, we give a general framework to obtain so called robust online algorithms for a variety of dynamic problems: these online algorithms achieve an asymptotic competitive ratio of gamma + epsilon with migration O(1/epsilon), where gamma is the best known offline asymptotic approximation ratio. For our framework, we require only two ingredients: (i) the existence of an online algorithm for the static case (without departures) that provides a provably good solution compared to the total volume of the instance and (ii) that the optimal solution always exceeds this total volume. If these criteria are met, we can complement the online algorithm with any offline algorithm. While these criteria are naturally fulfilled by many dynamic problems, they are especially suited for packing problems. In order to show the usefulness of our approach in this area, we improve upon the best known robust algorithms for the dynamic versions of generalizations of Strip Packing and Bin Packing, including the first robust algorithms for general d-dimensional Bin Packing and Vector Packing.

关键词： online algorithms Dynamic algorithms Competitive ratio Recourse Packing problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：