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

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

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Matching Platforms with Multi-Channel Traffic 22

Online Algorithms for Matching Platforms with Multi-Channel ...

引用

Proceedings of the 23rd ACM Conference on Economics and Computation

作者： Vahideh Manshadi Scott Rodilitz Daniela Saban Akshaya Suresh Yale School of Management New Haven CT USA UCLA Anderson School of Management Los Angeles CA USA Stanford Graduate School of Business Stanford CA USA

ISBN: (纸本)9781450391504

Two-sided platforms rely on their recommendation algorithms to help their visitors successfully find a match. However, on platforms such as VolunteerMatch - which has facilitated tens of millions of connections between volunteers and nonprofits - a sizable fraction of website traffic arrives directly to a nonprofit's volunteering page via an external link, thus bypassing the platform's recommendation algorithm. We study how such platforms should account for this external traffic in the design of their recommendation engines, given the goal of maximizing the total number of successful matches. We model the platform's problem as a special case of online matching with stochastic rewards, where (using VolunteerMatch as a motivating example) volunteers arrive sequentially and (probabilistically) match with one opportunity, each of which has finite need for volunteers. In our framework, external traffic is interested only in their targeted opportunity; in contrast, internal traffic may be interested in many opportunities, and the platform's online algorithm selects which opportunity to recommend. In evaluating the performance of different algorithms, we take a worst-case analysis approach, yet we refine the notion of the competitive ratio by parameterizing it based on the amount of external traffic. After demonstrating the shortcomings of a commonly-used algorithm which is optimal in the absence of external traffic, we introduce a new algorithm - Adaptive Capacity (AC) - which accounts for matches differently based on whether they originate from internal or external traffic. We establish a lower bound on AC's competitive ratio that is increasing in the amount of external traffic, and we compare our lower bound to a parameterized upper bound on the competitive ratio of any online algorithm. We find that (in certain parameter regimes) AC is near-optimal regardless of the amount of external traffic, even though it does not know this amount a priori. Our analysis utilizes a p

关键词： competitive analysis multi-channel traffic matching platforms online algorithms

来源：评论

学校读者我要写书评

暂无评论

online algorithms of Task Allocation in Spatial Crowdsourcing 17

Online Algorithms of Task Allocation in Spatial Crowdsourcin...

引用

12th Chinese Conference on Computer Supported Cooperative Work and Social Computing (ChineseCSCW)

作者： Sun, Yong Wang, Jun Tan, Wenan Chuzhou Univ 1 Huifeng St Chuzhou 239000 Peoples R China Nanjing Univ Aeronaut & Astronaut 29 Yudao St Nanjing 210016 Jiangsu Peoples R China

ISBN: (纸本)9781450353526

Recently, spatial collaborations and crowdsourcing has emerged as a novel typical pattern for applying to a range of problems. A key problem of spatial collaboration is to allocate suitable workers to nearby tasks in a real-time online way. Traditional crowdsourcing algorithms always consider the quality of worker with prior knowledge. However, in online crowdsourcing context, the quality of crowd-workers is unknown and uncertain. It is so hard for such task crowdsourcing process in an inherently online and dynamic environment. To solve this spatial crowdsourcing problem, the branch-and-bound R-tree data structure is employed in our algorithms to prune the search tree of the nearby crowd-workers. Furthermore, we introduce a new online algorithm to deal with the uncertain crowdsourcing problems. Theoretical analysis and extensive experiments are conducted for validation purpose;and the experimental results show that our algorithms outperform several existing algorithms in terms of computation time in dealing with the increasing number of crowdsourcing task executing candidates.

关键词： Spatial crowdsourcing task allocation online algorithms collaborative computing

来源：评论

学校读者我要写书评

暂无评论

Alternative Measures for the Analysis of online algorithms

Alternative Measures for the Analysis of Online Algorithms

引用

作者： Dorrigiv, Reza University of Waterloo

学位级别：master

In this thesis we introduce and evaluate several new models for the analysis of online algorithms. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as paging and routing are intrinsically online and thus the design and analysis ofonline algorithms is one of the main research areas in theoretical computer *** analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. While in several instances competitive analysis gives satisfactory results, for certain problems it results in unrealistically pessimistic ratios and/orfails to distinguish between algorithms that have vastly differing performance under any practical characterization. Addressing these shortcomings has been the subject of intense research by many of the best minds in the field. In this thesis, building upon recent advances of others we introduce some new models for analysis of online algorithms, namely Bijective Analysis, Average Analysis,Parameterized Analysis, and Relative Interval Analysis. We show that they lead to good results when applied to paging and list update algorithms. Paging and list update are two well known online problems. Paging is one of the main examples of poor behavior of competitive analysis. We show that LRU is the unique optimal online paging algorithm according to Average Analysis on sequences with locality of reference. Recall that in practice input sequences for paging havehigh locality of reference. It has been empirically long established that LRU is the best paging algorithm. Yet, Average Analysis is the first model that gives strict separation of LRU from all other

关键词： Analysis of algorithms online algorithms Paging List Update Adaptive Analysis Data Compression

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Multi-shop Ski Rental with Machine Learned Predictions 20

Online Algorithms for Multi-shop Ski Rental with Machine Lea...

引用

Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems

作者： Shufan Wang Jian Li Binghamton University the State University of New York Binghamton NY USA Binghamton University the State University of New York Binghamton NY USA

ISBN: (纸本)9781450375184

Uncertainty plays a critical role in many real world applications where the decision maker is faced with multiple alternatives with different costs. These decisions arise in our daily lives, such as whether to rent an apartment or buy a house, which cannot be answered reliably without knowledge of the future. These decisionmaking problems are usually modeled as online rent-or-buy problems, such as the classical ski rental problem [4, 5, 8]. Two paradigms have been widely studied to deal with such uncertainty. On the one hand, online algorithms are designed without prior knowledge to the problem, and competitive ratio (CR) is used to characterize the goodness of the algorithm in lack of the future. On the other hand, machine learning is applied to address uncertainty by making future predictions via building robust models on prior data.

关键词： consistency competitive analysis robustness online algorithms machine learned prediction

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for multidimensional packing problems

引用

SIAM JOURNAL ON COMPUTING 2005年第2期35卷 431-448页

作者： Epstein, L Van Stee, R Univ Haifa Dept Math IL-31905 Haifa Israel Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany

We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension d > 1. Its asymptotic performance ratio is (Pi(infinity))(d), where Pi(infinity) approximate to 1.691 is the asymptotic performance ratio of the one-dimensional algorithm Harmonic. A modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d. Furthermore, we extend the techniques used in these algorithms to give optimal algorithms for online bounded space variable-sized packing and resource augmented packing.

关键词： multidimensional bin packing online algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

RANDOM-WALKS ON WEIGHTED GRAPHS AND APPLICATIONS TO online algorithms

引用

JOURNAL OF THE ACM 1993年第3期40卷 421-453页

作者： COPPERSMITH, D DOYLE, P RAGHAVAN, P SNIR, M AT&T BELL LABS MURRAY HILLNJ 07974

The design and analysis of randomized on-line algorithms are studied. This problem is shown to be closely related to the synthesis of random walks on graphs with positive real costs on their edges. A theory is develop... 详细信息

关键词： algorithms THEORY METRICAL TASKS online algorithms RANDOM WALKS SERVER PROBLEM

来源：评论

学校读者我要写书评

暂无评论

Randomized distributed online algorithms against adaptive offline adversaries

引用

INFORMATION PROCESSING LETTERS 2020年 161卷 105973-105973页

作者： Boyar, Joan Ellen, Faith Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark Univ Toronto Dept Comp Sci 10 Kings Coll Rd Toronto ON M5S 3G4 Canada

In the sequential setting, a decades-old fundamental result in online algorithms states that if there is a c-competitive randomized online algorithm against an adaptive, offline adversary, then there is a c-competitive deterministic algorithm. The adaptive, offline adversary is the strongest adversary among the ones usually considered, so the result states that if one has to be competitive against such a strong adversary, then randomization does not help. This implies that researchers do not consider randomization against an adaptive, offline adversary. We prove that in a distributed setting, this result does not necessarily hold, so randomization against an adaptive, offline adversary becomes interesting again. (C) 2020 Elsevier B.V. All rights reserved.

关键词： online algorithms Randomized algorithms Adaptive offline adversary Distributed systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：