zbMATH — the first resource for mathematics

Expressing combinatorial optimization problems by linear programs. (English) Zbl 0748.90074
The \({\mathcal P}={\mathcal NP}\) problem is investigated. The known \(\mathcal NP\)- complete problems can be formulated as an optimization of a linear function over a convex hull of feasible solutions of the problem. Such a representation does not provide an advantage because of the exponential size of the obtained linear program (LP). The paper aims at analysing the possibility to reduce the size of the LP. Adding new variables the author proposes to transform a polytope of the LP to a specific form, named symmetric. Roughly, it is a polytope that remains “invariant” under any permutation of the initial variables. The main result is that the travelling salesman problem and the matching problem cannot be expressed by any symmetric LP with a size less than exponential.

90C35 Programming involving graphs or networks
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
90C05 Linear programming
Full Text: DOI
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Aho, A.V.; Ullman, J.D.; Yannakakis, M., On notions of information transfer in VLSI circuits, (), 133-139
[3] Berge, C.; Chvatal, V., Topics on perfect graphs, () · Zbl 0546.00006
[4] Balas, E.; Pulleyblank, W., The perfectly matchable subgraph polytope of a bipartite graph, Networks, 13, 486-516, (1983) · Zbl 0525.90069
[5] Dobkin, D.; Lipton, R.J.; Reiss, S., Linear programming is log-space hard for P, Inform. process. lett., 8, 96-97, (1979) · Zbl 0402.68042
[6] Edmonds, J., Maximum matching and a polyhedron with 0, 1 vertices, J. res. nat. bur. standards B, 69, 125-130, (1965) · Zbl 0141.21802
[7] Garey, M.R.; Johson, D.S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[8] Golumbic, M., Algorithmic graph theory and perfect graphs, (1900), Academic Press New York/London
[9] Grotschel, M.; Lovasz, L.; Schruver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056
[10] Grotchel, M.; Padberg, M.W., Polyhedral theory, and polyhedral computations, (), 251-360
[11] Jeroslow, R.G., On defining sets of vertices of the hypercube by linear inequalities, Discrete math., 11, 119-124, (1975) · Zbl 0297.52009
[12] \scD. S. Johnson, personal communication.
[13] Karmakar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[14] Khachian, L.G.; Khachian, L.G., A polynomial algorithm in linear programming, Dokl. akad. nauk SSSR, Soviet math. doki., 20, 191-194, (1979), English translation · Zbl 0409.90079
[15] Lovasz, L., Vertex packing algorithms, (), 1-14
[16] Martin, R.K., Using separation algorithms to generate mixed integer model reformulations, (1987), Graduate School of Business, University of Chicago, working paper
[17] Martin, R.K.; Rardin, R.L.; Campbell, B.A., Polyhedral characterization of discrete dynamic programming, () · Zbl 0711.90066
[18] Melhorn, K.; Schmidt, E.M., Las Vegas is better than determinism in VLSI and distributed computing, (), 330-337
[19] Padberg, M.; Rao, M.R., Odd minimum cut-sets and b-matchings, Math. oper. res., 7, 67-80, (1982) · Zbl 0499.90056
[20] Padberg, M.; Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by branch and cut, Oper. res. lett., 6, 1-7, (1987) · Zbl 0618.90082
[21] Papadimitriou, C.H.; Sipser, M., Communication complexity, (), 196-200
[22] Papadimitriou, C.H.; Wolfe, D., The complexity of facets resolved, (), 74-78
[23] Papadimitriou, C.H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. comput. system sci., 28, 144-259, (1984) · Zbl 0571.68028
[24] Razborov, A.A., A lower bound on the monotone network complexity of the logical permanent, Math. notes, 37, 485-493, (1985) · Zbl 0584.94026
[25] Schruver, A., Theory of linear and integer programming, (1986), New York
[26] Swart, E.R., (), revision
[27] Valiant, L.G., Reducibility by algebraic projections, Enseign. math., 28, 253-268, (1982) · Zbl 0493.68045
[28] Wielandt, H., Finite permutation groups, (1964), Academic Press New York/London · Zbl 0138.02501
[29] Yao, A.C., Some complexity questions related to distributive computing, (), 209-213
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.