5 results on '"APPROXIMATION algorithms"'
Search Results
2. SUBLINEAR TIME ESTIMATION OF DEGREE DISTRIBUTION MOMENTS: THE ARBORICITY CONNECTION.
- Author
-
EDEN, TALYA, RON, DANA, and SESHADHRI, C.
- Subjects
- *
TIME perception , *ALGORITHMS , *QUERY (Information retrieval system) , *DEGREES of freedom , *UNDIRECTED graphs , *MATHEMATICS - Abstract
We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
3. Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
- Author
-
Dory, Michal, Ghaffari, Mohsen, and Ilchi, Saeed
- Subjects
FOS: Computer and information sciences ,Computer Networks and Communications ,Arboricity ,Distributed computing ,Approximation algorithms ,Theoretical Computer Science ,Dominating set ,Computational Theory and Mathematics ,Computer Science - Distributed, Parallel, and Cluster Computing ,Hardware and Architecture ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,Distributed, Parallel, and Cluster Computing (cs.DC) ,Distributed Computing ,Dominating Set ,Approximation Algorithms - Abstract
We describe a simple deterministic O(e-1 log A) round distributed algorithm for (2a + 1)(1 + e) approximation of minimum weighted dominating set on graphs with arboricity at most a. Here A denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O(a(2)) approximation in O(log n) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic O(a log ?) approximation in O(log A) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic O(a) approximation in O(log(2)?) rounds (implicit in Bansal et al. in Inform Process Lett 122:21-24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized O(a) approximation in O(a log n) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized O(a log ?) round distributed algorithm that sharpens the approximation factor to a (1 + o(1)). If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve a - 1 - e approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017)., Distributed Computing, ISSN:0178-2770, ISSN:1432-0452
- Published
- 2022
4. Tight approximation bounds for dominating set on graphs of bounded arboricity
- Author
-
Seeun William Umboh, Nikhil Bansal, Discrete Mathematics, and Combinatorial Optimization 1
- Subjects
Matching (graph theory) ,0102 computer and information sciences ,02 engineering and technology ,Hardness of approximation ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Dominating set ,Computer Science::Discrete Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Data Structures and Algorithms ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) ,Computer Science::Distributed, Parallel, and Cluster Computing ,Complement (set theory) ,Mathematics ,Discrete mathematics ,Quantitative Biology::Neurons and Cognition ,Rounding ,Arboricity ,Approximation algorithm ,Approximation algorithms ,Computer Science Applications ,010201 computation theory & mathematics ,Bounded function ,Signal Processing ,020201 artificial intelligence & image processing ,Bounded arboricity ,Information Systems - Abstract
We consider the minimum dominating set problem on graphs with bounded arboricity. For graphs with arboricity a, we give an LP rounding algorithm that achieves an approximation factor of 3a and we complement this with a matching (up to constants) hardness of approximation result.
- Published
- 2017
5. Approximating k-spanner problems fork>2
- Author
-
David Peleg and Michael Elkin
- Subjects
Discrete mathematics ,Spanning tree ,General Computer Science ,Sublinear function ,Logarithm ,Arboricity ,Spanner ,Approximation algorithm ,Approximation algorithms ,Theoretical Computer Science ,Combinatorics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Algorithmics ,Bounded function ,Graph algorithms ,Computer Science::Data Structures and Algorithms ,Spanners ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Given a graph G = (V, E), a subgraph G' = (V, H), H ⊆ E is a k-spanner of G if for any pair of vertices u, w ∈ V it satisfies dH(u, w) ≤ kdG(u, w). The basic k-spanner problem is to find a k-spanner of a given graph G with the smallest possible number of edges. This paper considers approximation algorithms for this and some related problems for k > 2, known to be Ω(2log1-µn)-inapproximable. The basic k-spanner problem over undirected graphs with k > 2 has been given a sublinear ratio approximation algorithm (with ratio roughly O(n2/(k+1))), but no such algorithms were known for other variants of the problem, including the directed and the client-server variants, as well as for the related k-DSS problem. We present the first approximation algorithms for these problems with sublinear approximation ratio. The second contribution of this paper is in characterizing some wide families of graphs on which the problems do admit a logarithmic and a polylogarithmic approximation ratios. These families are characterized as containing graphs that have optimal or "near-optimal" spanners with certain desirable properties, such as being a tree, having low arboricity or having low girth. All our results generalize to the directed and the client-server variants of the problems. As a simple corollary, we present an algorithm that given a graph G builds a subgraph with O(n) edges and stretch bounded by the tree-stretch of G, namely the minimum maximal stretch of a spanning tree for G. The analysis of our algorithms involves the novel notion of edge-dominating systems developed in the paper. The technique introduced in the paper reduces the studied algorithmic approximability questions on k-spanners to purely graph-theoretical questions concerning the existence of certain combinatorial objects in families of graphs.
- Published
- 2005
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.