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

online algorithms for Maximum Cardinality Matching with Edge Arrivals

ALGORITHMICA 2019年第5期81卷 1781-1799页

作者： Buchbinder, Niv Segev, Danny Tkach, Yevgeny Tel Aviv Univ Sch Math Sci Dept Stat & Operat Res IL-69978 Tel Aviv Israel Univ Haifa Dept Stat IL-31905 Haifa Israel

In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in an arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1/2-competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5/9-competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2/3+1/Phi(2) approximate to 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, while this result slightly falls short of the currently best 1/1+1n 2 approximate to 0.5906 bound by Epstein et al. (Inf Comput 259(1):31-40, 2018), it holds even for an easier model in which vertices along with their adjacent edges arrive online. As a result, we improve on the currently best upper bound of 0.6252 for the latter model, due to Wang and Wong (in: Proceedings of the 42nd ICALP, 2015).

关键词： Maximum matching online algorithms Competitive analysis Primal-dual method

来源：评论

学校读者我要写书评

暂无评论

online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第2期26卷 223-236页

作者： Zhang, Yong Chin, Francis Y. L. Ting, Hing-Fung Han, Xin Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Dalian Univ Technol Sch Software Dalian Peoples R China

In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P (ij) . When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90(a similar to)-rotation on any plane P (ij) is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 (d) is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 (d+1)-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing.

关键词： online algorithms Bin packing 1-space bounded Multi dimensional

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Information Aggregation From Distributed and Correlated Sources

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2016年第6期24卷 3714-3725页

作者： Chau, Chi-Kin Khonji, Majid Aftab, Muhammad Masdar Inst Sci & Technol Dept Elect Engn & Comp Sci Abu Dhabi U Arab Emirates

There is a fundamental tradeoff between the communication cost and the latency in information aggregation. Aggregating multiple communication messages over time can alleviate overhead and improve energy efficiency on one hand, but inevitably incurs information delay on the other hand. In the presence of uncertain future inputs, this tradeoff should be balanced in an online manner, which is studied by the classical dynamic TCP ACK problem for a single information source. In this paper, we extend dynamic TCP ACK problem to a general setting of collecting aggregate information from distributed and correlated information sources. In this model, distributed sources observe correlated events, whereas only a small number of reports are required from the sources. The sources make online decisions about their reporting operations in a distributed manner without prior knowledge of the local observations at others. Our problem captures a wide range of applications, such as in-situ sensing, anycast acknowledgement, and distributed caching. We present simple threshold-based competitive distributed online algorithms under different settings of intercommunication. Our algorithms match the theoretical lower bounds in order of magnitude. We observe that our algorithms can produce satisfactory performance in simulations and practical test bed.

关键词： online algorithms competitive analysis distributed optimization problem latency communication cost

来源：评论

学校读者我要写书评

暂无评论

online algorithms with discrete visibility - Exploring unknown polygonal environments

引用

IEEE ROBOTICS & AUTOMATION MAGAZINE 2008年第2期15卷 67-76页

作者： Ghosh, Subir Kumar Burdick, Joel Wakeman Bhattacharya, Amitava Sarkar, Sudeep Tata Inst Fundamental Res Sch Comp Sci Bombay 400005 Maharashtra India Univ S Florida Tampa FL USA

The context of this work is the exploration of unknown polygonal environments with obstacles. Both the outer boundary and the boundaries of obstacles are piecewise linear. The boundaries can be nonconvex. The exploration problem can be motivated by the following application. Imagine that a robot has to explore the interior of a collapsed building, which has crumbled due to an earthquake, to search for human survivors. It is clearly impossible to have a knowledge of the building's interior geometry prior to the exploration. Thus, the robot must be able to see, with its onboard vision sensors, all points in the building's interior while following its exploration path. In this way, no potential survivors will be missed by the exploring robot. The exploratory path must clearly reflect the topology of the free space, and, therefore, such exploratory paths can be used to guide future robot excursions (such as would arise in our example from a rescue operation).

关键词： polygon exploration online algorithms point robot competitive ratio art gallery problem discrete visibility visibility polygon

来源：评论

学校读者我要写书评

暂无评论

online algorithms for the Interval Scheduling Problem in the Cloud: Affinity Pair Threshold Based Approaches

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING

引用

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING 2022年第2期7卷 441-455页

作者： Oikonomou, Panagiotis Tziritas, Nikos Loukopoulos, Thanasis Theodoropoulos, Georgios Hanai, Masatoshi Khan, Samee U. Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Guangdong Peoples R China Univ Thessaly Dept Comp Sci & Telecommun Lamia 35131 Greece Univ Thessaly Dept Comp Sci & Biomed Informat Lamia 35131 Greece Mississippi State Univ Dept Elect & Comp Engn Starkville MS 39762 USA

In the interval scheduling problem, jobs have known start and end times (referred to as job intervals) and must be assigned to processing nodes for their whole duration. Although the problem originally stems from the resource allocation demands of resident processes in operating systems, it found a renewed interest in the Cloud context, both in IaaS and SaaS, since reservations for virtual machines and services often have known activation intervals. A common objective of interval scheduling is to minimize busy time of machines which relates (among others) to minimizing the number of machines participating in the computation. As a consequence, bin packing techniques have been applied in the past. In this paper we tackle the online version of the problem, whereby future job arrivals are unknown. We propose novel algorithms that work as a pre-processing step to any bin packing scheme by offering recommendations that are enforced in all packing decisions. Job overlaps are used to characterize pairwise job affinity and subsequently provide threshold based job allocation recommendations. Thresholds are calculated using lower bound theoretical analysis upon two extreme workloads (sparse and dense). Experimental evaluation using real world workloads illustrates the merits of our approach against state-of-the-art algorithms.

关键词： Task analysis Servers Scheduling Resource management Optimal scheduling Energy consumption Computer science Interval scheduling bin packing online algorithms resource allocation

来源：评论

学校读者我要写书评

暂无评论

online algorithms with advice for the dual bin packing problem

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2017年第4期25卷 953-966页

作者： Renault, Marc P. CNRS Paris France Univ Paris Diderot Paris France

This paper studies the problem of maximizing the number of items packed into n bins, known as the dual bin packing problem, in the advice per request model. In general, no online algorithm has a constant competitive ratio for this problem. An online algorithm with 1 bit of advice per request is shown to be 3/2-competitive. Next, for 0 < epsilon < 1/2, an online algorithm with advice that is (1/(1 - epsilon))-competitive and uses bits O(1/epsilon) of advice per request is presented.

关键词： online algorithms online computation with advice Competitive analysis Dual bin packing Multiple knapsack problem

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Dynamic Matching Markets in Power Distribution Systems

引用

IEEE CONTROL SYSTEMS LETTERS 2021年第3期5卷 995-1000页

作者： Muthirayan, Deepan Parvania, Masood Khargonekar, Pramod P. Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92697 USA Univ Utah Dept Elect & Comp Engn Salt Lake City UT 84112 USA

This letter proposes online algorithms for dynamic matching markets in power distribution systems. These algorithms address the problem of matching flexible loads with renewable generation, with the objective of maximizing social welfare of the exchange in the system. More specifically, two online matching algorithms are proposed for two generation-load scenarios: (i) when the mean of renewable generation is greater than the mean of the flexible load, and (ii) when the condition (i) is reversed. With the intuition that the performance of such algorithms degrades with increasing randomness of the supply and demand, two properties are proposed for assessing the performance of the algorithms. First property is convergence to optimality (CO) as the underlying randomness of renewable generation and customer loads goes to zero. The second property is deviation from optimality, which is measured as a function of the standard deviation of the underlying randomness of renewable generation and customer loads. The algorithm proposed for the first scenario is shown to satisfy CO and a deviation from optimality that varies linearly with the variation in the standard deviation. We then show that the algorithm proposed for the second scenario satisfies CO and a deviation from optimality that varies linearly with the variation in standard deviation plus an offset under certain condition.

关键词： online algorithms dynamic matching markets flexible loads power distribution systems

来源：评论

学校读者我要写书评

暂无评论

online algorithms for searching and exploration in the plane

引用

COMPUTER SCIENCE REVIEW 2010年第4期4卷 189-201页

作者： Ghosh, Subir Kumar Klein, Rolf Tata Inst Fundamental Res Sch Comp Sci Bombay 400005 Maharashtra India Univ Bonn Inst Comp Sci 1 D-53117 Bonn Germany

In this paper, we survey online algorithms in computational geometry that have been designed for mobile robots for searching a target and for exploring a region in the plane. (C) 2010 Elsevier Inc. All rights reserved.

关键词： online algorithms Motion planning Competitive ratio Target searching Exploration Approximation algorithms Randomized algorithm Computational geometry Shortest path Minimum link path Visibility polygons Watchman route

来源：评论

学校读者我要写书评

暂无评论

online algorithms: a survey

引用

MATHEMATICAL PROGRAMMING 2003年第1-2期97卷 3-26页

作者： Albers, S Univ Freiburg Inst Informat D-79110 Freiburg Germany

During the last 15 years online algorithms have received considerable research interest. In this survey we give an introduction to the competitive analysis of online algorithms and present important results. We study ... 详细信息

关键词： COMPUTER algorithms algorithms ARITHMETIC -- Foundations ALGEBRA online algorithms online data processing

来源：评论

学校读者我要写书评

暂无评论

online algorithms FOR NONNEGATIVE MATRIX FACTORIZATION WITH THE ITAKURA-SAITO DIVERGENCE

ONLINE ALGORITHMS FOR NONNEGATIVE MATRIX FACTORIZATION WITH ...

引用

IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA)

作者： Lefevre, Augustin Bach, Francis Fevotte, Cedric INRIA ENS Sierra Team 23 Ave Italie F-75013 Paris France CNRS LTCI Telecom Paris Tech F-75014 Paris France

ISBN: (纸本)9781457706936

Nonnegative matrix factorization (NMF) is now a common tool for audio source separation. When learning NMF on large audio databases, one major drawback is that the complexity in time is O(F K N) when updating the dictionary (where (F, N) is the dimension of the input power spectrograms, and K the number of basis spectra), thus forbidding its application on signals longer than an hour. We provide an online algorithm with a complexity of O(F K) in time and memory for updates in the dictionary. We show on audio simulations that the online approach is faster for short audio signals and allows to analyze audio signals of several hours.

关键词： nonnegative matrix factorization online algorithms Itakura-Saito divergence blind source separation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：