The front size of a matrix $A$ is the largest number of non-zeros below the diagonal in any column of its Cholesky factor. If $A$ is symmetric then the minimum front size of $A$ is equal to the treewidth of $G(A)$. Here $G(A)$ is an undirected graph with $A$ as its adjacency matrix. Hence, front size of symmetric matrix can be approximated by using the approximation algorithms of treewidth. The best known factor is $O(\sqrt{\log{n}})$.
I noticed that an approximation algorithm (to approximate Kelly-Width) in one of my recent papers, implies $O({\log}^{3/2}{n})$ approximation for front size of asymmetric matrices.
Minimizing front size is a fundamental problem and is very crucial in multi-frontal algorithms. I am wondering if there is an earlier approximation algorithm for front size of asymmetric matrices.
I will be surprised (and simultaneously excited) if the algorithm mentioned in my paper is the first approximation algorithm with non-trivial approximation factor.
Is there an approximation algorithm for the front size of asymmetric matrices, prior to our work ?
