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 topolo...
详细信息
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.
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-colou...
详细信息
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.
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 conn...
详细信息
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
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 with...
详细信息
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
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.
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 algorith...
详细信息
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).
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 k...
详细信息
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.
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 variet...
详细信息
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.
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 c...
详细信息
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.
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
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/ε) rounds, and we give a matching lower bound that holds even for bipartite graphs.
暂无评论