Publication: Coloring Jacobians revisited: a new algorithm for star and acyclic bicoloring
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Coloring Jacobians revisited: a new algorithm for star and acyclic bicoloring

- Article in a journal -
 

Author(s)
David Juedes , Jeffrey Jones

Published in
Optimization Methods and Software

Year
2012

Abstract
This paper presents a new polynomial-time algorithm, approximate star bicoloring (ASBC), for star bicoloring and acyclic bicoloring. These NP-complete combinatorial problems arise from problems associated with computing large sparse Jacobian matrices. The main results of this paper lie in approximation analysis related to these problems. In particular, it is shown that (i) both star and acyclic bicoloring can be approximated in polynomial time to the ratio O(n 2/3) and (ii) both star and acyclic bicoloring cannot be approximated to the ratio O(n 1/3-e) in polynomial time under reasonable complexity theoretic hypotheses. The ASBC algorithm is also analysed experimentally on a collection of realistic test cases from the Harwell–Boeing sparse matrix collection. The experimental results indicate that ASBC performs quite well in practice; the performance of the new algorithm always fell within the range of 1.53 and 6 times optimal on the given test sets.

AD Theory and Techniques
Combinatorics, Sparsity

BibTeX
@ARTICLE{
         Juedes2012CJr,
       author = "Juedes, David and Jones, Jeffrey",
       title = "Coloring {J}acobians revisited: a new algorithm for star and acyclic bicoloring",
       journal = "Optimization Methods and Software",
       volume = "27",
       number = "2",
       pages = "295--309",
       year = "2012",
       doi = "10.1080/10556788.2011.606575",
       url = "http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.606575",
       eprint = "http://www.tandfonline.com/doi/pdf/10.1080/10556788.2011.606575",
       abstract = "This paper presents a new polynomial-time algorithm, approximate star bicoloring
         (ASBC), for star bicoloring and acyclic bicoloring. These NP-complete combinatorial problems arise
         from problems associated with computing large sparse Jacobian matrices. The main results of this
         paper lie in approximation analysis related to these problems. In particular, it is shown that (i)
         both star and acyclic bicoloring can be approximated in polynomial time to the ratio O(n 2/3) and
         (ii) both star and acyclic bicoloring cannot be approximated to the ratio O(n 1/3-e) in polynomial
         time under reasonable complexity theoretic hypotheses. The ASBC algorithm is also analysed
         experimentally on a collection of realistic test cases from the Harwell–Boeing sparse
         matrix collection. The experimental results indicate that ASBC performs quite well in practice; the
         performance of the new algorithm always fell within the range of 1.53 and 6 times optimal on the
         given test sets.",
       ad_theotech = "Combinatorics, Sparsity"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)