A generic framework for approximation analysis of greedy algorithms for star bicoloring. (4th July 2021)

• Record Type: Journal Article
• Authors: Juedes, David W.; Jones, Jeffrey S.
• Is Part Of: Optimization methods and software. Volume 36:Number 4(2021)
• Page Start: 869
• Page End: 890
• Publication Date: 2021-07-04
• Subjects: Star bicoloring -- acyclic bicoloring -- automatic differentiation -- approximation algorithms; 68W25 -- 68Q17; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1649671
• Languages: English
• ISSNs: 1055-6788

Abstract

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 Ω ( 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 .