The complexity of facets (and some facets of complexity)

ABSTRACT

Many important combinatorial optimization problems, including the traveling salesman problem (TSP), the clique problem and many others, call for the optimization of a linear functional over some discrete set of vectors.

REFERENCES

• 1: E. Balas , "Facets of the knapsack polytope", Math.Progr. 8, 146-164, (1975).
• 2: E. Balas and E. Zemel, "Critical cutsets of graphs and canonical facets of set packing polytopes", Math. of Oper. Res. 2, 15-20, (1977).
• 3: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 4: V. Chvatal, "Edmonds polytopes and weakly hamiltonian graphs", Math.Progr. 5, 29-40, (1973).
• 5: V. Chvatal, "On certain polytopes associated with graphs", J. of Comb. Theory (B) 18, 138-154, (1975).
• 6: G. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, 1963.
• 7: G. B. Dantzig, D. R. Fulkerson, S. M. Johnson, "Solution of a large-scale travelling salesman problem", Operations Research 2, 393-410, (1954).
• 8: J. Doyen and V. van Diest, "New families of hypohamiltonian graphs", Discrete Math. 13, 225-236, (1975).
• 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: M. Grotschel, "On the monotone symmetric travelling salesman problem:hypohamiltonian/hypotraceable graphs and facets", Math. of Oper. Res. 5, 285-292, (1980).
• 11: M. Grotschel, L. Lovasz, S. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization", Bonn, (1980).
• 12: M. Grotschel and M. W, Padberg, "On the symmetric travelling salesman problem II: Lifting theorem and facets", Math. Progr. 16, 281-302, (1979).
• 13: F. Harary, Graph Theory, Addison Wesley, 1969.
• 14: R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher eds., Plenum Press, 85-103, (1972).
• 15: R. M. Karp and C. H. Papadimitriou, "On linear characterizations of combinatorial optimization problems", Proc. 21st FOCS, 1-9, (1980).
• 16: D. Kelly, "The 3-irreducible partially ordered sets", Can. J. Math. 29, 367-383, (1977).
• 17: L. G. Khacian, "A polynomial algorithm for linear programming", Dokl. Ak. Nauk. SSSR, 1093-1096, (1979).
• 18: E. W. Leggett, Jr. and D. J. Moore, "Optimization problems and the polynomial hierarchy", Theor. Comp. Science 15, 279-289, (1981).
• 19: W. F. Lindgren, "An infinite class of hypohamiltonian graphs", Amer. Math. Monthly 74, 1087-1089, (1967).
• 20: G. L. Nemhauser and L. E. Trotter, "Properties of vertex packing and independence system polyhedra", Math. Progr. 6, 48-61, (1974).
• 21: M. W. Padberg, "On the facial structure of set packing polyhedra", Math. Progr. 5, 199-215, (1973).
• 22: M. W. Padberg, "On the complexity of set packing polyhedra", Annals of Discrete Math. 1, 421-434, (1977).
• 23: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 24: C. Thomassen, "Hypohamiltonian and hypotraceable graphs", Discrete Math. 9, 91-96, (1974).
• 25: W. T. Trotter Jr. and J. I. Moore Jr., "Characterization problems for graphs, partially ordered sets, lattices and families of sets", Discrete Math. 16, 361-381, (1976).
• 26: W. T. Trotter Jr. and J. A. Ross, "For t-&-ge;3, every t-dimensonal partial order can be embedded in a t+1-irreducible partial order", (1981).
• 27: L. A. Wolsey, "Further facet generating procedures for vertex packing polytopes", Math. Progr. 11, 158-163, (1976).
• 28: M. Yannakakis, "The complexity of the partial order dimension problem", SIAM J. Appl. Dis. Meth., to appear.