Author name cluster

Claudson F. Bornstein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

TCS Journal 2004 Journal Article

Flow metrics

Claudson F. Bornstein
Santosh Vempala

We introduce flow metrics as a relaxation of path metrics (i. e. linear orderings). They are defined by polynomial-sized linear programs and have interesting properties including spreading. We use them to obtain relaxations for several NP-hard linear ordering problems such as minimum linear arrangement and minimum pathwidth. Our approach has the advantage of achieving the best-known approximation guarantees for these problems using the same relaxation and essentially the same rounding algorithm for all the problems while varying only the objective function from problem to problem. This is in contrast to the current state of the literature where each problem either has a new relaxation or a new rounding or both. We also characterize a natural projection of the flow polyhedron.

Details DOI

FOCS Conference 1997 Conference Paper

Parallelizing Elimination Orders with Linear Fill

Claudson F. Bornstein
Bruce M. Maggs
Gary L. Miller
R. Ravi 0001

This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the order produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. In general, the input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an order with height at most O(log/sup 3/ n) times optimal, fill at most O(m), and work at most O(W*(G)), where W*(G) is the minimum possible work over all elimination orders for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an order that is actually better, in terms of work and fill, than the original one. We also present an algorithm that produces an order with a factor of log n less height, but with a factor of O(/spl radic/log n) more fill.

Details