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

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

来源：评论

学校读者我要写书评

暂无评论

Revisiting online algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis

引用

IEEE ACCESS 2024年 12卷 174723-174739页

作者： Markarian, Christine Fachkha, Claude Yassine, Noura Univ Dubai Coll Engn & Informat Technol Dubai U Arab Emirates Beirut Arab Univ Fac Sci Math & Comp Sci Dept Beirut 11502 Lebanon

online algorithms are crucial for real-time decision-making and adaptability across diverse fields, such as operations research, computer science, and combinatorics. These algorithms handle data incrementally and make decisions without prior knowledge of future inputs, thereby effectively addressing complex challenges. This study provides a comprehensive survey of online algorithms, focusing on the Set Cover problem (SC). SC is one of the most extensively studied NP-complete problems, contributing significantly to advancements in approximation techniques, complexity theory, and online algorithms research. It involves selecting a minimal-weight subset from a collection of subsets to cover all elements. This survey examines online algorithms for Set Cover in multiple contexts, including competitive analysis, stochastic models, advice complexity, predictive algorithms, and recourse strategies. While competitive analysis, which compares online algorithms to the best possible offline solutions, remains a key evaluation method, this paper aims to extend the understanding beyond traditional worst-case scenarios. By providing in-depth insights into algorithm design, analytical methods, and practical applications, it seeks to advance the field and stimulate further research in evolving contexts. Additionally, it underscores the intersection of online algorithms with broader domains such as machine learning and predictive analytics, establishing new benchmarks for exploring their broader implications.

关键词： Approximation algorithms Prediction algorithms Stochastic processes Complexity theory Surveys Predictive models Costs Urban areas Real-time systems Probabilistic logic Set cover online algorithms competitive analysis stochastic model advice complexity algorithms with predictions algorithms with recourse

来源：评论

学校读者我要写书评

暂无评论

Improved online algorithms for the Sorting Buffer Problem on Line Metrics

引用

ACM TRANSACTIONS ON algorithms 2009年第1期6卷 15-15页

作者： Gamzu, Iftah Segev, Danny Tel Aviv Univ Sch Comp Sci Tel Aviv Israel MIT Sloan Sch Management Cambridge MA 02139 USA

An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric space;whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server. In this article, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced line metric or a continuous line metric. Our main findings can be briefly summarized as follows. (1) We present a deterministic O(log n)-competitive algorithm for n-point evenly-spaced line metrics. This result improves on a randomized O(log(2) n)-competitive algorithm due to Khandekar and Pandit [2006b]. It also refutes their conjecture, stating that a deterministic strategy is unlikely to obtain a nontrivial competitive ratio. (2) We devise a deterministic O(log N log log N)-competitive algorithm for continuous line metrics, where N denotes the length of the input sequence. In this context, we introduce a novel discretization technique of independent interest. (3) We establish the first nontrivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least 2+root 3/root 3 approximate to 2.154. This result settles, to some extent, an open question due to Khandekar and Pandit [2006b], who posed the task of attaining lower bounds on the achievable competitive ratio as a foundational objective for future research.

关键词： Disk scheduling line metrics online algorithms sorting buffer

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Reasoning about online algorithms with Weighted Automata

引用

ACM TRANSACTIONS ON algorithms 2010年第2期6卷 1–36页

作者： Aminof, Benjamin Kupferman, Orna Lampert, Robby Hebrew Univ Jerusalem Sch Engn & Comp Sci IL-91904 Jerusalem Israel

We describe an automata-theoretic approach for the competitive analysis of online algorithms. Our approach is based on weighted automata, which assign to each input word a cost in R->= 0. By relating the "unbounded look ahead" of optimal offline algorithms with nondeterminism, and relating the "no look ahead" of online algorithms with determinism, we are able to solve problems about the competitive ratio of online algorithms, and the memory they require, by reducing them to questions about determinization and approximated determinization of weighted automata.

关键词： algorithms Theory Verification Formal verification weighted automata online algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：