Divide-and-Conquer Approximation Algorithms via Spreading Metrics

Copyright [©] (2000) by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit or commericial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns rational lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimization problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm. We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a d-dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) multiway separators and r-separators (for small values of r) in directed graphs.

By: Guy Even (Univ. des Saarlandes, Germany), Joseph Naor (Technion, Israel), Satish Rao (NEC Res. Inst.), Baruch Schieber

Published in: Journal of the Association for Computing Machinery, volume 47, (no 4), pages 585-616 in 2000

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .