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 edges during each step, the generic framework produces a polynomial-time approximation algorithm for MINIMUM STAR BICOLORING that is always at least
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
and
, 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
approximation algorithms for MINIMUM STAR BICOLORING: MAX-NEIGHBORHOOD, MAX-RATIO
, and LOCAL-SEARCH-k.
Disclosure statement
No potential conflict of interest was reported by the authors.
Notes
1 We say that a natural number is square if there exists an integer
such that
. Hence, the statement ‘for every square
’ is shorthand for ‘for every
such that there exists an
with
.’