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

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

作者： Brodal, Gerth Stolting Moruz, Gabriel Negoescu, Andrei Aarhus Univ Dept Comp Sci MADALGO Ctr Mass Data Algorithm DK-8200 Aarhus N Denmark Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

ISBN: (纸本)9783642291159

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k (2)) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.

关键词： On-line algorithms Competitive analysis Paging randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Neighbor Discovery in Wireless Networks with Multipacket Reception

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2015年第7期26卷 1984-1998页

作者： Russell, Alexander Vasudevan, Sudarshan Wang, Bing Zeng, Wei Chen, Xian Wei, Wei Univ Connecticut Comp Sci & Engn Dept Storrs CT 06269 USA Palo Alto Networks Inc Santa Clara CA USA Connecticut Transportat Safety Res Ctr Storrs CT USA Microsoft Corp Redmond WA 98052 USA

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow packets from multiple simultaneous transmitters to be received successfully at a receiver. Starting with a clique of n nodes, we first analyze a simple Aloha-like algorithm and show that it takes Theta(n ln n/k) time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. We then design two adaptive neighbor discovery algorithms that dynamically adjust the transmission probability for each node. We show that the adaptive algorithms yield a Theta(ln n) improvement over the Aloha-like scheme for a clique with n, nodes and are thus order-optimal. Finally, we analyze our algorithms in a general multi-hop network setting. We show an upper bound of O(Delta ln n/k) for the Aloha-like algorithm when the maximum node degree is Delta, which is at most a factor In n worse than the optimal. In addition, when Delta is large, we show that the adaptive algorithms are order-optimal, i.e., have a running time of O(Delta/k) which matches the lower bound for the problem.

关键词： Wireless networks ad hoc networks multipacket reception network management neighbor discovery randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Coordinate descent algorithms

引用

MATHEMATICAL PROGRAMMING 2015年第1期151卷 3-34页

作者： Wright, Stephen J. Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence properties, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises frequently in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for problems of this type. We also present some parallel variants and discuss their convergence properties under several models of parallel execution.

关键词： Coordinate descent randomized algorithms Parallel numerical computing

来源：评论

学校读者我要写书评

暂无评论

Non-additive two-option ski rental

引用

THEORETICAL COMPUTER SCIENCE 2015年 584卷 42-52页

作者： Levi, Amir Patt-Shamir, Boaz Tel Aviv Univ Sch Elect Engn IL-6997801 Tel Aviv Israel

We consider the following generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. In our generalization, there are two "payment plans" called "options," such that each option i (for i = 1,2) consists of two kinds of costs: b(i) is the (one time) cost to start using Option i, and a(1) is the (ongoing) usage cost per unit of time for Option i. We assume w.l.o.g. that a(1) > a(2) and b(1) < b(2). Additionally, we assume the existence of a transition cost c, which is incurred if we switch from Option 1 to Option 2. (In the classical version, b(1) = 0, a(2) = 0 and c = b(2).) We give deterministic and randomized algorithms for this general setting and analyze their competitive ratio. We also prove that the competitive ratios of our algorithms are the best possible by presenting matching lower bounds for both the deterministic and the randomized cases. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Competitive analysis Ski rental randomized algorithms Duration prediction Buy or rent

来源：评论

学校读者我要写书评

暂无评论

Online pricing for multi-type of items

引用

THEORETICAL COMPUTER SCIENCE 2015年 572卷 66-82页

作者： Ting, H. F. Xiang, Xiangzhong Univ Hong Kong Dept Comp Pokfulam Hong Kong Peoples R China

This paper studies the online pricing problem in which there is a sequence of users who want to buy items from one seller. The single seller has k types of items and each type has limited copies. These users are arriving one by one at different times and are single-minded. When arriving, each user would announce her interested bundle of items and a non-increasing acceptable price function, which specifies how much she is willing to pay for a certain number of bundles. Upon the arrival of a user, the seller needs to determine immediately the number of bundles to be sold to the user and the price he would charge her. His goal is to maximize the sum of money received from users. When items are indivisible, we show that no deterministic algorithm for the problem could have competitive ratio better than O (hk) where h is the highest unit price that at least some user is willing to pay. Thus we focus on randomized algorithms. We derive a lower bound Omega(logh + root k) on the competitive ratio of any randomized algorithm for solving this problem. Then we give the first competitive randomized algorithm Rp-MULTI which is O (psi(h)root k Delta/delta)-competitive, where Delta and delta are respectively the maximum and minimum copies a type of items can have and psi(h) is a function growing slightly faster than logh. When h is known ahead of time, the ratio is decreased to O ((logh)root k Delta/delta). When items are divisible and can be sold fractionally, we concentrate on designing competitive deterministic algorithms. We give the first competitive deterministic algorithm Dp-MULTI which is O (psi(h)root k Delta/delta)-competitive. When h is known, the ratio can be decreased to O ((logh)root k Delta/delta). We also study randomized algorithms for the problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Online pricing Competitive analysis Lower bounds randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A stopping rule for stochastic approximation

引用

AUTOMATICA 2015年 60卷 1-6页

作者： Wada, Takayuki Fujisaki, Yasumasa Osaka Univ Dept Informat & Phys Sci Suita Osaka 5650871 Japan

A stochastic approximation algorithm is a recursive procedure to find the solution to an unknown nonlinear equation via noisy measurements. In this paper, we present a stopping rule for a stochastic approximation. We show that there is a high probability that the distance between the exact solution and the candidate solution is less than a specified tolerance level when the stochastic approximation stops according to our stopping rule. Furthermore, the number of recursions required by the stopping rule is a polynomial function of the problem size. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Stochastic approximation randomized algorithms Adaptive control System identification

来源：评论

学校读者我要写书评

暂无评论

Robust network supercornputing with unreliable workers

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 75卷 81-92页

作者： Konwar, Kishori M. Rajasekaran, Sanguthevar Shvartsman, Alexander A. Univ Connecticut Storrs CT USA Univ British Columbia Vancouver BC Canada

Internet supercomputing is becoming a powerful tool for harnessing massive amounts of computational resources. However in typical master-worker settings the correctness of the results of the computation crucially relies on the ability of the master to depend on the computation performed by the workers. We consider a distributed system consisting of a master process and a collection of synchronous worker processes that can execute tasks on behalf of the master and that may act nefariously by deliberately returning fallacious results. The master decides on the correctness of the results by assigning the same task to several workers. For such a setting with n processes and t tasks we study the problem of collectively performing the tasks under two different failure models: model-F-a, where some fraction f of workers that are prone to returning arbitrary (e.g., incorrect) results and the probability p of such faulty behavior are not known a priori to the master, and model F-b when these quantities are known to the master. Previous works assume that the number of faulty processes or the probability of a process acting maliciously is known to the master, e.g., as in model F-b. In this paper this assumption is removed in model F-a. First, for model F-a we provide an efficient algorithm-based on the Stopping Rule Algorithm by Dagum et al. (1995)- that can estimate f and p with (is an element of, delta)-approximation, for any 0 < delta < 1 and is an element of > 0. We also provide a randomized algorithm for detecting the faulty processes for model F-a. Finally, we provide algorithms to perform t tasks, with n workers, in models F-a and F-b. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Distributed algorithms Fault-tolerance randomized algorithms Reliability Internet supercomputing

来源：评论

学校读者我要写书评

暂无评论

Guaranteed Outlier Removal with Mixed Integer Linear Programs

Guaranteed Outlier Removal with Mixed Integer Linear Program...

引用

IEEE Conference on Computer Vision and Pattern Recognition

作者： Tat-Jun Chin Yang Heng Kee Anders Eriksson Frank Neumann School of Computer Science The University of Adelaide School of Electrical Engineering and Computer Science Queensland University of Technology

ISBN: (纸本)9781467388528

The maximum consensus problem is fundamentally important to robust geometric fitting in computer vision. Solving the problem exactly is computationally demanding, and the effort required increases rapidly with the problem size. Although randomized algorithms are much more efficient, the optimality of the solution is not guaranteed. Towards the goal of solving maximum consensus exactly, we present guaranteed outlier removal as a technique to reduce the runtime of exact algorithms. Specifically, before conducting global optimization, we attempt to remove data that are provably true outliers, i.e., those that do not exist in the maximum consensus set. We propose an algorithm based on mixed integer linear programming to perform the removal. The result of our algorithm is a smaller data instance that admits a much faster solution by subsequent exact algorithms, while yielding the same globally optimal result as the original problem. We demonstrate that overall speedups of up to 80% can be achieved on common vision problems.

关键词： Mixed integer linear programming outliers linear programming randomized algorithms original problem Mixed integer images computer vision algorithms Runtime Global optimization

来源：评论

学校读者我要写书评

暂无评论

A Survey on Greedy Based algorithms for Biclustering of Gene Expression Microarray Data

A Survey on Greedy Based Algorithms for Biclustering of Gene...

引用

International Conference on Information Technology (ICIT)

作者： Bhawani Sankar Biswal Prateeka Mishra Anjali Mohapatra Swati Vipsita Dept. of CSE IIIT Bhubaneswar Bhubaneswar India

ISBN: (纸本)9781509035854

In the context of gene expression microarray data, biclustering is a technique to identify clusters of genes that are co-expressed under clusters of conditions. It usually has high computational complexity (NP-Hard). In computer science domain, combinatorial problems like biclustering, refer to the tasks associated with the discovery of grouping, ordering or assigning a discrete set of objects fulfilling some fixed constraints. Greedy Search approach is a popular method often used for solving combinatorial problems. It is adoptable in this context because of its variety aspects of search performance. Its variability caused by randomization and the robustness in parameter settings improves the search performance. This review article presents a brief survey of various greedy based biclustering algorithms that are being frequently applied on gene expression microarray data. These algorithms are further classified into iterative greedy approach and stochastic greedy approach based on their search criteria.

关键词： biology computing computational complexity data handling genetics greedy algorithms iterative methods pattern clustering randomised algorithms search problems stochastic processes biology computing greedy algorithm tabu search data processing greedy method iterative methods Markov chain complexity classes Cluster Analysis randomized algorithms Genetics Stochastic Processes

来源：评论

学校读者我要写书评

暂无评论

A probabilistic ellipsoid algorithm for linear optimization problems with uncertain LMI constraints

引用

AUTOMATICA 2015年 52卷 248-254页

作者： Ataei, Armin Wang, Qian Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA Penn State Univ Dept Mech & Nucl Engn University Pk PA 16802 USA

In this paper, a probabilistic algorithm based on the deep cut ellipsoid method is proposed to solve a linear optimization problem subject to an uncertain linear matrix inequality (LMI). First, a deep cut ellipsoid algorithm is introduced to address probabilistic feasibility of the uncertain LMI. Objective cuts are then defined to search for the optimal solution. The final probabilistic ellipsoid algorithm is a combination of feasibility cuts and objective cuts. It is shown that in a finite number of iterations, the ellipsoid algorithm either returns a suboptimal probabilistically feasible solution with a high confidence level or finds the problem infeasible. Furthermore, the bounds of the suboptimal value are provided with probabilistic guarantees. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Linear matrix inequalities randomized algorithms Uncertain systems Ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：