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

作者： Chen, Yu University of Pennsylvania

学位级别：Ph.D., Doctor of Philosophy

As the scale of the problems we want to solve in real life becomes larger, the input sizes of the problems we want to solve could be much larger than the memory of a single computer. In these cases, the classical algorithms may no longer be feasible options, even when they run in linear time and linear space, as the input size is too large. In this thesis, we study various combinatorial problems in different computation models that process large input sizes using limited resources. In particular, we consider the query model, streaming model, and massively parallel computation model. In addition, we also study the tradeoffs between the adaptivity and performance of algorithms in these models. We first consider two graph problems, vertex coloring problem and metric traveling salesman problem (TSP). The main results are structure results for these problems, which give frameworks for achieving sublinear algorithms of these problems in different models. We also show that the sublinear algorithms for (∆ + 1)-coloring problem are tight. We then consider the graph sparsification problem, which is an important technique for designing sublinear algorithms. We give proof of the existence of a linear size hypergraph cut sparsifier, along with a polynomial algorithm that calculates one. We also consider sublinear algorithms for this problem in the streaming and query models. Finally, we study the round complexity of submodular function minimization (SFM). In particular, we give a polynomial lower bound on the number of rounds we need to compute s − t max flow - a special case of SFM - in the streaming model. We also prove a polynomial lower bound on the number of rounds we need to solve the general SFM problem in polynomial queries.

关键词： sublinear algorithm Lower bound Combinational problem

来源：评论

学校读者我要写书评

暂无评论

Range partitioning within sublinear time: algorithms and lower bounds

引用

THEORETICAL COMPUTER SCIENCE 2021年 857卷 177-191页

作者： Ning, Baoling Li, Jianzhong Jiang, Shouxu Harbin Inst Technol Harbin Peoples R China

Range partitioning is a typical and mostly used data partitioning method and has became a core operation in most of big data computing platforms. Given an input Lof Ndata items admitting a total order, the goal of range partitioning is to divide the whole input into kranges containing the same number of data items. There is a trivial lower bound Omega(N) for the exact partitioning algorithms, since they need to at least make a full scan of the whole data. In the context of big data computing, even algorithms with O(N) time are not always thought to be efficient enough, the ultimate goal of designing algorithms on big data is usually to solve problems within sublineartime. Therefore, it is well motivated and important to study sublinear algorithms for the range partitioning problem. The paper aims to answer three questions. For the internal memory (RAM) model, since sophisticated sampling based (epsilon, delta)-approximation partitioning algorithm with O(klog(N/delta)/epsilon(2)) time cost has been proposed, the first question is what a lower bound we can obtain for sublinear partitioning algorithms. For the external memory (I/O) model, as far as we know, no previous works give external partitioning algorithms with performance guarantee within sublinear time, therefore the two questions are what the upper bound and the lower bound we can achieve for sublinear external partitioning algorithms. To answer the above questions, based on the RAM and I/O model, the paper studies the lower and upper bounds for the range partitioning problem. For the RAM model, alower bound Omega(k(1-delta)/epsilon(2)) for the cost of sampling based partitioning algorithms is proved. For the I/O model, two lower bounds of the sampling cost required by sublinear external range partitioning algorithms are proved, which indicate that at least a full scan of the whole input is needed in the worst case and a general sublinear external partitioning algorithm does not exist. Motivated by the hard in

关键词： Range partitioning sublinear algorithm Lower bounds External memory model

来源：评论

学校读者我要写书评

暂无评论

Detecting Curved Edges in Noisy Images in sublinear Time

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2017年第3期59卷 373-393页

作者： Wang, Yi-Qing Trouve, Alain Amit, Yali Nadler, Boaz Weizmann Inst Sci Dept Comp Sci & Appl Math Rehovot Israel Univ Paris Saclay CNRS ENS Cachan CMLA F-94235 Cachan France Univ Chicago Dept Stat Chicago IL 60637 USA Univ Chicago Dept Comp Sci Chicago IL 60637 USA Univ Chicago Dept Coll Chicago IL 60637 USA

Detecting edges in noisy images is a fundamental task in image processing. Motivated, in part, by various real-time applications that involve large and noisy images, in this paper we consider the problem of detecting long curved edges under extreme computational constraints, that allow processing of only a fraction of all image pixels. We present a sublinear algorithm for this task, which runs in two stages: (1) a multiscale scheme to detect curved edges inside a few image strips;and (2) a tracking procedure to estimate their extent beyond these strips. We theoretically analyze the runtime and detection performance of our algorithm and empirically illustrate its competitive results on both simulated and real images.

关键词： Curved edge detection sublinear algorithm Noisy images

来源：评论

学校读者我要写书评

暂无评论

sublinear Decoding Schemes for Non-adaptive Group Testing with Inhibitors 1

引用

15th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Bui, Thach, V Kuribayashi, Minoru Kojima, Tetsuya Echizen, Isao SOKENDAI Grad Univ Adv Studies Hayama Kanagawa Japan Natl Inst Informat Tokyo Japan Okayama Univ Okayama Japan Tokyo Coll Natl Inst Technol Hachioji Tokyo Japan

ISBN: (数字)9783030148126

ISBN: (纸本)9783030148119;9783030148126

Identification of up to d defective items and up to h inhibitors in a set of n items is the main task of non-adaptive group testing with inhibitors. To reduce the cost of this Herculean task, a subset of the n items is formed and then tested. This is called group testing. A test outcome on a subset of items is positive if the subset contains at least one defective item and no inhibitors, and negative otherwise. We present two decoding schemes for efficiently identifying the defective items and the inhibitors in the presence of e erroneous outcomes in time poly(d, h, e, log(2) n), which is sublinear to the number of items. This decoding complexity significantly improves the state-of-the-art schemes in which the decoding time is linear to the number of items, i.e., poly(d, h, e, n). Moreover, each column of the measurement matrices associated with the proposed schemes can be nonrandomly generated in polynomial order of the number of rows. As a result, one can save space for storing them. Simulation results confirm our theoretical analysis. When the number of items is sufficiently large, the decoding time in our proposed scheme is smallest in comparison with existing work. In addition, when some erroneous outcomes are allowed, the number of tests in the proposed scheme is often smaller than the number of tests in existing work.

关键词： Non-adaptive group testing sublinear algorithm Sparse recovery

来源：评论

学校读者我要写书评

暂无评论

Dynamic (1+ε)-Approximate Matching Size in Truly sublinear Update Time 64

Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear ...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Bhattacharya, Sayan Kiss, Peter Saranurak, Thatchaphol Univ Warwick Coventry W Midlands England Univ Michighan Ann Arbor MI USA

ISBN: (纸本)9798350318944

We show a fully dynamic algorithm for maintaining (1 + epsilon)-approximate size of maximum matching of the graph with n vertices and m edges using m(0.5-Omega epsilon(1)) update time. This is the first polynomial improvement over the long-standing O(n) update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16], [Behnezhad and Khanna SODA'22]). Our key technical component is the first sublinear algorithm for (1, epsilon n)-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.

关键词： Approximate Maximum Matching Dynamic algorithms sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

On Triangle Estimation Using Tripartite Independent Set Queries

引用

THEORY OF COMPUTING SYSTEMS 2021年第8期65卷 1165-1192页

作者： Bhattacharya, Anup Bishnu, Arijit Ghosh, Arijit Mishra, Gopinath Indian Stat Inst Kolkata India

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the number of triangles in a graph using only polylogarithmic queries when the number of triangles on any edge in the graph is polylogarithmically bounded. Our query oracle Tripartite Independent Set (TIS) takes three disjoint sets of vertices, and as inputs, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of group queries (Ron and Tsur ACM Trans. Comput. Theory 8(4), 15, 2016;Dell and Lapinskas 2018) and in particular is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (2018). We extend the algorithmic framework of Beame et al., with TIS replacing BIS, for approximately counting triangles in graphs.

关键词： Triangle estimation Query complexity sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

Analysis of data streams: Computational and algorithmic challenges

引用

TECHNOMETRICS 2007年第3期49卷 346-356页

作者： Gilbert, A. C. Strauss, M. J. Univ Michigan Dept Math Ann Arbor MI 48109 USA

Over the past 15 years, our ability to collect massive data sets has increased dramatically. Concomitantly, our need to process, compress, store, analyze, and summarize these data sets has grown as well. Scientific, engineering, medical, and industrial applications require that we carry out these tasks efficiently and reasonably accurately. Data streams are one type of modern massive data sets, characterized by their size and by their distributed and dynamic properties. We give an expository discussion of data stream models and the algorithmic challenges that these models pose for computational statistical analysis, then present an overview of three streaming algorithms and a discussion of the computational challenges with each.

关键词： approximation approximation algorithm streaming algorithm sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

Theoretical and experimental analysis of a randomized algorithm for Sparse Fourier transform analysis

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2006年第2期211卷 572-595页

作者： Zou, J Gilbert, A Strauss, M Daubechies, I Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA Princeton Univ Dept Math Princeton NJ 08544 USA

We analyze a sublinear RAlSFA (randomized algorithm for Sparse Fourier analysis) that finds a near-optimal B-term, Sparse representation R for a given discrete signal S of length N, in time and space poly(B, log(N)), following the approach given in [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost poly(log(N)) should be compared with the superlinear Omega(N logN) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RAlSFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002], turns out to be very slow in practice. Our main result is a greatly improved and practical RAlSFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RAlSFA constructs, with probability at least 1 - delta, a near-optimal B-term representation R in time poly(B) log(N) log(1/delta)/is an element of(2) log(M) such that vertical bar vertical bar S - R vertical bar vertical bar(2)(2) <= (1 + is an element of) vertical bar vertical bar S - R(opt)vertical bar vertical bar(2)(2). Furthermore, this RAlSFA implementation already beats the FFTW for not unreasonably large N. We extend the algorithm to higher dimensional cases both theoretically and numerically. The crossover point lies at N similar or equal to 70, 000 in one dimension, and at N similar or equal to 900 for data on a N x N grid in two dimensions for small B signals where there is noise. (c) 2005 Elsevier Inc. All rights reserved.

关键词： RAlSFA sparse Fourier representation fast Fourier transform sublinear algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A sparse spectral method for homogenization multiscale problems

引用

MULTISCALE MODELING & SIMULATION 2007年第3期6卷 711-740页

作者： Daubechies, Ingrid Runborg, Olof Zou, Jing Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA Kungl Tekniska Hogskolan S-10044 Stockholm Sweden Univ Maryland CSCAMM College Pk MD 20742 USA

We develop a new sparse spectral method, in which the fast Fourier transform (FFT) is replaced by RAlSFA (randomized algorithm of sparse Fourier analysis);this is a sublinear randomized algorithm that takes time O(B log N) to recover a B-term Fourier representation for a signal of length N, where we assume B << N. To illustrate its potential, we consider the parabolic homogenization problem with a characteristic. ne scale size epsilon. For fixed tolerance the sparse method has a computational cost of O(vertical bar log epsilon vertical bar) per time step, whereas standard methods cost at least O(epsilon(-1)). We present a theoretical analysis as well as numerical results;they show the advantage of the new method in speed over the traditional spectral methods when epsilon is very small. We also show some ways to extend the methods to hyperbolic and elliptic problems.

关键词： multiscale methods sublinear algorithm homogenization spectral methods sparse Fourier representation

来源：评论

学校读者我要写书评

暂无评论

Finding a dense-core in Jellyfish graphs

引用

COMPUTER NETWORKS 2008年第15期52卷 2831-2841页

作者： Gonen, Mira Ron, Dana Weinsberg, Udi Wool, Avishai Tel Aviv Univ Sch Elect Engn Ramat Aviv Israel

The connectivity of the Internet crucially depends on the relationships between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). These relationships can be modeled as a graph, called the AS-graph, in which the vertices model the ASes, and the edges model the peering arrangements between the ASes. Based on topological studies, it is widely believed that the Internet graph contains a central dense-core: Informally, this is a small set of high-degree, tightly interconnected ASes that participate in a large fraction of end-to-end routes. Finding this dense-core is a very important practical task when analyzing the Internet's topology. In this work we introduce a randomized sublinear algorithm that finds a dense-core of the AS-graph. We mathematically prove the correctness of our algorithm, bound the density of the core it returns, and analyze its running time. We also implemented our algorithm and tested it on real AS-graph data and on real undirected version of WWW network data. Our results show that the core discovered by our algorithm is nearly identical to the cores found by existing algorithms - at a fraction of the running time. (C) 2008 Elsevier B.V. All rights reserved.

关键词： AS-graph Dense-core sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：