The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916466076418048 |
|---|---|
| author | Chen, Yeyuan |
| author_facet | Chen, Yeyuan |
| contents | The greedy algorithm adapted from Kruskal's algorithm is an efficient and folklore way to produce a $k$-spanner with girth at least $k+2$. The greedy algorithm has shown to be `existentially optimal', while it's not `universally optimal' for any constant $k$. Here, `universal optimality' means an algorithm can produce the smallest $k$-spanner $H$ given any $n$-vertex input graph $G$.
However, how well the greedy algorithm works compared to `universal optimality' is still unclear for superconstant $k:=k(n)$. In this paper, we aim to give a new and fine-grained analysis of this problem in undirected unweighted graph setting. Specifically, we show some bounds on this problem including the following two
(1) On the negative side, when $k<\frac{1}{3}n-O(1)$, the greedy algorithm is not `universally optimal'.
(2) On the positive side, when $k>\frac{2}{3}n+O(1)$, the greedy algorithm is `universally optimal'.
We also introduce an appropriate notion for `approximately universal optimality'. An algorithm is $(α,β)$-universally optimal iff given any $n$-vertex input graph $G$, it can produce a $k$-spanner $H$ of $G$ with size $|H|\leq n+α(|H^*|-n)+β$, where $H^*$ is the smallest $k$-spanner of $G$. We show the following positive bounds.
(1) When $k>\frac{4}{7}n+O(1)$, the greedy algorithm is $(2,O(1))$-universally optimal.
(2) When $k>\frac{12}{23}n+O(1)$, the greedy algorithm is $(18,O(1))$-universally optimal.
(3) When $k>\frac{1}{2}n+O(1)$, the greedy algorithm is $(32,O(1))$-universally optimal.
All our proofs are constructive building on new structural analysis on spanners. We give some ideas about how to break small cycles in a spanner to increase the girth. These ideas may help us to understand the relation between girth and spanners. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_01486 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner Chen, Yeyuan Data Structures and Algorithms Discrete Mathematics Combinatorics 05 The greedy algorithm adapted from Kruskal's algorithm is an efficient and folklore way to produce a $k$-spanner with girth at least $k+2$. The greedy algorithm has shown to be `existentially optimal', while it's not `universally optimal' for any constant $k$. Here, `universal optimality' means an algorithm can produce the smallest $k$-spanner $H$ given any $n$-vertex input graph $G$. However, how well the greedy algorithm works compared to `universal optimality' is still unclear for superconstant $k:=k(n)$. In this paper, we aim to give a new and fine-grained analysis of this problem in undirected unweighted graph setting. Specifically, we show some bounds on this problem including the following two (1) On the negative side, when $k<\frac{1}{3}n-O(1)$, the greedy algorithm is not `universally optimal'. (2) On the positive side, when $k>\frac{2}{3}n+O(1)$, the greedy algorithm is `universally optimal'. We also introduce an appropriate notion for `approximately universal optimality'. An algorithm is $(α,β)$-universally optimal iff given any $n$-vertex input graph $G$, it can produce a $k$-spanner $H$ of $G$ with size $|H|\leq n+α(|H^*|-n)+β$, where $H^*$ is the smallest $k$-spanner of $G$. We show the following positive bounds. (1) When $k>\frac{4}{7}n+O(1)$, the greedy algorithm is $(2,O(1))$-universally optimal. (2) When $k>\frac{12}{23}n+O(1)$, the greedy algorithm is $(18,O(1))$-universally optimal. (3) When $k>\frac{1}{2}n+O(1)$, the greedy algorithm is $(32,O(1))$-universally optimal. All our proofs are constructive building on new structural analysis on spanners. We give some ideas about how to break small cycles in a spanner to increase the girth. These ideas may help us to understand the relation between girth and spanners. |
| title | The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 05 |
| url | https://arxiv.org/abs/2411.01486 |