The complexity of design automation problems

ABSTRACT

This paper reviews several problems that arise in the area of design automation. Most of these problems are shown to be NP-hard. Further, it is unlikely that any of these problems can be solved by fast approximation algorithms that guarantee solutions that are always within some fixed relative error of the optimal solution value. This points out the importance of heuristics and other tools to obtain algorithms that perform well on the problem instances of “interest”.

REFERENCES

• 1: Melvin A Breuer, The application of integer programming in design automation, Proceedings of the SHARE design automation project, p.2.1-2.19, January 1966 [doi>10.1145/800267.810774]
• 2: Breuer, M.A.(ed.), Design Automation of Digital Systems, Vol.1, Theory and Techniques, Prentice-Hall, Englewood Cliffs, NJ, 1972.
• 3: Breuer, M.A., "Recent Developments in the Automated Design and Analysis of Digital Systems," Proceedings of the IEEE, Vol. 60. No. 1, January 1972, pp. 12-27.
• 4: Christofedes, N., "Worst-case Analysis of a New Heuristic for a Traveling Salesman Problem," Mgmt. Science Research Report, Carnegie Mellon University, 1976.
• 5: Clark, R.L., "A Technique for Improving Wirability in Automated Circuit Card Placement, Rand Corp. Report R-4049, August 1969.
• 6: vanCleemput, W.M., "Computer Aided Design of Digital Systems," 3 volumes, Digital Systems Lab., Stanford University, Computer Science Press, Potomac, MD, 1976.
• 7: Ehrlich, G.S., S.Even and R.E.Tarjan, "Intersection graphs of Curves in the Plane," Jr. Combin. Theo., Ser. B, 21, 1976, pp. 8-20.
• 8: M. R. Garey , R. L. Graham , D. S. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.10-22, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803626]
• 9: Garey, M.R., R.L.Graham and D.S.Johnson, "The Complexity of Computing Steiner Minimal Trees," SIAM Jr.Appl.Math., 32, 1977, pp.835-859.
• 10: 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
• 11: Habayeb, A.R., "System Decomposition, Partitioning, and Integration for Microelectronics," IEEE Trans. on System Science and Cybernetics, Vol.SSC-4, No.2, July 1968, pp.164-172.
• 12: Ellis Horowitz , Sartaj Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM (JACM), v.21 n.2, p.277-292, April 1974 [doi>10.1145/321812.321823]
• 13: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 14: Ibarra, O.H. and S. Sahni, "Polynomially Complete Fault Detection Problems," IEEE Trans. on Computers, Vo1.C-24, March 1975, pp.242-249.
• 15: Karp, R., "On the Reducibility of Combinatorial Problems," in R.E.Miller and J.W.Thatcher(eds.), Complexity of Computer Computations, Plenum Press, NY, 1972, pp.85-103.
• 16: Karp, R., "The Fast Approximate Solution of Hard Combinatorial Problems," Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Winnipeg, 1975.
• 17: Karp, R., "The Probabilistic Analysis of Some Combinatorial Search Algorithms," University of California, Berkeley, Memo No.ERL-M581, April 1976.
• 18: Karp, R., "Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plane," Math. of Oper. Res., 2(3), 1977, pp.209-224.
• 19: Kodres, U.R., "Formulation and Solution of Circuit Card Design Problems Through Use of Graph Methods," in G.A.Walker(ed.), Advances in Electronic Circuit Packaging, Vol.2, Plenum Press, New York, NY, 1962, pp.121-142.
• 20: Kodres, U.R., "Logic Circuit Layout," The Digest Record of the 1969 Joint Conference of Mathematical and Computer Aids to Design, October 1969.
• 21: Lawler, E.L., "Electrical Assemblies with a Minimum Number of Interconnections," IEEE Trans. on Electronic Computers (Correspondence), Vol.EC-11, February 1962, pp.86-88.
• 22: Lawler, E.L., K.N. Levitt and J.Turner, "Module Clustering to Minimize Debay in Digital Networks," IEEE Trans. on Computers, Vol.C-18, January 1969, pp.47-57.
• 23: Lueker, G.S., "Two NP-Complete Problems In Nonnegative Integer Programming," Report No.178, Computer Science Lab., Princeton University, Princeton, NJ, 1975.
• 24: Notz, W.A., E. Schischa, J.L. Smith and M.G.Smith, "Large Scale Integration; Benefitting the Systems Designer," Electronics, February 20, 1967, pp.130-141.
• 25: Tomaso Pomentale, An algorithm for minimizing backboard wiring functions, Communications of the ACM, v.8 n.11, p.699-703, Nov. 1965 [doi>10.1145/365660.365684]
• 26: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 27: Sahni, S., Mathematical Concepts in Science and Engineering, University of Minnesota, 1980.
• 28: Shamos, M.I. and D.Hoey, "Closest Point Problems," 16th Annual IEEE Symposium on Founi. of Comp. Sc., 1975, pp.151-163.
• 29: Yao, A., "An 0(EloglogV) Algorithm for Minimum Spanning Trees," Information Processing Letters, 4(1), 1975, pp.21-23.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design, Theory

Keywords:
Approximation algorithm, Complexity, Design automation, NP-hard