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{ \gamma}_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{ \gamma}^j$ is a probability distribution over $r_j$ elements, for $1\leq j \leq N$. Our main theorem asserts that for any $\alpha>0$, $$\lim_{ k \rightarrow \infty } \frac{ 1}{ k} \cdot \ln p(\lfloor{ \alpha k}\rfloor,k) = -\max_{ 1\leq j \leq N} M_j,$$ where $M_j$ depends only on $\alpha$, $\bar{ \gamma}^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.
Categories: cs.DS