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

Foundation of Reactive local Topology Control

IEEE COMMUNICATIONS LETTERS 2015年第7期19卷 1213-1216页

作者： Neumann, Florentin Frey, Hannes Univ Koblenz Landau Dept Comp Sci D-56070 Koblenz Germany

We formalize the concept reactive (aka contention-based or beaconless) topology control and its underlying problem statement. By means of message complexity, we define the classes of O(k)- and Omega(k)-reactive topology control algorithms which allow us to distinguish reactive from conventional local approaches and to classify the former. Moreover, based on our formalisms we prove two fundamental propositions regarding the reactive computability of standard topology control structures. Thus, our contribution not only establishes a taxonomy for identification of research gaps, but constitutes a theoretical foundation for profound investigation of this algorithm classes' principal power.

关键词： Ad hoc wireless networks reactive beaconless on-demand topology control local algorithms

来源：评论

学校读者我要写书评

暂无评论

local Hadwiger's Conjecture

引用

JOURNAL OF COMBINATORIAL THEORY SERIES B 2023年第1期162卷 154-183页

作者： Moore, Benjamin Postle, Luke Turner, Lise Charles Univ Prague Comp Sci Inst Prague Czech Republic Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

We propose local versions of Hadwiger's Conjecture, where only balls of radius & omega;(log(v(G))) around each vertex are required to be Kt-minor-free. We ask: if a graph is locally-Ktminor-free, is it t-colourable? We show that the answer is yes when t & LE;5, even in the stronger setting of list-colouring, and we complement this result with a O(log v(G))-round distributed colouring algorithm in the local model. Further, we show that for large enough values of t, we can list-colour locally-Kt-minor-free graphs with 13 & BULL;max h(t), 1312 (t - 1)1}) colours, where h(t) is any value such that all Kt-minor-free graphs are h(t)-list-colourable. We again complement this with a O(log v(G))-round distributed algorithm. & COPY;2023 Published by Elsevier Inc.

关键词： Hadwiger's Conjecture Graph colouring Graph minors local algorithms

来源：评论

学校读者我要写书评

暂无评论

Constructing near spanning trees with few local inspections

引用

RANDOM STRUCTURES & algorithms 2017年第2期50卷 183-200页

作者： Levi, Reut Moshkovitz, Guy Ron, Dana Rubinfeld, Ronitt Shapira, Asaf MPI Informat D-66123 Saarbrucken Germany Tel Aviv Univ Sch Math IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded-degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph G consisting of (1+E)n edges (for a prespecified constant E>0), where the decision for different edges should be consistent with the same subgraph G. Can this task be performed by inspecting only a constant number of edges in G? Our main results are: We show that if every t-vertex subgraph of G has expansion 1/(logt)1+o(1) then one can (deterministically) construct a sparse spanning subgraph G of G using few inspections. To this end we analyze a local version of a famous minimum-weight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3-regular graphs of high girth, in which every t-vertex subgraph has expansion 1/(logt)1-o(1). We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183-200, 2017

关键词： graph expansion local algorithms sparse spanning graph

来源：评论

学校读者我要写书评

暂无评论

A local O(n²) Gathering Algorithm 10

A Local O(n<SUP>2</SUP>) Gathering Algorithm

引用

22nd ACM Symposium on Parallelism in algorithms and Architectures

作者： Degener, Bastian Kempkes, Barbara auf der Heide, Friedhelm Meyer Univ Gesamthsch Paderborn Dept Comp Sci Heinz Nixdorf Inst D-4790 Paderborn Germany

ISBN: (纸本)9781450300797

The gathering problem, where n autonomous robots with restricted capabilities are required to meet in a single point of the plane, is widely studied We consider the case that robots are limited to see only robots within a bounded vicinity and present an algorithm achieving gathering in O(n(2)) rounds in expectation A round consists of a movement of all robots, in random order. All previous algorithms with a proven time bound assume global view on the configuration of all robots

关键词： swarm robotics local algorithms distributed algorithms gathering geometric networks

来源：评论

学校读者我要写书评

暂无评论

An Optimal local Approximation Algorithm for Max-Min Linear Programs 09

An Optimal Local Approximation Algorithm for Max-Min Linear ...

引用

21st ACM Symposium on Parallelism in algorithms and Architectures

作者： Floreen, Patrik Kaasinen, Joel Kaski, Petteri Suomela, Jukka Univ Helsinki HIIT FI-00014 Helsinki Finland

In a max-min LP, the objective is to maximise omega subject to Ax = omega 1, and x >= 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min... 详细信息

ISBN: (纸本)9781605586069

In a max-min LP, the objective is to maximise omega subject to Ax <= 1, Cx >= omega 1, and x >= 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min Us. The approximation ratio Of Our algorithm is the best possible for any local algorithm;there is a matching unconditional lower bound.

关键词： local algorithms approximation algorithms linear programs

来源：评论

学校读者我要写书评

暂无评论

Computing Heat Kernel Pagerank and a local Clustering Algorithm 1

引用

25th International Workshop on Combinatorial algorithms (IWOCA)

作者： Chung, Fan Simpson, Olivia Univ Calif San Diego La Jolla CA 92093 USA

ISBN: (数字)9783319193151

ISBN: (纸本)9783319193151;9783319193144

Heat kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the heat kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time O(log(epsilon(-1)) log n/epsilon(3) log log(epsilon(-1))), assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with heat kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a heat kernel pagerank vector, using the heat kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset S of Cheeger ratio phi, many vertices in S may serve as seeds for a heat kernel pagerank vector which will find a cut of conductance O(root phi).

关键词： Heat kernel pagerank Heat kernel local algorithms

来源：评论

学校读者我要写书评

暂无评论

local Planar Domination Revisited 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Heydt, Ozan Siebertz, Sebastian Vigny, Alexandre Univ Bremen Bremen Germany

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

We show how to compute an (11 + epsilon) - approximation of a minimum dominating set in a planar graph in a constant number of rounds in the local model of distributed computing. This improves on the previously best known approximation factor of 52, which was achieved by an elegant and simple algorithm of Lenzen et al. Our algorithm combines ideas from the algorithm of Lenzen et al. with recent work of Czygrinow et al. and Kublenz et al. to reduce to the case of bounded degree graphs. We can then apply an LP-based approximation in a constant number of rounds. We also study a distributed version of the classical greedy algorithm, which however falls short of achieving the best approximation ratio.

关键词： Dominating set local algorithms Planar graphs

来源：评论

学校读者我要写书评

暂无评论

A local Scalable Distributed Expectation Maximization Algorithm for Large Peer-to-Peer Networks

A Local Scalable Distributed Expectation Maximization Algori...

引用

9th IEEE International Conference on Data Mining

作者： Bhaduri, Kanishka Srivastava, Ashok N. NASA Ames Res Ctr MCT Inc MS 269-2 Moffett Field CA 94035 USA NASA Ames Res Ctr Moffett Field CA 94035 USA

ISBN: (纸本)9781424452422

This paper describes a local and distributed expectation maximization algorithm for learning parameters of Gaussian mixture models (GMM) in large peer-to-peer (P2P) environments. The algorithm can be used for a variety of well-known data mining tasks in distributed environments such as clustering, anomaly detection, target tracking, and density estimation to name a few, necessary for many emerging P2P applications in bioinformatics, webmining and sensor networks. Centralizing all or some of the data to build global models is impractical in such P2P environments because of the large number of data sources, the asynchronous nature of the P2P networks, and dynamic nature of the data/network. The proposed algorithm takes a two-step approach. In the monitoring phase, the algorithm checks if the model 'quality' is acceptable by using an efficient local algorithm. This is then used as a feedback loop to sample data from the network and rebuild the GMM when it is outdated. We present thorough experimental results to verify our theoretical claims.

关键词： peer-to-peer local algorithms expectation maximization

来源：评论

学校读者我要写书评

暂无评论

Scalable, Optimal Flow Routing in Datacenters via local Link Balancing 13

Scalable, Optimal Flow Routing in Datacenters via Local Link...

引用

ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT)

作者： Sen, Siddhartha Shue, David Ihm, Sunghwan Freedman, Michael J. Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9781450321013

Datacenter networks should support high network utilization. Yet today's routing is typically load agnostic, so large flows can starve other flows if routed through overutilized links. Even recent proposals like centralized scheduling or end-host multi-pathing give suboptimal throughput, and they suffer from poor scalability and other limitations. We present a simple, switch-local algorithm called localFlow that is optimal (under standard assumptions), scalable, and practical. Although localFlow may split an individual flow (this is necessary for optimality), it does so infrequently by considering the aggregate flow per destination and allowing slack in distributing this flow. We use an optimization decomposition to prove localFlow's optimality when combined with unmodified end hosts' TCP. Splitting flows presents several new technical challenges that must be overcome in order to interact efficiently with TCP and work on emerging standards for programmable, commodity switches. Since localFlow acts independently on each switch, it is highly scalable, adapts quickly to dynamic workloads, and admits flexible deployment strategies. We present detailed packet-level simulations comparing localFlow to a variety of alternative schemes, on real datacenter workloads.

关键词： Flow routing Datacenter networks local algorithms Optimization decomposition

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: local Independent Set Approximation 16

Brief Announcement: Local Independent Set Approximation

引用

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

作者： Bodlaender, Marijke H. L. Halldorsson, Magnus M. Konrad, Christian Kuhn, Fabian Reykjavik Univ Sch Comp Sci ICE TCS Reykjavik Iceland Univ Freiburg Dept Comp Sci Freiburg Germany

We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(nε)-approximation algorithm for the maximum independent set problem that operates in O(1/&#... 详细信息

ISBN: (纸本)9781450339643

关键词： local algorithms maximum independent set network decompositions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：