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

Communication Complexity of Quasirandom Rumor Spreading

algorithmICA 2015年第2期72卷 467-492页

作者： Berenbrink, Petra Elsaesser, Robert Sauerwald, Thomas Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Salzburg Univ Dept Comp Sci A-5020 Salzburg Austria Univ Cambridge Comp Lab Cambridge CB3 0FD England

We consider rumor spreading on random graphs and hypercubes in the quasirandom phone call model. In this model, every node has a list of neighbors whose order is specified by an adversary. In step i every node opens a channel to its ith neighbor (modulo degree) on that list, beginning from a randomly chosen starting position. Then, the channels can be used for bi-directional communication in that step. The goal is to spread a message efficiently to all nodes of the graph. For random graphs (with sufficiently many edges) we present an address-oblivious algorithm with runtime O(logn) that uses at most O(nloglogn) message transmissions. For hypercubes of dimension logn we present an address-oblivious algorithm with runtime O(logn) that uses at most O(n(loglogn)(2)) message transmissions. Together with a result of Elsasser (Proc. of SPAA'06, pp. 148-157, 2006), our results imply that for random graphs the communication complexity of the quasirandom phone call model is significantly smaller than that of the standard phone call model.

关键词： randomized algorithm Broadcasting Parallel computing

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Distributed and on-line routing on tori

引用

algorithmICA 2002年第4期32卷 562-593页

作者： Yeh, TH Kuo, CM Lei, CL Yen, HC Natl Taiwan Univ Dept Elect Engn Taipei 10764 Taiwan

In this paper we study tire problem of assigning paths to packets oil N x N tori in an on-line and distributed fashion. By on-line we mean that the routing decisions must be made without any knowledge of future requests. Being distributed is an equally important feature of our design. for Such algorithms need knot know the global configuration of the network in the process of routing packets. We use the technique of competitive analysis to measure the performance of our design, In addition to showing an Omega(log N) lower bound on the competitive ratio, we present both deterministic and randomized algorithms which are O(log N) competitive with respect to the maximum load (i.e., congestion) on communication links.

关键词： routing on-line algorithm competitive analysis distributed algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

WEIGHTED FRACTIONAL AND INTEGRAL KAPPA-MATCHING IN HYPERGRAPHS

引用

DISCRETE APPLIED MATHEMATICS 1995年第2-3期57卷 255-269页

作者： SRIVASTAV, A STANGIER, P UNIV COLOGNE INST INFORMATD-50969 COLOGNEGERMANY

We consider the problem of finding polynomial-time approximations of maximal weighted k-matchings in a hypergraph and investigate the relationship between the integral and fractional maxima of the corresponding 0-1 integer linear program and its LP-relaxation. We extend results of Raghavan, who gave a deterministic approximation algorithm for unweighted k-matching, to the weighted case and compare the so obtained lower bound for the ratio of the integer and fractional maximum with a lower bound of Aharoni et al. (1985) and Alon et al. (1992).

关键词： HYPERGRAPH MATCHING INTEGER AND LINEAR PROGRAMMING randomized algorithm DERANDOMIZATION

来源：评论

学校读者我要写书评

暂无评论

Connected facility location via random facility sampling and core detouring

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第8期76卷 709-726页

作者： Eisenbrand, Friedrich Grandoni, Fabrizio Rothvoss, Thomas Schafer, Guido Ecole Polytech Fed Lausanne Inst Math CH-1015 Lausanne Switzerland Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Ctr Wiskunde & Informat NL-1090 GB Amsterdam Netherlands

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Connected facility location Approximation algorithm randomized algorithm Network design

来源：评论

学校读者我要写书评

暂无评论

Streaming Histogram Publication over Weighted Sliding Windows Under Differential Privacy

引用

Tsinghua Science and Technology 2024年第6期29卷 1674-1693页

作者： Xiujun Wang Lei Mo Xiao Zheng Zhe Dang School of Computer Science and Technology Anhui University of TechnologyMa’anshan 243032China Institute for Artificial Intelligence Hefei Comprehensive National Science CenterHefei 230088China Baosight Software(Anhui)Co.Ltd. Ma’anshan 243000China School of Electrical Engineering and Computer Science Washington State UniversityPullman 99164WAUSA

Continuously publishing histograms in data streams is crucial to many real-time applications,as it provides not only critical statistical information,but also reduces privacy leaking *** the importance of elements usually decreases over time in data streams,in this paper we model a data stream by a sequence of weighted sliding windows,and then study how to publish histograms over these windows *** existing literature can hardly solve this problem in a real-time way,because they need to buffer all elements in each sliding window,resulting in high computational overhead and prohibitive storage *** this paper,we overcome this drawback by proposing an online algorithm denoted by Efficient Streaming Histogram Publishing(ESHP)to continuously publish histograms over weighted sliding ***,our method first creates a novel sketching structure,called Approximate-Estimate Sketch(AESketch),to maintain the counting information of each histogram interval at every time instance;then,it creates histograms that satisfy the differential privacy requirement by smartly adding appropriate noise values into the sketching *** experimental results and rigorous theoretical analysis demonstrate that the ESHP method can offer equivalent data utility with significantly lower computational overhead and storage costs when compared to other existing methods.

关键词： differential privacy randomized algorithm streaming data publication weighted sliding window approximate statistics data usability computational complexity

来源：评论

学校读者我要写书评

暂无评论

Practical algorithm Substitution Attacks on Real-World Public-Key Cryptosystems

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2023年 18卷 5069-5081页

作者： Jiang, Haodong Han, Jiang Zhang, Zhenfeng Ma, Zhi Wang, Hong Henan Key Lab Network Cryptog Technol Zhengzhou 450001 Henan Peoples R China Chinese Acad Sci Inst Software Beijing 100190 Peoples R China

The revelations about massive surveillance have created significant interest in algorithm substitution attack (ASA), where an honest implementation of a cryptographic primitive is replaced by a subverted one which can help "big brother" to break cryptographic security while generating output indistinguishable from the honest output. The current known ASAs on public-key cryptography are either dedicated for a type of concrete constructions with specific internal, or restrictive when applying to the real-word cryptographic standards (Ateniese et al., ACM CCS'15;Russell et al., ACM CCS'17;Chen et al., ASIACRYPT'20). In this paper, we first present a practical undetectable substitution for a general randomized algorithm with certain structure such that the randomness can be revealed to the big brother. Then, instantiating this randomized algorithm, we present a series of ASAs on core primitives in public-key cryptography including public-key encryption, key encapsulation mechanism, key exchange, and digital signature. In particular, our ASAs are universal in the sense that they do not rely on the internal description of the underlying cryptographic algorithm. Moreover, our ASAs are also practical since they can affect not only the widely deployed cryptographic standards, but also the ongoing NIST post-quantum standards.

关键词： algorithm substitution attack randomized algorithm public-key cryptography

来源：评论

学校读者我要写书评

暂无评论

Time-optimal construction of overlay networks

引用

DISTRIBUTED COMPUTING 2023年第3期36卷 313-347页

作者： Goette, Thorsten Hinnenthal, Kristian Scheideler, Christian Werthmann, Julian Paderborn Univ Dept Comp Sci Warburger Str 100 D-33098 Paderborn Germany

This article shows how to construct an overlay network of constant degree and diameter O(log n) in O(log n) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network's graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in O(log n) time w.h.p., which beats the currently best O(log3/2 n) time algorithm of Gotte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Q(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. algorithms and techniques (APPROX/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks (Augustine et al. in Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm's execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in O(log n) time w.h.p.

关键词： Distributed protocol Peer-to-peer network randomized algorithm Expander

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Cell Association and Scheduling in Femtocell Networks

引用

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTING 2015年第3期3卷 432-443页

作者： Zhou, Hui Mao, Shiwen Agrawal, Prathima Auburn Univ Dept Elect & Comp Engn Auburn AL 36849 USA

Femtocells are recognized as effective for improving network coverage and capacity and for reducing power consumption due to the reduced range of wireless transmissions. Although highly appealing, a plethora of challenging problems need to be addressed for fully harvesting its potential. In this paper, we investigate the problem of cell association and service scheduling in femtocell networks. In addition to the general goal of offloading traffic from the macrobase station (BS), we also aim at minimizing the latency of service requested by the users, while considering both open and closed access strategies. We show that the cell association problem is NP-hard, and propose several near-optimal solution algorithms for assigning users to BS s, including a sequential fixing algorithm, a rounding approximation algorithm, a greedy approximation algorithm, and a randomized algorithm. For service scheduling, we develop an optimal algorithm to minimize the average waiting time for the users associated with the same BS. The proposed algorithms are analyzed with respect to performance bounds, approximation ratios, and optimality, and are evaluated with simulations.

关键词： Approximation algorithm cell association femtocell load balancing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A general method for geometric feature matching and model extraction

引用

INTERNATIONAL JOURNAL OF COMPUTER VISION 2001年第1期45卷 39-54页

作者： Olson, CF Univ Washington Dept Comp & Software Syst Bothell WA 98011 USA

Popular algorithms for feature matching and model extraction fall into two broad categories: generate-and-test and Hough transform variations. However, both methods suffer from problems in practical implementations. Generate-and-test methods are sensitive to noise in the data. They often fail when the generated model fit is poor due to error in the data used to generate the model position. Hough transform variations are less sensitive to noise, but implementations for complex problems suffer from large time and space requirements and from the detection of false positives. This paper describes a general method for solving problems where a model is extracted from, or fit to, data that draws benefits from both generate-and-test methods and those based on the Hough transform, yielding a method superior to both. An important component of the method is the subdivision of the problem into many subproblems. This allows efficient generate-and-test techniques to be used, including the use of randomization to limit the number of subproblems that must be examined. Each subproblem is solved using pose space analysis techniques similar to the Hough transform, which lowers the sensitivity of the method to noise. This strategy is easy to implement and results in practical algorithms that are efficient and robust. We describe case studies of the application of this method to object recognition, geometric primitive extraction, robust regression, and motion segmentation.

关键词： divide-and-conquer feature matching generate-and-test geometric primitive extraction Hough transform model extraction motion segmentation object recognition randomized algorithm robust regression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：