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

Proceedings of the Fifteenth annual acm-siam symposium on discrete algorithms

作者： Fill, James Allen Janson, Svante Department of Mathematical Sciences Johns Hopkins University 34th and Charles Streets Baltimore MD 21218-2682 United States Department of Mathematics Uppsala University P. O. Box 480 SE-751 06 Uppsala Sweden

the analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit comparisons. On the other hand, the standard analyses of many other algorithms (such as Quicksort) are performed in terms of the number of key comparisons. We introduce the prospect of a fair comparison between algorithms of the two types by providing an average-case analysis of the number of bit comparisons required by Quicksort. Counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total. We also provide a new algorithm, "BitsQuick", that reduces this factor to constant order by eliminating needless bit comparisons.

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

13th annual acm-siam symposium on discrete algorithms, SODA 2002

ISBN: (纸本)089871513X

the proceedings contain 129 papers. the topics discussed include: union-find with deletions;on directed Steiner trees;cache oblivious search trees via binary trees of small height;a locality-preserving cache-oblivious dynamic dictionary;optimal time-space trade-offs for non-comparison-based sorting;an approximation algorithm for the group Steiner problem;static optimality and dynamic search-optimality in lists and trees;improved algorithms for the data placement problem;web caching with request reordering;censorship resistant peer-to-peer content addressable networks;an ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph;undiscretized dynamic programming: faster algorithms for facility location and related problems on trees;Delaunay triangulation programs on surface data;dense point sets have sparse Delaunay triangulations;and quality meshing with weighted Delaunay refinement.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

ISBN: (纸本)9781510819672

the proceedings contain 146 papers. the topics discussed include: locality-sensitive hashing without false negatives;new directions in nearest neighbor searching with applications to lattice sieving;phase transitions in group testing;tight bounds for the distribution-free testing of monotone conjunctions;designing networks with good equilibria under uncertainty;characterization of strongly stable matchings;learning and efficiency in games with dynamic population;on dynamic approximate shortest paths for planar graphs with worst case costs;error amplification for pairwise spanner lower bounds;on notions of distortion and an almost minimum spanning tree with constant average distortion;approximately efficient double auctions with strong budget balance;and interpolating between truthful and non-truthful mechanisms for combinatorial auctions.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

ISBN: (纸本)9781510819672

关键词：

来源：评论

学校读者我要写书评

暂无评论

Lower-Bounded Facility Location

引用

acm TRANSACTIONS ON algorithms 2010年第4期6卷 1–16页

作者： Svitkina, Zoya Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

We study the lower-bounded facility location problem which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this facility is opened. this problem was introduced independently in the papers by Karger and Minkoff [2000] and by Guha et al. [2000], both of which give bicriteria approximation algorithms for it. these bicriteria algorithms come within a constant factor of the optimal solution cost, but they also violate the lower bound constraints by a constant factor. Our result in this article is the first true approximation algorithm for the lower-bounded facility location problem which respects the lower bound constraints and achieves a constant approximation ratio for the objective function. the main technical idea for the design of the algorithm is a reduction to the capacitated facility location problem, which has known constant-factor approximation algorithms.

关键词： Approximation algorithm facility location

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

ISBN: (纸本)9781510819672

关键词：

来源：评论

学校读者我要写书评

暂无评论

All-to-all optical routing in optimal chordal rings of degree four

All-to-all optical routing in optimal chordal rings of degre...

引用

10th annual acm-siam symposium on discrete algorithms

作者： Narayanan, L Opatrny, J Sotteau, D Concordia Univ Dept Comp Sci Montreal PQ H3G 1M8 Canada

ISBN: (纸本)0898714346

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing(or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. the switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently ii they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of routes to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus an the all-to-all communication instance I-A in a widely studied family of chordal rings of degree 4, called optimal chordal rings. For these networks, we prove exact bounds on the optimal load induced on an edge for I-A, over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I-A using at most 1.013 times the lower bound on the number of wavelengths. the previous best approximation algorithm has performance ratio 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks.

关键词： algorithms

来源：评论

学校读者我要写书评

暂无评论

Superiority and Complexity of the Spaced Seeds

Superiority and Complexity of the Spaced Seeds

引用

17th acm-siam symposium on discrete algorithms

作者： Li, Ming Ma, Bin Zhang, Louxin Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Western Ontario Dept Comp Sci London ON N6A 5B8 Canada Natl Univ Singapore Dept Math Singapore 117543 Singapore

ISBN: (纸本)9780898716054

Optimal spaced seeds were introduced by the theoretical computer science community to bioinformatics to effectively increase homology search sensitivity. they are now serving thousands of homology search queries daily. While dozens of papers have been published on optimal spaced seeds since their invention, many fundamental questions still remain unanswered. In this paper, we settle several open questions in this area. Specifically, we prove that when the length of a non-uniformly spaced seed is bounded by an exponential function of the seed weight, the seed outperforms strictly the traditional consecutive seed in both (i) the average number of non-overlapping hits and (ii) the asymptotic hit probability. then, we study the computation of the hit probability of a spaced seed, solving three more open questions: (iii) hit probability computation in a uniform homologous region is NP-hard and (iv) it admits a PTAS;(v) the asymptotic hit probability is computable in exponential time in seed length, independent of the homologous region length.

关键词： Seed

来源：评论

学校读者我要写书评

暂无评论

Optimal Construction of Compressed Indexes for Highly Repetitive Texts 30

Optimal Construction of Compressed Indexes for Highly Repeti...

引用

30th annual acm-siam symposium on discrete algorithms (SODA)

作者： Kempa, Dominik Univ Helsinki Helsinki Inst Informat Technol HIIT Dept Comp Sci Helsinki Finland Univ Warwick Dept Comp Sci Coventry England Univ Warwick Ctr Discrete Math & its Applicat DIMAP Coventry England

ISBN: (纸本)9781611975482

We propose algorithms that, given the input string of length n over integer alphabet of size sigma, construct the Burrows{Wheeler transform (BWT), the permuted longest-common-prefix (PLCP) array, and the LZ77 parsing in O(n= log(sigma) n + r polylog n) time and working space, where r is the number of runs in the BWT of the input. these are the essential components of many compressed indexes such as compressed suffix tree, FM-index, and grammar and LZ77-based indexes, but also find numerous applications in sequence analysis and data compression. the value of r is a common measure of repetitiveness that is significantly smaller than n if the string is highly repetitive. Since just accessing every symbol of the string requires Omega(n/ log(sigma) n) time, the presented algorithms are time and space optimal for inputs satisfying the assumption n=r is an element of(polylog n) on the repetitiveness. For such inputs our result improves upon the currently fastest general algorithms of Belazzougui (STOC 2014) and Munro et al. (SODA 2017) which run in O(n) time and use O(n= log(sigma) n) working space. We also show how to use our techniques to obtain optimal solutions on highly repetitive data for other fundamental string processing problems such as: Lyndon factorization, construction of run-length compressed suffix arrays, and some classical \textbook" problems such as computing the longest substring occurring at least some fixed number of times.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Tree Exploration with Logarithmic Memory 18

Tree Exploration with Logarithmic Memory

引用

18th acm-siam symposium on discrete algorithms

作者： Gasieniec, Leszek Pelc, Andrzej Radzik, Tomasz Zhang, Xiaohui Univ Liverpool Dept Comp Sci Chadwick Bldg Liverpool L69 7ZF Merseyside England Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada Kings Coll London Dept Comp Sci London WC2R 2LS England

ISBN: (纸本)9780898716245

We consider the task of network exploration by a mobile agent (robot) with small memory. the agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. the agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O(log n)-bit memory for all n-node trees. this strengthens the result from [15], where O(log(2) n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there.

关键词： Mobile agents

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：