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

SIAM JOURNAL ON COMPUTING 2012年第4期41卷 728-746页

作者： Emek, Yuval Halldorsson, Magnus M. Mansour, Yishay Patt-Shamir, Boaz Radhakrishnan, Jaikumar Rawitz, Dror ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland Reykjavik Univ Sch Comp Sci IS-103 Reykjavik Iceland Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay 400005 Maharashtra India

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

关键词： online set packing competitive analysis randomized algorithm packet fragmentation multipacket frames

来源：评论

学校读者我要写书评

暂无评论

Monitoring schedules for randomly deployed sensor networks without geographic information

Monitoring schedules for randomly deployed sensor networks w...

引用

12th International Symposium on Pervasive Systems, algorithms, and Networks (I-SPAN)

作者： Calinescu, G. IIT Dept Comp Sci Chicago IL 60616 USA

ISBN: (纸本)9780769549309

Given n sensors and m targets, a monitoring schedule is a partition of the sensor set such that each part of the partition can monitor all targets. Monitoring schedules are used to maximize the time all targets are monitored when there is no possibility of replacing the batteries of the sensors. Each part of the partition is used for one unit of time, and thus the goal is to maximize the number of parts in the partition. We present distributed algorithms for Monitoring Schedule under the following assumptions: 1) identical sensors can each monitor all targets within a certain radius, 2) the n sensors are randomly distributed uniformly in a large square containing the targets, 3) the number of sensors is high enough given the area the square, and 4) the communication range is at least a constant times the the sensing range. We present randomized distributed algorithms that achieve a constant factor approximation in polylogarithmic number of communication rounds, with high probability. These results hold if we make one of the following two assumptions: 1) any two sensors within communication range are able to estimate within a constant their relative distance, or 2) the communication range is an exact fraction of the sensing range. We improve the results of Calinescu and Ellis (DIAL M-POMC '08) by eliminating the assumption that the communication range must be twice the sensing range, and by this result holding with fewer sensors.

关键词： wireless network distributed algorithm randomized algorithm area monitoring

来源：评论

学校读者我要写书评

暂无评论

Fast Matrix Rank algorithms and Applications 12

Fast Matrix Rank Algorithms and Applications

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Cheung, Ho Yee Kwok, Tsz Chiu Lau, Lap Chi Chinese Univ Hong Kong H ongKong Peoples R China Univ Southern Calif Los Angeles CA USA

ISBN: (纸本)9781450312455

We consider the problem of computing the rank of an m x n matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in (O) over tilde (vertical bar A vertical bar + r(omega)) field operations, where vertical bar A vertical bar denotes the number of nonzero entries in A and omega < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with running time O(mnr(omega-2)). Our algorithm is faster when r < max{m, n}, for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in (O) over tilde (mn) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in numerical linear algebra, combinatorial optimization and dynamic data structure.

关键词： Matrix Rank Numerical Linear Algebra Combinatorial Optimization randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

PHED: Pre-Handshaking Neighbor Discovery Protocols in Full Duplex Wireless Ad Hoc Networks

PHED: Pre-Handshaking Neighbor Discovery Protocols in Full D...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Sun, Guobao Wu, Fan Gao, Xiaofeng Chen, Guihai Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Dept Comp Sci & Engn Shanghai 200030 Peoples R China

ISBN: (纸本)9781467309219;9781467309202

Neighbor Discovery (ND) is a basic and crucial step for initializing wireless ad hoc networks. A fast, precise, and energy-efficient ND protocol has significant importance to subsequent operations in wireless networks. However, many existing protocols have high probabilities to generate idle slots in their neighbor discovering processes, which extends the executing duration, and thus compromises their performance. In this paper, we propose a novel randomized protocol PHED, Pre-Handshaking Neighbor Discovery Protocol, to initialize synchronous full duplex wireless ad hoc networks. By introducing a pre-communication strategy to help each node be aware of activities of its neighborhood, we significantly reduce the probabilities of generating idle slots and collisions. Moreover, with the development of single channel full duplex communication technology [1, 2], we further decrease the processing time needed in PHED, and construct the first full duplex neighbor discovery protocol. Our theoretical analysis proves that PHED can increase the speed of ND by approximately 98% in comparison with the classical ALOHA-like protocols [3, 4]. In addition, we prove the effectiveness of PHED by simulations.

关键词： Wireless Ad Hoc Networks Neighbor Discovery Full Duplex Technology randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved PTAS approximation algorithm for k-means Clustering Problem

An Improved PTAS approximation Algorithm for k-means Cluster...

引用

2nd International Conference on Uncertainty Reasoning and Knowledge Engineering (URKE)

作者： Wang Shouqiang Shanghai Jiao Tong Univ Dept Informat Engn Jinan 250023 Peoples R China

ISBN: (纸本)9781467314602

This paper presented an improved (1+epsilon)-randomized approximation algorithm proposed by Ostrovsky. The running time of the improved algorithm is O(2(O(k alpha 2/epsilon)) nd), where d,n denote the dimension and the number of the input points respectively, and alpha(<1) represents the separated coefficient. The successful probability is (1/2(1 - e((-1/2 epsilon))))(k)(1 - O(root alpha)). Compared to the original algorithm, the improved algorithm runs more efficiency.

关键词： Algorith randomized algorithm Clustering Centroid

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm with Constant Approximation for k-Means Based on the Least Cluster Size

A Randomized Algorithm with Constant Approximation for <i>k<...

引用

7th World Congress on Intelligent Control and Automation

作者： Wang, Shouqiang Zhu, Daming Zhang, Sheng Shandong Univ Sch Comp Sci & Technol Jinan 250010 Peoples R China Shandong Jiaotong Univ Dept Informat Engn Jinan 250023 Peoples R China

ISBN: (纸本)9781424421138

The k-means clustering is one of the most popular schemes to solve the problem of clustering. This paper investigates the approximate algorithm for the k-means clustering by means of selecting the k initial points used as centers from the original point set. It is proved that an expected 2-approximation factor can be obtained, if k centers belong to one of the optimal sub cluster points respectively. To find these k points, a randomized algorithm is proposed which obtain an expected 2-approximation factor with high probability. This algorithm selects some points from the original points to be used as candidate centers, and the size of the sample is based on having at least points of each cluster. At last, some-examples are selected to verify our algorithm and get good results.

关键词： k-means clustering algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm for the sum selection problem

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期377卷 151-156页

作者： Lin, Tien-Ching Lee, D. T. Acad Sinica Inst Informat Sci Taipei 11529 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 10764 Taiwan

Let A be a sequence of n real numbers a(1), a(2),., a(n). We consider the SUM SELECTION PROBLEM as that of finding the segment A(i*, j*) such that the rank of s(i*, j*) = Sigma(j*)(t=i) at over all possible feasible segments is k, where a feasible segment A (i, j) = a(i), a(i + 1),..., a(j) is a consecutive subsequence of A, and its width j - i + 1 satisfies l <= j - i + 1 <= u for some given integers t and it, and l <= u. It is a generalization of two well-known problems: the SELECTION PROBLEM in computer science for which e = it = 1, and the MAXIMUM SUM SEGMENT PROBLEM in bioinformatics for which the rank k is the total number of possible feasible segments. We will give a randomized algorithm for the Sum SELECTION PROBLEM that runs in expected O(n log(u - l)) time. It matches the optimal O(n) time randomized algorithm for the SELECTION PROBLEM. We can also solve the K MAXIMUM SUMS PROBLEM, to enumerate the k largest sums, in expected 0(n log(u - e) + k) time. The previously best known result was an algorithm that solves this problem for the case when f = 1, u = n and runs in O(n log(2) n + k) time in the worst case. (c) 2007 Elsevier B.V. All rights reserved.

关键词： bioinformatics randomized algorithm random sampling order-statistic tree k maximum sums problem sum selection problem selection problem maximum sum segment problem maximum sum problem

来源：评论

学校读者我要写书评

暂无评论

Time-Efficient randomized Multiple-Message Broadcast in Radio Networks 11

Time-Efficient Randomized Multiple-Message Broadcast in Radi...

引用

30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Khabbazian, Majid Kowalski, Dariusz R. Univ Winnipeg Dept Appl Comp Sci Winnipeg MB R3B 2E9 Canada

ISBN: (纸本)9781450307192

Multiple-message broadcast, or k-broadcast, is one of the fundamental problems in network communication. In short, there are k packets distributed across the network, each of them has to be delivered to all other nodes. We consider this task in the model of multi-hop radio network, in which n nodes interact by transmitting and receiving messages. A message transmitted at a round reaches all neighbors of the transmitter at the end of the same round, but may not be successfully received by some, or even all, of these neighbors. More specifically, a node receives a message at a round if this is the only message that has reached this node in this round. Due to this specific interference-prone nature of radio networks, many communication tasks become more challenging and more costly than in other types of networks, especially in ad-hoc setting in which each node knows only its own id and linear estimates on the basic network parameters, such as the number of nodes n, diameter D and maximum node degree Delta. We design a new randomized k-broadcast algorithm combining the best of two worlds: efficient randomized transmission schedules and network coding. We show that our algorithm accomplishes multi-broadcast in O(log Delta) amortized number of communication rounds per packet, with high probability. This improves over the best previous solution of Bar-Yehuda. Israeli and Itai [5], which guarantees only O(log Delta log n) of amortized number of rounds per packet, with high probability.

关键词： radio networks multiple-message broadcast randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A FAST algorithm FOR FOURIER CONTINUATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2011年第6期33卷 3241-3260页

作者： Lyon, Mark Univ New Hampshire Dept Math & Stat Durham NH 03861 USA

A new algorithm is presented which provides a fast method for the computation of recently developed Fourier continuations (a particular type of Fourier extension method) that yield superalgebraically convergent Fourier series approximations of nonperiodic functions. Previously, the coefficients of an approximating Fourier series have been obtained by means of a regularized singular value decomposition (SVD)-based least-squares solution to an overdetermined linear system of equations. These SVD methods are effective when the size of the system does not become too large, but they quickly become unwieldy as the number of unknowns in the system grows. We demonstrate a novel decoupling of the least-squares problem which results in two systems of equations, one of which may be solved quickly by means of fast Fourier transforms (FFTs) and another that is demonstrated to be well approximated by a low-rank system. Utilizing randomized algorithms, the low-rank system is reduced to a significantly smaller system of equations. This new system is then efficiently solved with drastically reduced computational cost and memory requirements while still benefiting from the advantages of using a regularized SVD. The computational cost of the new algorithm in on the order of the cost of a single FFT multiplied by a slowly increasing factor that grows only logarithmically with the size of the system.

关键词： Fourier series continuation method Fourier extension randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Property Tester for Tree-Likeness of Quartet Topologies

引用

THEORY OF COMPUTING SYSTEMS 2011年第3期49卷 576-587页

作者： Chang, Maw-Shang Lin, Chuang-Chieh Rossmanith, Peter Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan Rhein Westfal TH Aachen Dept Comp Sci D-52056 Aachen Germany

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property P and a parameter 0 0, and present the first property tester ... 详细信息

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property P and a parameter 0 < epsilon < 1, by examining function values of f over o(vertical bar D vertical bar) elements in D, determine whether f satisfies P or differs from any one which satisfies P in at least epsilon vertical bar D vertical bar elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f(Q), which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that fQ satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f(Q). In this paper, we prove the existence of a set of quartet topologies of error number at least c((n)(4)) for some constant c > 0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n(3)/epsilon) queries, and is of one-sided error and non-adaptive.

关键词： randomized algorithm Property testing Evolutionary tree Quartet method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：