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

local algorithms for Sparse Spanning Graphs

ALGORITHMICA 2020年第4期82卷 747-786页

作者： Levi, Reut Ron, Dana Rubinfeld, Ronitt Weizmann Inst Sci Rehovot Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel MIT CSAIL Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most (1+ epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be Omega (root n). This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is poly(1/epsilon, h) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.

关键词： Sublinear algorithms local algorithms Sparse spanning subgraphs Minor-free graphs Property testing Bounded degree model

来源：评论

学校读者我要写书评

暂无评论

local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree

引用

RANDOM STRUCTURES & algorithms 2023年第3期63卷 689-715页

作者： El Alaoui, Ahmed Montanari, Andrea Sellke, Mark Cornell Univ Dept Stat & Data Sci Ithaca NY 14850 USA Stanford Univ Dept Elect Engn Stanford CA USA Stanford Univ Dept Stat Stanford CA USA Stanford Univ Dept Math Stanford CA USA

Given a graph G of degree k over n vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth 2L, we develop a local message passing algorithm whose complexity is O(nkL), and that achieves near optimal cut values among all L-local algorithms. Focusing on max-cut, the algorithm constructs a cut of value nk/4 + nP* root k/4 + err(n, k, L), where P-star approximate to 0.763166 is the value of the Parisi formula from spin glass theory, and err(n, k, L) = o(n)(n) + no(k)(root k) + n root ko(L)(1) (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, that is, graphs whose girth becomes 2L after removing a small fraction of vertices. Earlier work established that, for random k-regular graphs, the typical v v max-cut value is nk/4 + nP(star) root k/4 + o(n)(n) + no(k)(root k). Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max-cut, and nearly maximum min-bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near-Ramanujan property of random regular graphs.

关键词： graph partionning maximum cut minimum bisection local algorithms message passing

来源：评论

学校读者我要写书评

暂无评论

local algorithms for Block Models with Side Information 16

Local Algorithms for Block Models with Side Information

引用

7th ACM Conference on Innovations in Theoretical Computer Science (ITCS)

作者： Mossel, Elchanan Xu, Jiaming Univ Penn Dept Stat Philadelphia PA 19104 USA Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9781450340571

There has been a recent interest in understanding the power of local algorithms for optimization and inference problems on sparse graphs. Gamarnik and Sudan (2014) showed that local algorithms are weaker than global algorithms for finding large independent sets in sparse random regular graphs thus refuting a conjecture by Hatami, Lovasz, and Szegedy (2012). Montanari (2015) showed that local algorithms are suboptimal for finding a community with high connectivity in the sparse Erdos-Renyi random graphs. For the symmetric planted partition problem (also named community detection for the block models) on sparse graphs, a simple observation is that local algorithms cannot have non-trivial performance. In this work we consider the effect of side information on local algorithms for community detection under the binary symmetric stochastic block model. In the block model with side information each of the n vertices is labeled + or independently and uniformly at random;each pair of vertices is connected independently with probability a/n if both of them have the same label or b/n otherwise. The goal is to estimate the underlying vertex labeling given 1) the graph structure and 2) side information in the form of a vertex labeling positively correlated with the true one. Assuming that the ratio between in and out degree a/b is 0(1) and the average degree (a + b)/2 = n (1), we show that a local algorithm, namely, belief propagation run on the local neighborhoods, maximizes the expected fraction of vertices labeled correctly in the following three regimes: center dot broken vertical bar a -b broken vertical bar < 2 and all 0 < alpha 1/2 center dot (a-b)(2) > C(a+b) for some constant C and all 0 < alpha < 1/2 center dot For all a,b if the probability that each given vertex label is incorrect is at most alpha(*) for some constant alpha(*) is an element of (0,1/2). Thus, in contrast to the case of independent sets or a single community in random graphs and to the case of symmetri

关键词： local algorithms random graphs community detection

来源：评论

学校读者我要写书评

暂无评论

local algorithms for Sensor Selection 15

Local Algorithms for Sensor Selection

引用

15th ACM International Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (ACM PE-WASUN)

作者： Shamoun, Simon Tu, Tianyi Abdelzaher, Tarek Bar-Noy, Amotz CUNY New York NY 10021 USA CUNY Brooklyn Coll Brooklyn NY 11210 USA Univ Illinois Urbana IL 61801 USA

ISBN: (纸本)9781450359610

We study local algorithms for sensor selection, in which each sensor in a network uses information from nearby sensors alone to decide if it should be selected to predict the data of non-selected sensors. Our goal is to show how the prediction quality can be improved by increasing the level of knowledge available to each sensor. We specifically study this for a graph model of the network, in which prediction quality is defined by virtual links between sensors. Each node knows the links along all paths of fixed length extending outward from itself. The maximum path length increases with the level of knowledge. We designed algorithms for the first few levels and evaluated them on randomly generated graphs and real datasets, determining the optimal parameters for each algorithm and comparing them to baseline global strategies. Our results show that just knowing the links to immediate neighbors is enough to be as good as a simple global greedy algorithm, and increasing the knowledge improves the selection quality.

关键词： sensor selection local algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic local algorithms, unique identifiers, and fractional graph colouring

引用

THEORETICAL COMPUTER SCIENCE 2016年第PartB期610卷 204-217页

作者： Hasemann, Henning Hirvonen, Juho Rybicki, Joel Suomela, Jukka TU Braunschweig Inst Operating Syst & Comp Networks Braunschweig Germany Helsinki Inst Informat Technol HIIT Helsinki Finland Aalto Univ Dept Informat & Comp Sci Espoo Finland Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

In the fractional graph colouring problem, the task is to schedule the activities of the nodes so that each node is active for 1 time unit in total, and at each point of time the set of active nodes forms an independent set. We show that for any alpha > 1 there exists a deterministic distributed algorithm that finds a fractional graph colouring of length at most alpha(Delta + 1) in any graph in one synchronous communication round;here 4 is the maximum degree of the graph. The result is near-tight, as there are graphs in which the optimal solution has length Delta + 1. The result is, of course, too good to be true. The usual definitions of scheduling problems (fractional graph colouring, fractional domatic partition, etc.) in a distributed setting leave a loophole that can be exploited in the design of distributed algorithms: the size of the local output is not bounded. Our algorithm produces an output that seems to be perfectly good by the usual standards but it is impractical, as the schedule of each node consists of a very large number of short periods of activity. More generally, the algorithm demonstrates that when we study distributed algorithms for scheduling problems, we can choose virtually any trade-off between the following three parameters: T, the running time of the algorithm, l, the length of the schedule, and K, the maximum number of periods of activity for any single node. Here l is the objective function of the optimisation problem, while K captures the "subjective" quality of the solution. If we study, for example, bounded-degree graphs, we can trivially keep T and K constant, at the cost of a large l, or we can keep K and l constant, at the cost of a large T. Our algorithm shows that yet another trade-off is possible: we can keep T and l constant at the cost of a large K. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Distributed algorithms Fractional domatic partition Fractional graph colouring local algorithms Unique identifiers

来源：评论

学校读者我要写书评

暂无评论

Systems of fixpoint equations: Abstraction, games, up-to techniques and local algorithms

引用

INFORMATION AND COMPUTATION 2024年 301卷

作者： Baldan, Paolo Koenig, Barbara Padoan, Tommaso Univ Padua Padua Italy Univ Duisburg Essen Essen Germany Univ Trieste Trieste Italy

Systems of fixpoint equations over complete lattices, which combine least and greatest fixpoints, often arise from verification tasks such as model checking and behavioural equivalence checking. In this paper we develop a theory of approximation in the style of abstract interpretation, where a system over some concrete domain is abstracted into a system on a suitable abstract domain, ensuring sound and possibly complete over-approximations of the solutions. We also show how up-to techniques, commonly used to simplify coinductive proofs, fit into this framework, interpreted as abstractions. Additionally, we characterise the solution of fixpoint equation systems through parity games, extending prior work limited to continuous lattices. This game-based approach allows for local algorithms that verify system properties, such as determining whether a state satisfies a formula or two states are behaviourally equivalent. We describe a local algorithm, that can be combined with abstraction and up-to techniques to speed up the computation. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by/4.0/).

关键词： Fixpoint equation systems Complete lattices Parity games Abstract interpretation Up-to techniques local algorithms mu-calculus Bisimilarity

来源：评论

学校读者我要写书评

暂无评论

A STRUCTURAL THEOREM FOR local algorithms WITH APPLICATIONS TO CODING, TESTING, AND VERIFICATION

引用

SIAM JOURNAL ON COMPUTING 2023年第6期52卷 1413-1463页

作者： Dall'Agnol, Marcel Gur, Tom Lachish, Oded Univ Warwick Coventry CV4 7AL W Midlands England Birkbeck Univ London Comp Sci & Informat Syst London WC1E 7HX England

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and probabilistically checkable proofs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with n(1-1/O(q2 log 2 q)) sample complexity, following the definition of Goldreich and Ron [ACM Trans. Comput. Theory, 8 (2016), 7]. We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacypreserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following. We strengthen the stateof-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity;this resolves an open problem raised by Gur and Lachish [SIAM J. Comput., 50 (2021), pp. 788-813]. We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity;this resolves a problem left open in a work of Fischer, Lachish, and Vasudev [Proceedings of the 56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, pp. 1163-1182], bypassing an exponential blowup caused by previous techniques in the case of adaptive testers. We prove that the known separation between proofs of proximity and testers is essentially maximal;this resolves a problem left open by Gur and Rothblum [Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017, pp. 39:1-39:43;Comput. Complexity, 27 (2018), pp. 99-207] regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal-Szemeredi theorem.

关键词： local algorithms sample-based algorithms coding theory property testing adaptivity sunflower lemmas

来源：评论

学校读者我要写书评

暂无评论

Analysing local algorithms in location-aware quasi-unit-disk graphs

引用

DISCRETE APPLIED MATHEMATICS 2011年第15期159卷 1566-1580页

作者： Hassinen, Marja Kaasinen, Joel Kranakis, Evangelos Polishchuk, Valentin Suomela, Jukka Wiese, Andreas Univ Helsinki HIIT FIN-00014 Helsinki Finland Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Tech Univ Berlin Inst Math D-10623 Berlin Germany

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds;here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs. which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs. (C) 2011 Published by Elsevier B.V.

关键词： Geometric graphs local algorithms local horizon Location-aware nodes Quasi-unit-disk graphs

来源：评论

学校读者我要写书评

暂无评论

SUBOPTIMALITY OF local algorithms FOR A CLASS OF MAX-CUT PROBLEMS

引用

ANNALS OF PROBABILITY 2019年第3期47卷 1587-1618页

作者： Chen, Wei-Kuo Gamarnik, David Panchenko, Dmitry Rahman, Mustazee Univ Minnesota Sch Math Minneapolis MN 55455 USA Univ Toronto Dept Math Toronto ON Canada MIT Sloan Sch Management Cambridge MA 02139 USA MIT Dept Math Cambridge MA 02139 USA

We show that in random K-uniform hypergraphs of constant average degree, for even K >= 4, local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used frequently to obtain lower bounds for the max-cut problem on random graphs, but it was not known whether they could be successful in finding nearly maximal cuts. This result follows from the fact that the overlap of any two nearly maximal cuts in such hypergraphs does not take values in a certain nontrivial interval-a phenomenon referred to as the overlap gap property-which is proved by comparing diluted models with large average degree with appropriate fully connected spin glass models and showing the overlap gap property in the latter setting.

关键词： local algorithms maximum cut problems spin glasses

来源：评论

学校读者我要写书评

暂无评论

Properties of regular graphs with large girth via local algorithms

引用

JOURNAL OF COMBINATORIAL THEORY SERIES B 2016年 121卷 367-397页

作者： Hoppen, Carlos Wormald, Nicholas Univ Fed Rio Grande do Sul Inst Matemat BR-90046900 Porto Alegre RS Brazil Monash Univ Sch Math Sci Clayton Vic 3800 Australia

The average-case analysis of probabilistic algorithms has proved to be very successful for finding asymptotic bounds on parameters of random regular graphs. Recently, the authors obtained a general transfer result which translates such bounds into (deterministic) results about all regular graphs with sufficiently large girth. In this paper, we apply this methodology to obtain new upper or lower bounds on the size of maximum independent sets and power dominating sets in cubic graphs with large girth, and maximum cuts, maximum and minimum bisections, and minimum connected and weakly-connected dominating sets in r-regular graphs with large girth. All the new bounds improve upon the best previous bounds. For independent sets in cubic graphs, this also improves on the best "almost sure" bounds for random cubic graphs. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Large-girth graphs Random regular graphs local algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：