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

Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms

THEORETICAL COMPUTER SCIENCE 2007年第1-3期381卷 183-196页

作者： Parnas, Michal Ron, Dana Acad Coll Tel Aviv Yaffo Sch Comp Sci Tel Aviv Israel Tel Aviv Univ Dept EE Syst Ramat Aviv Israel

For a given graph G over n vertices, let OPTG denote the size of an optimal solution in G of a particular minimization problem (e.g., the size of a minimum vertex cover). A randomized algorithm will be called an alpha-approximation algorithm with an additive error for this minimization problem if for any given additive error parameter epsilon > 0 it computes a value (OPT) over tilde such that, with probability at least 2/3, it holds that OPTG <= (OPT) over tilde <= alpha .OPTG + epsilon n. Assume that the maximum degree or average degree of G is bounded. In this case, we show a reduction from local distributed approximation algorithms for the vertex cover problem to sublinear approximation algorithms for this problem. This reduction can be modified easily and applied to other optimization problems that have local distributed approximation algorithms, such as the dominating set problem. We also show that for the minimum vertex cover problem, the query complexity of such approximation algorithms must grow at least linearly with the average degree (d) over bar of the graph. This lower bound holds for every multiplicative factor alpha and small constant epsilon as long as (d) over bar = O(n/alpha). In particular this means that for dense graphs it is not possible to design an algorithm whose complexity is o(n). (c) 2007 Elsevier B.V. All rights reserved.

关键词： sublinear approximation algorithms distributed algorithms minimum vertex cover

来源：评论

学校读者我要写书评

暂无评论

Best of two local models: Centralized local and distributed local algorithms

引用

INFORMATION AND COMPUTATION 2018年第Part1期262卷 69-89页

作者： Even, Guy Medina, Moti Ron, Dana Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Ben Gurion Univ Negev Dept Elect & Comp Engn IL-8410501 Beer Sheva Israel

We consider two models of computation: centralized local algorithms and local distributed algorithms. algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in log* n, where n is the number of vertices of the input graph. The recursive centralized local improvement technique by Nguyen and Onak (FOCS 2008) is employed to obtain a distributed approximation scheme for maximum (weighted) matching. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Centralized local algorithms sublinear approximation algorithms Graph algorithms Distributed local algorithms Maximum matching Maximum weighted matching

来源：评论

学校读者我要写书评

暂无评论

Deterministic Stateless Centralized Local algorithms for Bounded Degree Graphs

引用

22nd Annual European Symposium on algorithms (ESA) held as part of ALGO Meeting

作者： Even, Guy Medina, Moti Ron, Dana Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

ISBN: (纸本)9783662447772;9783662447765

We design centralized local algorithms for: maximal independent set, maximal matching, and graph coloring. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes is O(log* n), where n is the number of vertices of the input graph. Our algorithms for maximal independent set and maximal matching improves over previous randomized algorithms by Alon et al. (SODA 2012) and Mansour et al. (ICALP 2012). In these previous algorithms, the number of probes and the space required for storing the state between queries are poly(log n). We also design the first centralized local algorithm for graph coloring. Our graph coloring algorithms are deterministic and stateless. Let Delta denote the maximum degree of a graph over n vertices. Our algorithm for coloring the vertices by Delta + 1 colors requires O(log* n) probes for constant degree graphs. Surprisingly, for the case where the number of colors is O(Delta(2) log.), the number of probes of our algorithm is O(Delta . log* n + Delta(2)), that is, the number of probes is sublinear if Delta = o(root n), i.e., our algorithm applies for graphs with unbounded degrees.

关键词： Centralized Local algorithms sublinear approximation algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating the Distance to Properties in Bounded-Degree and General Sparse Graphs

引用

ACM TRANSACTIONS ON algorithms 2009年第2期5卷 1–28页

作者： Marko, Sharon Ron, Dana Tel Aviv Univ Dept Elect Engn Syst IL-69978 Tel Aviv Israel

We address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property P. That is, we are interested in sublinear algorithms for estimating the fraction of edge modifications (additions or deletions) that must be performed on a graph so that it obtains P. This fraction is taken with respect to a given upper bound m on the number of edges. In particular, for graphs with degree bound d over n vertices, m = dn. To perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex. The problem of estimating the distance to having a property was first explicitly addressed by Parnas et al. [2006]. In the context of graphs this problem was studied by Fischer and Newman [2007] in the dense graphs model. In this model the fraction of edge modifications is taken with respect to n(2), and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. Fischer and Newman showed that every graph property that has a testing algorithm in this model, with query complexity independent of the size of the graph, also has a distance approximation algorithm with query complexity that is independent of the size of graph. In this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties shown to have efficient testing algorithms by Goldreich and Ron [2002]. Specifically, these properties are k-edge connectivity, subgraph freeness (for constant-size subgraphs), being an Eulerian graph, and cycle freeness. A variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. This approximation improves on a recent result of Parnas and Ron [2007].

关键词： sublinear approximation algorithms property testing distance approximation graph properties

来源：评论

学校读者我要写书评

暂无评论

Approximating the Distance to Monotonicity in High Dimensions

引用

ACM TRANSACTIONS ON algorithms 2010年第3期6卷 1–37页

作者： Fattal, Shahar Ron, Dana Tel Aviv Univ Dept Engn IL-69978 Tel Aviv Israel

In this article we study the problem of approximating the distance of a function f : [n](d) -> R to monotonicity where [n] = {1,..., n} and R is some fully ordered range. Namely, we are interested in randomized sublinear algorithms that approximate the Hamming distance between a given function and the closest monotone function. We allow both an additive error, parameterized by d, and a multiplicative error. Previous work on distance approximation to monotonicity focused on the one-dimensional case and the only explicit extension to higher dimensions was with a multiplicative approximation factor exponential in the dimension d. Building on Goldreich et al. [2000] and Dodis et al. [1999], in which there are better implicit results for the case n = 2, we describe a reduction from the case of functions over the d-dimensional hypercube [n](d) to the case of functions over the k-dimensional hypercube [n](k), where 1 <= k <= d. The quality of estimation that this reduction provides is linear in inverted right perpendiculard/kinverted left perpendicular and logarithmic in the size of the range vertical bar R vertical bar (if the range is infinite or just very large, then log vertical bar R vertical bar can be replaced by d log n). Using this reduction and a known distance approximation algorithm for the one-dimensional case, we obtain a distance approximation algorithm for functions over the d-dimensional hypercube, with any range R, which has a multiplicative approximation factor of O(d log vertical bar R vertical bar). For the case of a binary range, we present algorithms for distance approximation to monotonicity of functions over one dimension, two dimensions, and the k-dimensional hypercube (for any k >= 1). Applying these algorithms and the reduction described before, we obtain a variety of distance approximation algorithms for Boolean functions over the d-dimensional hypercube which suggest a trade-off between quality of estimation and efficiency of computation. In p

关键词： algorithms Theory sublinear approximation algorithms property testing distance approximation monotonicity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：