Divide-and-conquer approximation algorithms via spreading metrics
- 1 July 2000
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 47 (4), 585-616
- https://doi.org/10.1145/347476.347478
Abstract
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 lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial 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 whose approximation factor is O (min{log τ, log log τ, log k log log k }) where k denotes the number of “interesting” vertices in the problem instance, and is at most the number of vertices. 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) balanced partitions and p -separators (for small values of p ) in directed graphs.Keywords
This publication has 15 references indexed in Scilit:
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Fast Approximate Graph Partitioning AlgorithmsSIAM Journal on Computing, 1999
- Approximating Minimum Feedback Sets and Multicuts in Directed GraphsAlgorithmica, 1998
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation AlgorithmSIAM Journal on Computing, 1998
- Approximation Algorithms for Steiner and Directed MulticutsJournal of Algorithms, 1997
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their ApplicationsSIAM Journal on Computing, 1996
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Interior-Point Polynomial Algorithms in Convex ProgrammingPublished by Society for Industrial & Applied Mathematics (SIAM) ,1994
- Geometric Algorithms and Combinatorial OptimizationAlgorithms and Combinatorics, 1988
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984