A generic framework for approximation analysis of greedy algorithms for star bicoloring

Abstract

This paper presents a generic framework for the design and comparison of polynomial-time approximation algorithms for MINIMUM STAR BICOLORING. This generic framework is parameterized by algorithms which produce sequences of distance-2 independent sets. As our main technical result we show that, when the parameterized algorithm produces sequences of distance-2 independent sets that remove at least $\mathrm{\Omega }(n^{ϵ})$ edges during each step, the generic framework produces a polynomial-time approximation algorithm for MINIMUM STAR BICOLORING that is always at least $O(n^{1-ϵ/(1+ϵ)})$ of optimal. Under the generic framework, we model two algorithms for MINIMUM STAR BICOLORING from the literature: Complete Direct Cover (CDC) [Hossain and Steihaug, Computing a sparse Jacobian matrix by rows and columns, Optim. Methods Softw. 10 (1998), pp. 33–48] and ASBC [Juedes and Jones, Coloring Jacobians revisited: A new algorithm for star and acyclic bicoloring, Optim. Methods Softw. 27(1–3) (2012), pp. 295–309]. We apply our main result to show approximation upper bounds of $O(n^{3/4})$ and $O(n^{2/3})$, respectively, for these two algorithms. Our approximation upper bound for CDC is the first known approximation analysis for this algorithm. In addition to modelling CDC and ASBC, we use the generic framework to build and analyze three new $O(n^{2/3})$ approximation algorithms for MINIMUM STAR BICOLORING: MAX-NEIGHBORHOOD, MAX-RATIO${}_c$, and LOCAL-SEARCH-k.

Keywords:

• Star bicoloring
• acyclic bicoloring
• automatic differentiation
• approximation algorithms

2010 Mathematics Subject Classifications:

• 68W25
• 68Q17

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 We say that a natural number $n_s\in \mathbb{N}$ is square if there exists an integer $i\in \mathbb{N}$ such that $n_s=i\ast i$. Hence, the statement ‘for every square $n_s\in \mathbb{N}$’ is shorthand for ‘for every $n_s\in \mathbb{N}$ such that there exists an $i\in \mathbb{N}$ with $n_s=i\ast i$.’