C. H. Papadimitriou
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.
- 1.E. Balas , "Facets of the knapsack polytope", Math.Progr. 8, 146-164, (1975).Google Scholar
Digital Library
- 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).Google ScholarDigital Library
- 3.C. Berge, Graphs and Hypergraphs, North-Holland, 1973. Google ScholarDigital Library
- 4.V. Chvatal, "Edmonds polytopes and weakly hamiltonian graphs", Math.Progr. 5, 29-40, (1973).Google ScholarDigital Library
- 5.V. Chvatal, "On certain polytopes associated with graphs", J. of Comb. Theory (B) 18, 138-154, (1975).Google ScholarCross Ref
- 6.G. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, 1963.Google Scholar
- 7.G. B. Dantzig, D. R. Fulkerson, S. M. Johnson, "Solution of a large-scale travelling salesman problem", Operations Research 2, 393-410, (1954).Google ScholarCross Ref
- 8.J. Doyen and V. van Diest, "New families of hypohamiltonian graphs", Discrete Math. 13, 225-236, (1975).Google ScholarDigital Library
- 9.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completenes, W. H. Freeman, 1979. Google ScholarDigital Library
- 10.M. Grotschel, "On the monotone symmetric travelling salesman problem:hypohamiltonian/hypotraceable graphs and facets", Math. of Oper. Res. 5, 285-292, (1980).Google ScholarDigital Library
- 11.M. Grotschel, L. Lovasz, S. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization", Bonn, (1980).Google Scholar
- 12.M. Grotschel and M. W, Padberg, "On the symmetric travelling salesman problem II: Lifting theorem and facets", Math. Progr. 16, 281-302, (1979).Google ScholarCross Ref
- 13.F. Harary, Graph Theory, Addison Wesley, 1969.Google Scholar
- 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).Google Scholar
- 15.R. M. Karp and C. H. Papadimitriou, "On linear characterizations of combinatorial optimization problems", Proc. 21st FOCS, 1-9, (1980).Google ScholarDigital Library
- 16.D. Kelly, "The 3-irreducible partially ordered sets", Can. J. Math. 29, 367-383, (1977).Google Scholar
- 17.L. G. Khacian, "A polynomial algorithm for linear programming", Dokl. Ak. Nauk. SSSR, 1093-1096, (1979).Google Scholar
- 18.E. W. Leggett, Jr. and D. J. Moore, "Optimization problems and the polynomial hierarchy", Theor. Comp. Science 15, 279-289, (1981).Google ScholarCross Ref
- 19.W. F. Lindgren, "An infinite class of hypohamiltonian graphs", Amer. Math. Monthly 74, 1087-1089, (1967).Google ScholarCross Ref
- 20.G. L. Nemhauser and L. E. Trotter, "Properties of vertex packing and independence system polyhedra", Math. Progr. 6, 48-61, (1974).Google ScholarDigital Library
- 21.M. W. Padberg, "On the facial structure of set packing polyhedra", Math. Progr. 5, 199-215, (1973).Google ScholarDigital Library
- 22.M. W. Padberg, "On the complexity of set packing polyhedra", Annals of Discrete Math. 1, 421-434, (1977).Google ScholarCross Ref
- 23.C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982. Google ScholarDigital Library
- 24.C. Thomassen, "Hypohamiltonian and hypotraceable graphs", Discrete Math. 9, 91-96, (1974).Google ScholarDigital Library
- 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).Google ScholarCross Ref
- 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).Google Scholar
- 27.L. A. Wolsey, "Further facet generating procedures for vertex packing polytopes", Math. Progr. 11, 158-163, (1976).Google ScholarDigital Library
- 28.M. Yannakakis, "The complexity of the partial order dimension problem", SIAM J. Appl. Dis. Meth., to appear.Google Scholar
- The complexity of facets (and some facets of complexity)
Recommendations
Lifting facets of the cut polytope
The cut polytope P"c(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. We give a sufficient condition for an inequality defining a facet of P"c(G) to define a facet of the cut polytope of a graph containing G ...
Facets of the Asymmetric Traveling Salesman Polytope
In this paper we consider the Asymmetric Traveling Salesman polytope, Pn, defined as the convex hull of the incidence vectors of tours in a complete digraph with n vertices, and its monotonization, P̃n. Several classes of valid inequalities for both ...
Clique-Web Facets for Multicut Polytopes
Let G = V , E be a graph. An edge set { uv ∈ E | u ∈ S i , v ∈ S j , i â j }, where S 1, ', S k is a partition of V , is called a multicut with k shores. We investigate the polytopes MC k â n and MC k â n that are defined ...
Comments