Tutorial on Computational Complexity

References

• Bartholdi J., Narasimhan L., Tovey C. Recognizing equilibria in spatial voting games. Social Choice and Welfare (1991) 8(3):183–197Crossref, Google Scholar
• Bramel J., Simchi-Levi D. A location based heuristic for general routing problems. Oper. Res. (1995) 43(4):649–660Link, Google Scholar
• Brockett R. W. Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems. Linear Algebra Appl. (1991) 146(1):79–91Crossref, Google Scholar
• Canny J., Reif J. New lower bound techniques for robot motion planning problems. Proc. 28th Annual IEEE Sympos. in Foundations of Comput. Sci. (1987) Los Angeles, CA:49–60Crossref, Google Scholar
• Carter M., Tovey C. When is the classroom assignment problem hard? Oper. Res. (1992) 40(Supplement No. 1):S28–S39Link, Google Scholar
• Chandra B., Karloff H., Tovey C. New results on the old kopt algorithm for the traveling salesman problem. SIAM J. Comput. (1999) 28(6):1998–2029Crossref, Google Scholar
• Chernoff H. Lecture on statistics. (1975) 18–304Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Chvatal V. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. (1973) 4(3):305–337Crossref, Google Scholar
• Coxson G. The P-matrix problem is co-NP-complete. Math. Programming (1994) 64A(2):173–178Crossref, Google Scholar
• Dantzig G.Linear Programming and Extensions (1963) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Garey M., Johnson D.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman, San Francisco, CA) Google Scholar
• Geoffrion A. An introduction to structured modeling. Management Sci. (1987) 33(5):547–588Link, Google Scholar
• Geoffrion A., Gass S., Harris C. Structured modeling. Encyclopedia of Operations Research and Management Science (1996) (Kluwer Academic Publishers, Norwell, MA) Google Scholar
• Goemans M., Williamson D. Improved approximation algorithms for maximum cut and satisfiability problems using semi-definite programming. J. ACM (1995) 42(4):1113–1145Google Scholar
• Hackman S., Leachman R. A general framework for modeling production. Management Sci. (1989) 35(4):478–495Link, Google Scholar
• Håstad J. Some optimal inapproximability results. Proc. 29th Annual ACM Sympos. on Theory of Comput. STOC '97 (1997) 1–10Crossref, Google Scholar
• Karloff H., Zwick U. A 7/8 approximation algorithm for MAX 3SAT. Proc. 38th Annual IEEE Symposi. in Foundations of Comput. Sci. (1997) 406–415Crossref, Google Scholar
• Knuth D.Fundamental Algorithms (1973) (Addison-Wesley, Reading, MA) Google Scholar
• Latombe Jean-Claude. Robot Motion Planning (1991) (Kluwer Academic Publishers, Norwell, MA) Crossref, Google Scholar
• Lofgren C. Machine configuration of flexible printed circuit board assembly systems. (1986) . Ph.D. thesis, School of ISyE, Georgia Institute of Technology, Atlanta, GAGoogle Scholar
• McConnell J. V.Understanding Human Behavior (1989) 6th ed.(Holt, Rinehart, and Winston, New York) Google Scholar
• Papadimitriou C.Computational Complexity (1994) (Addison-Wesley, Reading, MA) Google Scholar
• Papadimitriou C., Steiglitz K.Combinatorial Optimization: Algorithms and Complexity (1982) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Rosenberg Adam. (1993) . Conversation with authorGoogle Scholar
• Sipser M.Introduction to the Theory of Computation (1997) (PWS Publishing, Cambridge, MA) Google Scholar
• Tovey C. A simplified NP-complete satisfiability problem. Discrete Appl. Math. (1984) 8(1):85–89Crossref, Google Scholar
• Tovey C. Lecture on heuristics in advanced topics course CS8113. (1993) . Georgia Institute of Technology, Atlanta, GAGoogle Scholar