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

Counting distinct items over update streams

16th International Symposium on algorithms and Computations (ISAAC 2005)

作者： Ganguly, Sumit Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

ISBN: (纸本)3540309357

In data streaming applications, data arrives at rapid rates and in high volume, thus making it essential to process each stream update very efficiently in terms of both time and space. A data stream is a sequence of data records that must be processed continuously in an online fashion using sub-linear space and sub-linear processing time. We consider the problem of tracking the number of distinct items over data streams that allow insertion and deletion operations. We present two algorithms that improve on the space and time complexity of existing algorithms. (c) 2007 Elsevier B. V. All rights reserved.

关键词： randomized algorithm online algorithm data stream distinct items negative dependence

来源：评论

学校读者我要写书评

暂无评论

A modified ant algorithm for solving the quadratic assignment problem

A modified ant algorithm for solving the quadratic assignmen...

引用

International Conference on Intelligent Pervasive Computing (IPC 2007)

作者： Qi, Chengming Beijing Union Univ Coll Automat Beijing 100101 Peoples R China

ISBN: (纸本)9780769530062

The Quadratic Assignment Problem(QAP) is one of the hardest combinatorial optimization problems known. Ant algorithms have been inspired by the behavior of real ant colonies. In this paper, we introduce random algorithm to the constructive procedure of the solution of Ant System (AS) and adopt dynamic adaptive approach to update pheromone trails. In our algorithm, only partial facilities are randomly chosen to compute the designed probability. Experimental results for solving the QAP demonstrate that the proposed approach can obtain the better quality of the solutions.

关键词： ant system combinatorial optimization randomized algorithm QAP

来源：评论

学校读者我要写书评

暂无评论

An improved randomized on-line algorithm for a weighted interval selection problem

引用

JOURNAL OF SCHEDULING 2004年第4期7卷 293-311页

作者： Miyazawa, H Erlebach, T ETH Comp Engn & Networks Lab TIK CH-8092 Zurich Switzerland Univ Tokyo Grad Sch Engn Dept Math Engn & Informat Phys Bunkyo Ku Tokyo 1138656 Japan

Given a set of weighted intervals, the objective of the weighted interval selection problem (WISP) is to select a maximum-weight subset such that the selected intervals are pairwise disjoint. We consider on-line algorithms that process the intervals in order of non-decreasing left endpoints. Preemption is allowed, but rejections are irrevocable. This problem has natural applications in various scheduling problems. We study the class of monotone instances of WISP, i.e., we require that the order of right endpoints of the given intervals coincides with that of the left endpoints. This class includes the case where all intervals have the same length. For monotone instances of WISP, the best possible competitive ratio for deterministic on-line algorithms is known to be 1/4. It has long been an open question whether there exists a randomized algorithm with better competitive ratio. In this paper, we present a new randomized algorithm and prove that it achieves a better competitive ratio 1/3 for the special case of monotone WISP where the sequence of weights of the arriving intervals is non-decreasing. Thus we provide the first result towards a solution of the long-standing open question. Furthermore, we show that no randomized algorithm achieves a competitive ratio strictly larger than 4/5. This is the first non-trivial upper bound for randomized algorithms for monotone WISP.

关键词： interval scheduling on-line algorithm competitive analysis randomized algorithm upper bound lower bound

来源：评论

学校读者我要写书评

暂无评论

Club theory of the Grid

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2006年第14期18卷 1759-1773页

作者： Shi, Yao Lau, Francis C. M. Tse, Savio S. H. Du, Zhi-Hui Tang, Rui-Chun Li, San-Li Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

The Grid is a new type of resource sharing infrastructure. Due to software and hardware limitations, the service that a certain Grid can offer is finite, and so is the number of users it can accommodate. If the number of users is too small, much of the planned resources would be wasted. On the other hand, excessive loading due to too many users could substantially reduce the benefit enjoyed by each user and also the efficiency of the Grid service. Therefore, there are two main problems for Grid design. (1) How many users should the Grid serve so that each user can receive the maximum benefit? (2) To a certain group of users, how much resources should be invested so that the construction and maintenance of the Grid become viable? Based on the economic theory of clubs, this paper gives a quantitative analysis of the quasi-optimal number of users and amount of each resource by regarding Grid services and resources as club goods. Based on our assumptions on the system model, we deduce two preliminary results and verify them by experiments using GridFTP. These two results allow the users to run randomized algorithms to achieve better system performance. Copyright (c) 2006 John Wiley & Sons, Ltd.

关键词： Grid computing club theory cost-benefit analysis randomized algorithm probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

RANDOM EDGE can be exponential on abstract cubes

引用

ADVANCES IN MATHEMATICS 2006年第1期204卷 262-277页

作者： Matousek, Jiri Szabo, Tibor ETH Zentrum Inst Theoret Informat Zurich Switzerland Charles Univ Prague Dept Appl Math Prague 11800 1 Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI Prague 11800 1 Czech Republic

We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by Williamson Hoke [Completely unimodal numberings of a simple polytope, Discrete Appl. Math. 20 (1988) 69-81.] and by Kalai [A simple way to tell a simple polytope from its graph, J. Combin. Theory Ser. A 49(2) (1988) 381-383.] under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const.n(1/3)) steps with high probability. The best previous lower bound was quadratic. So in order for RANDOM EDGE to succeed in polynomial time, geometry must help. (C) 2005 Elsevier Inc. All rights reserved.

关键词： linear programming simplex algorithm abstract objective function randomized algorithm unique sink orientation

来源：评论

学校读者我要写书评

暂无评论

On the probabilistic foundations of probabilistic roadmap planning

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2006年第7期25卷 627-643页

作者： Hsu, David Latombe, Jean-Claude Kurniawati, Hanna Natl Univ Singapore Dept Comp Sci Singapore 117543 Singapore Stanford Univ Dept Comp Sci Stanford CA 94305 USA

Why is probabilistic roadmap (PRM) planning probabilistic? How does the probability measure used for sampling a robots configuration space affect the performance of a PRM planner? These questions have received little attention to date. This paper tries to fill this gap and identify promising directions to improve future planners. It introduces the probabilistic foundations of PRM planning and examines previous work in this context. It shows that the success of PRM planning depends mainly and critically on favorable "visibility" properties of a robot's configuration space. A promising direction for speeding up PRM planners is to infer partial knowledge of such properties from both workspace geometry and information gathered during roadmap construction, and to use this knowledge to adapt the probability measure for sampling. This paper also shows that the choice of the sampling source-pseudo-random or deterministic-has small impact on a PRM planner's performance, compared with that of the sampling measure. These conclusions are supported by both theoretical and empirical results.

关键词： robotics motion planning randomized algorithm random sampling probabilistic roadmap planning

来源：评论

学校读者我要写书评

暂无评论

GENERALIZED k-MULTIWAY CUT PROBLEMS

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2006年第1-2期21卷 69-82页

作者： Liu, Jiping Peng, Yuejian Zhao, Cheng Univ Lethbridge Dept Math & Comp Sci Lethbridge AB T1K 3M4 Canada Indiana State Univ Dept Math & Comp Sci Terre Haute IN 47809 USA

This paper considers the following problem: given an edgeweighted graph G = (V, E, w) and disjoint k-subsets U-p of V, find a minimum weighted set of edges E' subset of E such that its removal disconnects the graph into k parts and each part contains exactly one vertex from each U-p for 1 <= p <= r. This generalizes some well-known NP-hard problems. In this paper, we first apply greedy local search algorithm to obtain better approximation solutions. Then we give a randomized local search algorithm which produces a solution within a factor (1 + epsilon) with the probability at least (1 - 1/e) for any small epsilon. Simple near- optimum approximation algorithms are also proposed. Analogously, there is a maximum k-multiway cut problem with the same restrictions.

关键词： Approximation generalized k-multiway cut local search randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2006年第11期5卷 1620-1632页

作者： Luo, Hong Liu, Yonghe Das, Sajal K. Beijing Univ Posts & Telecommun Coll Comp Sci & Technol Beijing 100876 Peoples R China Univ Texas Dept Comp Sci & Engn Arlington TX 76019 USA

In this paper, we propose a routing algorithm called Minimum Fusion Steiner Tree (MFST) for energy efficient data gathering with aggregation ( fusion) in wireless sensor networks. Different from existing schemes, MFST not only optimizes over the data transmission cost, but also incorporates the cost for data fusion, which can be significant for emerging sensor networks with vectorial data and/or security requirements. By employing a randomized algorithm that allows fusion points to be chosen according to the nodes' data amounts, MFST achieves an approximation ratio of 5/4 log(k+1), where k denotes the number of source nodes, to the optimal solution for extremely general system setups, provided that fusion cost and data aggregation are nondecreasing against the total input data. Consequently, in contrast to algorithms that only excel in full or nonaggregation scenarios without considering fusion cost, MFST can thrive in a wide range of applications.

关键词： wireless sensor networks data fusion routing randomized algorithm approximation

来源：评论

学校读者我要写书评

暂无评论

A collaborative approach to stochastic load balancing with networked queues of autonomous service clusters

A collaborative approach to stochastic load balancing with n...

引用

International Conference on Collaborative Computing

作者： Lai, Cheng-Jia Polak, Wolfgang FX Palo Alto Lab 3400 Hillview AveBuilding 4 Palo Alto CA 94304 USA

ISBN: (纸本)9781424404285

Load balancing has been an increasingly important issue for handling computational intensive tasks in a distributed system such as in Grid and cluster computing. In such systems, multiple server instances are installed for handling requests from client applications, and each request (or task) typically needs to stay in a queue before an available server is assigned to process it. In this paper, we propose a high-performance queueing method for implementing a shared queue for collaborative clusters of servers. Each cluster of servers maintains a local queue and queues of different clusters are networked to form a unified (or shared) queue that may dispatch tasks to all available servers. We propose a new randomized algorithm for forwarding requests in an overcrowded local queue to a networked queue based on load information of the local and neighboring clusters. The algorithm achieves both load balancing and locality awareness.

关键词： groupware queueing theory randomised algorithms resource allocation workstation clusters autonomous service cluster collaborative server cluster high performance queueing locality awareness networked queue randomized algorithm shared queue stochastic loa

来源：评论

学校读者我要写书评

暂无评论

Computation of probabilistic output admissible set for time-varying uncertain constrained system

Computation of probabilistic output admissible set for time-...

引用

SICE-ICASE International Joint Conference

作者： Hatanaka, Takeshi Takaba, Kiyotsugu Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan JSPS Tokyo Japan

ISBN: (纸本)9788995003848

This paper considers time-varying uncertain constrained systems, and develops a method for computing a probabilistic output admissible (POA) set which consists of initial states probabilistically assured to satisfy the infinitetime constraint. The algorithm for the time-invariant case has already been presented in Hatanaka and Takaba (2006). This paper shows how this algorithm is extended to the time-varying case when an upper bound of a number called future output admissibility (FOA) index is available. We moreover present two methods for computing an upper bound of the FOA index;probabilistic and deterministic methods.

关键词： constrained system uncertainty maximal output admissible set randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：