Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916782511489024 |
|---|---|
| author | Kulik, Ariel Shachnai, Hadas |
| author_facet | Kulik, Ariel Shachnai, Hadas |
| contents | In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random $1.5$-approximation algorithm for Vertex Cover, whose running time of $\tilde{O}(1.01657^k)$ substantially improves the best known runnning time of $\tilde{O}(1.0883^k)$ [Brankovic and Fernau, 2013]. For $3$-Hitting Set we present a parameterized random $2$-approximation algorithm with running time of $\tilde{O}(1.0659^k)$, improving the best known $\tilde{O}(1.29^k)$ algorithm of [Brankovic and Fernau, 2012].
The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations of the form: $$p(b,k) = \min_{1\leq j \leq N} \sum_{i=1}^{r_j} \barγ_i^j \cdot p(b-\bar{b}^j_i, k-\bar{k}_i^j),$$ where $\bar{b}^j$ and $\bar{k}^j$ are vectors of natural numbers, and $\barγ^j$ is a probability distribution over $r_j$ elements, for $1\leq j \leq N$. Our main theorem asserts that for any $α>0$, $$\lim_{k \rightarrow \infty } \frac{1}{k} \cdot \ln p(\lfloor{αk}\rfloor,k) = -\max_{1\leq j \leq N} M_j,$$
where $M_j$ depends only on $α$, $\barγ^j$, $\bar{b}^j$ and $\bar{k}^j$, and can be efficiently calculated by solving a simple numerical optimization problem. To prove the theorem we show an equivalence between the recurrence and a stochastic process. We analyze this process using the {\em method of types}, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1911_02653 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations Kulik, Ariel Shachnai, Hadas Data Structures and Algorithms In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random $1.5$-approximation algorithm for Vertex Cover, whose running time of $\tilde{O}(1.01657^k)$ substantially improves the best known runnning time of $\tilde{O}(1.0883^k)$ [Brankovic and Fernau, 2013]. For $3$-Hitting Set we present a parameterized random $2$-approximation algorithm with running time of $\tilde{O}(1.0659^k)$, improving the best known $\tilde{O}(1.29^k)$ algorithm of [Brankovic and Fernau, 2012]. The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations of the form: $$p(b,k) = \min_{1\leq j \leq N} \sum_{i=1}^{r_j} \barγ_i^j \cdot p(b-\bar{b}^j_i, k-\bar{k}_i^j),$$ where $\bar{b}^j$ and $\bar{k}^j$ are vectors of natural numbers, and $\barγ^j$ is a probability distribution over $r_j$ elements, for $1\leq j \leq N$. Our main theorem asserts that for any $α>0$, $$\lim_{k \rightarrow \infty } \frac{1}{k} \cdot \ln p(\lfloor{αk}\rfloor,k) = -\max_{1\leq j \leq N} M_j,$$ where $M_j$ depends only on $α$, $\barγ^j$, $\bar{b}^j$ and $\bar{k}^j$, and can be efficiently calculated by solving a simple numerical optimization problem. To prove the theorem we show an equivalence between the recurrence and a stochastic process. We analyze this process using the {\em method of types}, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this paper. |
| title | Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1911.02653 |