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

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Timothy M. Chan School of Computer Science University of Waterloo

We establish the first nontrivial lower bounds on time-space tradeo's for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω(n log log_S n) expected time in the RAM model (or more generally in the comparison branching program model), if we have S bits of extra space besides the read-only input array. This bound is tight for all S ＞＞ logn, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman, and also complements recent lower bounds that are restricted to sequential access, as in the multi-pass streaming model [Chakrabarti et al., SODA 2008]. We also prove that any comparison-based, deterministic, multi-pass streaming algorithm for finding the median requires Ω(n (log(n/s))~* + n log_s n) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s ＞＞ (logn)~2. We get deterministic lower bounds for I/O-efficient algorithms as well. All proofs in this paper involve "elementary" techniques only.

关键词： Lower bound Read-Only randomized algorithms Proof TIGHT Streaming Sulfur

来源：评论

学校读者我要写书评

暂无评论

Expanders via Random Spanning Trees 09

Expanders via Random Spanning Trees

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Navin Goyal Luis Rademacher Santosh Vempala College of Computing Georgia Tech

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_(n,p), for p = Ω(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary; each spanning tree can be produced independently using an algorithm by Aldous and Broder: A random walk in the graph with edges leading to previously unvisited vertices included in the tree. Splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. For random graphs, splicers provide simple algorithms for sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).

关键词： Expander Device Component Line graph Device Splicer Unions Random randomized algorithms Random walk trees Spanning tree Union Elementary

来源：评论

学校读者我要写书评

暂无评论

Line Transversals of Convex Polyhedra in R~3 09

Line Transversals of Convex Polyhedra in R~3

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Haim Kaplan Natan Rubin Micha Sharir School of Computer Science Tel Aviv University

We establish a bound of O(n~2k~(1+ε)), for any ε > 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in R~3 with a total of n facets, and present a randomized algorithm which computes the boundary of T in comparable expected time. Thus, when k＜＜ n, the new bounds on the complexity (and construction cost) of T improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set T_(l_0) of line transversals which emanate from a fixed line l_0, establish an almost tight bound of O(nk~(1+ε)) on the complexity of T_(l_0), and provide a randomized algorithm which computes T_(l_0) in comparable expected time. Slightly improved combinatorial bounds for the complexity of T_(l_0), and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of P are pairwise disjoint: the case where l_0 is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to l_0.

关键词： polyhedrons randomized algorithms Convex polyhedron Bound Phosphorus Complexity Construction costs Convexity Line mutual exclusion

来源：评论

学校读者我要写书评

暂无评论

Finding duplicates in a data stream 09

Finding duplicates in a data stream

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Parikshit Gopalan Jaikumar Radhakrishnan University of Washington & Microsoft Research SVC TIFR

Given a data stream of length n over an alphabet [m] where n > m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O((logm)~3) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace. We present various relaxations of the condition n > m, under which one can find duplicates efficiently.

关键词： FINDINGS data flow randomized algorithms sublinear streams one pass

来源：评论

学校读者我要写书评

暂无评论

引用

Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

作者： Aviv Nisgav Boaz Patt-Shamir Tel Aviv University Tel Aviv Israel

ISBN: (纸本)9781605586069

We consider a system where users wish to find similar users. To model similarity, we assume the existence of a set of queries, and two users are deemed similar if their answers to these queries are (mostly) identical: each user has a vector of preferences, and two users are similar if their preference vectors differ in only a few coordinates. The preferences are unknown to the system initially, and the goal of the algorithm is to classify the users into classes of roughly the same preferences with the least possible number of queries presented to any user. We prove nearly matching lower and upper bounds on that problem. ecifically, we present an "anytime" algorithm that maintains a partition of the users, and the quality of the partition improves over time: let n be the number of users. At time T, groups of Õ(n/T) users with the same preferences will be separated (with high probability) if they differ in sufficiently many queries. We present a lower bound that matches the upper bound, up to a constant factor, for nearly all possible distances between user groups.

关键词： user classification market segmentation randomized algorithms collaboartive filtering recommendation systems

来源：评论

学校读者我要写书评

暂无评论

Distributed PageRank Computation with Link Failures

Distributed PageRank Computation with Link Failures

引用

2009 American Control Conference (ACC 2009)

作者： Hideaki Ishii Roberto Tempo Department of Computational Intelligence and Systems Science Tokyo Institute of Technology 4259-J2-54 Nagatsuta-cho Midori-ku Yokohama 226-8502 Japan IEIIT-CNR Politecnico di Torino Corso Duca degli Abruzzi 24 10129 Torino Italy

ISBN: (纸本)9781424445233

The Google search engine employs the so-called PageRank algorithm for ranking the search results. This algorithm quantifies the importance of each web page based on the link structure of the web. In this paper, we continue our recent work on distributed randomized computation of PageRank, where the pages locally determine their values by communicating with linked pages. In particular, we propose a distributed randomized algorithm with limited information, where only part of the linked pages is required to be contacted. This is useful to enhance flexibility and robustness in computation and communication.

关键词： Distributed computation Link failures Multi-agent consensus PageRank algorithm Randomization Stochastic matrices Search engines arithmetic Web pages Distribute COMMUNICATING Web search engines randomized algorithms Flexibility Communication Research

来源：评论

学校读者我要写书评

暂无评论

Adaptive randomized Algorithm for Finding Eigenvector of Stochastic Matrix with Application to PageRank

Adaptive Randomized Algorithm for Finding Eigenvector of Sto...

引用

48th IEEE Conference on Decision and Control (CDC)

作者： Alexander Nazin Boris Polyak Laboratory for Adaptive and Robust Control Systems Institute of Control Sciences RAS 65 Profsoyuznaya str. 117997 Moscow Russia

ISBN: (纸本)9781424438716

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent consensus, networked control and data mining. The well-known power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones;they require much less calculations for one iteration and are well-tailored for distributed computations. We propose a novel adaptive randomized algorithm and provide an explicit upper bound for its rate of convergence O((ln N/n)~(1/2)), where N is the dimension and n is the number of iterations. The bound looks promising because (ln N)~(1/2) is not large even for very high dimensions. The proposed algorithm is based on the mirrordescent method for convex stochastic optimization.

关键词： randomized algorithms Eigenvector Stochastic dimensions Competitors data mining iterative methods FINDINGS Self tuning

来源：评论

学校读者我要写书评

暂无评论

Approximating the online set multicover problems via randomized winnowing

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期393卷 54-71页

作者： Berman, Piotr DasGupta, Bhaskar Univ Illinois Dept Comp Sci Chicago IL 60607 USA Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every S is an element of S, and a "coverage factor" (positive integer) k. A subset {i(0), i(1).... } subset of V of elements are presented online in an arbitrary order. When each element i(P) is presented, we are also told the collection of all (at least k) sets (S)i(p) subset of S and their costs to which i(P) belongs and we need to select additional sets from Si-P if necessary such that our collection of selected sets contains at least k sets that contain the element i(P). The goal is to minimize the total cost of the selected sets.' In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of [N. Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (1988) 285-318]. This algorithm generalizes and improves some earlier results in [N. Alon, B. Awerbuch, Y Azar, N. Buchbinder, J. Naor, A general approach to online network optimization problems, in: Proceedings of the 15th ACM-SIAM Symposium on Discrete algorithms, 2004, pp. 570-579;N. Alon, B. Awerbuch, Y Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100-105]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100-105]. (C) 2007 Elsevier B.V. All rights reserved.

关键词： set multicover online algorithms randomized algorithms reverse engineering of biological networks

来源：评论

学校读者我要写书评

暂无评论

A randomized competitive algorithm for evaluating priced AND/OR trees

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期401卷 120-130页

作者： Laber, Eduardo Sany Dept Informat PUC Rio BR-22453901 Rio De Janeiro RJ Brazil

Recently, Charikar et al. investigated the problem of evaluating AND/OR trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. For an AND/OR tree T they presented a mu(T)-competitive deterministic polynomial time algorithm, where mu(T) is the number of leaves that must be read, in the worst case, in order to determine the value of T. Furthermore, they proved that mu(T) is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. The power of randomization in this context has remained as an open question. Here, we take a step towards solving this problem by presenting a 5/6 mu(T)-competitive randomized polynomial time algorithm. This contrasts with the best known lower bound mu(T)/2. (c) 2008 Elsevier B.V. All rights reserved.

关键词： randomized algorithms competitive analysis function evaluation AND/OR trees

来源：评论

学校读者我要写书评

暂无评论

randomized strategies for the plurality problem

引用

DISCRETE APPLIED MATHEMATICS 2008年第17期156卷 3305-3311页

作者： Kral, Daniel Sgall, Jiri Tichy, Tomas Acad Sci Czech Republic Inst Math CZ-11567 Prague Czech Republic Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci Fac Math & Phys CR-11800 Prague Czech Republic

We consider a game played by two players, Paul and Carol. At the beginning of the game, Carol fixes a coloring of n balls. At each turn, Paul chooses a pair of the balls and asks Carol whether the balls have the same color, Carol truthfully answers his question. Paul's goal is to determine the most frequent (plurality) color in the coloring by asking as few questions as possible. The game is studied in the probabilistic setting when Paul is allowed to choose his next question randomly. We give asymptotically tight bounds both for the case of two colors and many colors. For the balls colored by k colors, we prove a lower bound Omega(kn) on the expected number Of questions;this is asymptotically optimal. For the balls colored by two colors, we provide a strategy for Paul to determine the plurality color with the expected number of 2n/3 + O(root n log n) questions;this almost matches the lower bound 2n/3 - O(root n). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Concrete complexity randomized algorithms Plurality game Majority game

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：