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

local Approximability of Max-Min and Min-Max Linear Programs

THEORY OF COMPUTING SYSTEMS 2011年第4期49卷 672-697页

作者： Floreen, Patrik Hassinen, Marja Kaasinen, Joel Kaski, Petteri Musto, Topi Suomela, Jukka Univ Helsinki Helsinki Inst Informat Technol HIIT FIN-00014 Helsinki Finland

In a max-min LP, the objective is to maximise omega subject to A xa parts per thousand currency sign1, C xa parts per thousand yen omega 1, and xa parts per thousand yen0. In a min-max LP, the objective is to minimise rho subject to A xa parts per thousand currency sign rho 1, C xa parts per thousand yen1, and xa parts per thousand yen0. The matrices A and C are nonnegative and sparse: each row a (i) of A has at most Delta (I) positive elements, and each row c (k) of C has at most Delta (K) positive elements. We study the approximability of max-min LPs and min-max LPs in a distributed setting;in particular, we focus on local algorithms (constant-time distributed algorithms). We show that for any Delta (I) a parts per thousand yen2, Delta (K) a parts per thousand yen2, and epsilon > 0 there exists a local algorithm that achieves the approximation ratio Delta (I) (1-1/Delta (K) )+epsilon. We also show that this result is the best possible: no local algorithm can achieve the approximation ratio Delta (I) (1-1/Delta (K) ) for any Delta (I) a parts per thousand yen2 and Delta (K) a parts per thousand yen2.

关键词： Approximation algorithms Distributed algorithms Linear programs local algorithms

来源：评论

学校读者我要写书评

暂无评论

A Graphical μ—Calculus and local Model Checking

引用

Journal of Computer Science & Technology 2002年第6期17卷 665-671页

作者：林惠民 LaboratoryforComputerScience InstituteofSoftwareTheChineseAcademyofSciencesP.O.Box8718Beijing100080

A graphical notation for the propositionalμ-calculus, called modal graphs, ispresented. It is shown that both the textual and equational presentations of theμ-calculus canbe translated into modal graphs. A model checking algorithm based on such graphs is *** algorithm is truly local in the sense that it only generates the parts of the underlyingsearch space which are necessary for the computation of the final result. The correctness of thealgorithm is proven and its complexity analysed.

关键词： model checking μ-calculus modal graphs local algorithms

来源：评论

学校读者我要写书评

暂无评论

A simple local 3-approximation algorithm for vertex cover

引用

INFORMATION PROCESSING LETTERS 2009年第12期109卷 642-645页

作者： Polishchuk, Valentin Suomela, Jukka Aalto Univ HIIT FI-00014 Helsinki Finland Univ Helsinki FI-00014 Helsinki Finland

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering... 详细信息

关键词： Approximation algorithms Distributed computing Graph algorithms local algorithms

来源：评论

学校读者我要写书评

暂无评论

A local CLUSTERING ALGORITHM FOR MASSIVE GRAPHS AND ITS APPLICATION TO NEARLY LINEAR TIME GRAPH PARTITIONING

引用

SIAM JOURNAL ON COMPUTING 2013年第1期42卷 1-26页

作者： Spielman, Daniel A. Teng, Shang-Hua Yale Univ Dept Comp Sci Program Appl Math New Haven CT 06520 USA Univ So Calif Dept Comp Sci Viterbi Sch Engn Los Angeles CA 90089 USA

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster-a subset of vertices whose internal connections are significantly richer than its external connections-near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.

关键词： graph clustering graph partitioning local algorithms sparsest cut approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

local Computations on Triangular Graphs

引用

FUNDAMENTA INFORMATICAE 2010年第1-4期100卷 117-140页

作者： Mazurkiewicz, Antoni Polish Acad Sci Inst Comp Sci PL-01237 Warsaw Poland

The paper deals with the class of finite triangular graphs. It turns out that this class enjoys regular properties similar to those of trees and complete graphs. The main objective of the paper is to lift algorithms for some typical local computations, known for other classes of graphs, to the class of triangular graphs. local algorithms on graphs, according to [8, 9], are defined as local rules for relabeling graph nodes. Rules are local, if they are defined only for a class of subgraphs of processed graph (as neighborhoods of nodes or edges) and neither their results nor their applicability do not depend upon the knowledge of the whole graph labeling. While designing local algorithm for triangular graphs one needs to use some intrinsic properties of such graphs;it puts some additional light on their inherent structure. To illustrate essential features of local computations on triangular graphs, local algorithms for three typical issues of local computations are discussed: leader election, spanning tree construction, and nodes ordering. Correctness of these algorithms, as deadlock freeness, proper termination, and impartiality, are proved.

关键词： local algorithms triangular graphs leader elections spanning trees nodes orderings

来源：评论

学校读者我要写书评

暂无评论

Asynchronous local Construction of Bounded-Degree Network Topologies Using Only Neighborhood Information

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第3期67卷 2101-2113页

作者： Koyuncu, Erdem Jafarkhani, Hamid Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA Univ Calif Irvine Ctr Pervas Commun & Comp Irvine CA 92697 USA

We consider the ad-hoc networks consisting of n wireless nodes that are located on the plane. Any two given nodes are called neighbors if they are located within a certain distance (communication range) from one another. A given node can be directly connected to any one of its neighbors, and picks its connections according to a unique topology control algorithm that is available at every node. Given that each node knows only the indices (unique identification numbers) of its one and two-hop neighbors, we identify an algorithm that preserves connectivity and can operate without the need of any synchronization among nodes. Moreover, the algorithm results in a sparse graph with at most 5n edges and a maximum node degree of 10. Existing algorithms with the same promises further require neighbor distance and/or direction information at each node. We also evaluate the performance of our algorithm for random networks. In this case, our algorithm provides an asymptotically connected network with n(1+o(1)) edges with a degree less than or equal to 6 for 1-o(1) fraction of the nodes. We also introduce another asynchronous connectivity-preserving algorithm that can provide an upper bound as well as a lower bound on node degrees.

关键词： Topology control local algorithms connectivity degree-bounded graphs

来源：评论

学校读者我要写书评

暂无评论

A Generic local Algorithm for Mining Data Streams in Large Distributed Systems

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2009年第4期21卷 465-478页

作者： Wolff, Ran Bhaduri, Kanishka Kargupta, Hillol Univ Haifa Dept Management Informat Syst IL-31905 Haifa Israel NASA Ames Res Ctr Mission Crit Technol Inc IDU Grp Moffett Field CA 94035 USA Univ Maryland Dept Comp Sci & Elect Engn Baltimore MD 21250 USA AGNIK LLC Columbia MD 21045 USA

In a large network of computers or wireless sensors, each of the components (henceforth, peers) has some data about the global state of the system. Much of the system's functionality such as message routing, information retrieval, and load sharing relies on modeling the global state. We refer to the outcome of the function (e. g., the load experienced by each peer) as the model of the system. Since the state of the system is constantly changing, it is necessary to keep the models up to date. Computing global data mining models, e. g., decision trees, k-means clustering in large distributed systems may be very costly due to the scale of the system and due to communication cost, which may be high. The cost further increases in a dynamic scenario when the data changes rapidly. In this paper, we describe a two-step approach for dealing with these costs. First, we describe a highly efficient local algorithm that can be used to monitor a wide class of data mining models. Then, we use this algorithm as a feedback loop for the monitoring of complex functions of the data such as its k-means clustering. The theoretical claims are corroborated with a thorough experimental analysis.

关键词： Distributed data mining peer-to-peer local algorithms

来源：评论

学校读者我要写书评

暂无评论

A local updating algorithm for personalized PageRank via Chebyshev polynomials

引用

SOCIAL NETWORK ANALYSIS AND MINING 2022年第1期12卷 1-11页

作者： Bautista, Esteban Latapy, Matthieu Sorbonne Univ CNRS LIP6 F-75005 Paris France

The personalized PageRank algorithm is one of the most versatile tools for the analysis of networks. In spite of its ubiquity, maintaining personalized PageRank vectors when the underlying network constantly evolves is still a challenging task. To address this limitation, this work proposes a novel distributed algorithm to locally update personalized PageRank vectors when the graph topology changes. The proposed algorithm is based on the use of Chebyshev polynomials and a novel update equation that encompasses a large family of PageRank-based methods. In particular, the algorithm has the following advantages: (i) it has faster convergence speed than state-of-the-art alternatives for local personalized PageRank updating;and (ii) it can update the solution of recent extensions of personalized PageRank that rely on complex dynamical processes for which no updating algorithms have been developed. Experiments in a real-world temporal network of an autonomous system validate the effectiveness of the proposed algorithm.

关键词： PageRank Updating algorithms local algorithms Chebyshev polynomials Graph signal processing Semi-supervised learning

来源：评论

学校读者我要写书评

暂无评论

A local algorithm to compute multiple connected dominating sets in wireless sensor networks

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2011年第5期26卷 369-380页

作者： Islam, Kamrul Akl, Selim G. Queens Univ Sch Comp Kingston ON K7L 3N6 Canada

We investigate the problem of computing a family of connected dominating sets (CDSs) in wireless sensor networks (WSNs) in a distributed manner. Specifically, we present a local algorithm that computes a family S-1, S-2,..., S-m of non-trivial CDSs with the goal to maximise alpha = m / k, where k = max(u is an element of v) vertical bar{i : u is an element of S-i}vertical bar. In other words, we wish to find as many CDSs as possible, while minimising the number of frequencies of each node in these sets. Since CDSs play an important role for maximising network lifetime when they are used as backbones for broadcasting messages, maximising alpha reduces the possibility of repeatedly using the same subset of nodes as backbones. We provide an upper bound on the value of alpha via a 'nice' relationship between all minimum vertex-cuts and CDSs in the network graph, and present a local algorithm for the alpha maximisation problem. For a subclass of unit disk graphs (UDGs), it is shown that our algorithm achieves a constant approximation factor of the optimal solution. Here, a WSN is modelled as an UDG.

关键词： local algorithms multiple connected dominating sets maximum clique wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

local solutions for global problems in wireless networks

引用

JOURNAL OF DISCRETE algorithms 2007年第3期5卷 395-407页

作者： Urrutia, J. Univ Nacl Autonoma Mexico Inst Matematicas Mexico City DF Mexico

In this paper, we review a recently developed class of algorithms that solve global problems in unit distance wireless networks by means of local algorithms. A local algorithm is one in which any node of a network only has information on nodes at distance at most k from itself, for a constant k. For example, given a unit distance wireless network N, we want to obtain a planar subnetwork of N by means of an algorithm in which all nodes can communicate only with their neighbors in N, perform some operations, and then halt. We review algorithms for obtaining planar subnetworks, approximations to minimum weight spanning trees, Delaunay triangulations, and relative neighbor graphs. Given a unit distance wireless network N, we present new local algorithms to solve the following problems: 1. Calculate small dominating sets ( not necessarily connected) of N. 2. Extract a bounded degree planar subgraph H of N and obtain a proper edge coloring of H with at most 12 colors. The second of these algorithms can be used in the channel assignment problem. (C) 2007 Elsevier B.V. All rights reserved.

关键词： local algorithms Routing Ad hoc and wireless networks Dominating sets local vertex coloring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：