Divide-and-conquer approximation algorithms via spreading metrics

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, t , 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 t, log log t , 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.

REFERENCES

• 1: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 2: BAR-YEHUDA, R., EVEN, G., AND NAOR, J. 1998. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. Manuscript.
• 3: Avrim Blum , Goran Konjevod , R. Ravi , Santosh Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.100-105, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276717]
• 4: BHATT, S. N., AND LEIGHTON, F.T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300-343.
• 5: G. Even , J. Naor , S. Rao , B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.62, October 23-25, 1995
• 6: Guy Even, Fast Approximate Graph Partitioning Algorithms, SIAM Journal on Computing, v.28 n.6, p.2187-2214, Dec. 1999 [doi>10.1137/S0097539796308217]
• 7: EVEN, G., NAOR, J., SCHIEBER, B., AND SUDAN, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 151-174.
• 8: Uriel Feige, Approximating the bandwidth via volume respecting embeddings (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.90-99, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276716]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.
• 11: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 12: HANSEN, M. 1989. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 604-609.
• 13: Ming-er Kuo , Chung-Kuan Cheng, A network flow approach for hierarchical tree partitioning, Proceedings of the 34th annual conference on Design automation, p.512-517, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266269]
• 14: Philip N. Klein , Serge A. Plotkin , Satish Rao , Éva Tardos, Approximation algorithms for Steiner and directed multicuts, Journal of Algorithms, v.22 n.2, p.241-269, Feb. 1997 [doi>10.1006/jagm.1996.0833]
• 15: LEIGHTON, F. T., MAKEDON, F., AND TRAGOUDAS, S. 1990. Approximation algorithms for VLSI partition problems. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif. pp. 2866-2868.
• 16: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 17: LINIAL, N., LONDON, E., AND RABINOVICH, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215-245.
• 18: NESTEROV, Y., AND NEMIROVSKII, A. 1994. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia.
• 19: R. Ravi , Ajit Agrawal , Philip Klein, Ordering problems approximated: single-processor scheduling and interval graph completion, Proceedings of the 18th international colloquium on Automata, languages and programming, p.751-762, June 1991, Madrid, Spain
• 20: G. Ramalingam , C. Pandu Rangan, A unified approach to domination problems on interval graphs, Information Processing Letters, v.27 n.5, p.271-274, April 28, 1988 [doi>10.1016/0020-0190(88)90091-9]
• 21: Satish Rao , Andréa W. Richa, New approximation techniques for some ordering problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.211-218, January 25-27, 1998, San Francisco, California, United States
• 22: SAGAN, H. 1994. Space-Filling Curves. Springer-Verlag, New York.
• 23: SEYMOUR, P.D. 1995. Packing directed circuits fractionally. Combinatorica 15, 281-288.
• 24: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 25: Horst D. Simon , Shang-Hua Teng, How Good is Recursive Bisection?, SIAM Journal on Scientific Computing, v.18 n.5, p.1436-1445, Sept. 1997 [doi>10.1137/S1064827593255135]
• 26: Santosh Vempala, Random Projection: A New Approach to VLSI Layout, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.389, November 08-11, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, divide and conquer, feedback set, linear arrangement, multicut, spreading metrics