Geometric comparison of combinatorial polytopes. (English) Zbl 0813.90094
Summary: We survey some analytic methods of volume calculation and introduce a distance function for pairs of polytopes based on their volumes. We study the distance function in the context of three familiar settings of combinatorial optimization: (i) Chvátal-Gomory rounding, (ii) fixed- charge problems, and (iii) vertex packing.
MSC:
| 90C27 | Combinatorial optimization |
| 05C90 | Applications of graph theory |
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
Keywords:
survey; volume calculation; distance function; rounding; fixed-charge problems; vertex packingReferences:
| [1] | Barrow, D. L.; Smith, P. W., Spline notation applied to a volume problem, Amer. Math. Monthly, 86, 50-51 (1979) · Zbl 0411.51013 |
| [2] | Bender, E. A., Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory Ser. A, 15, 91-111 (1973), Ser. A · Zbl 0242.05006 |
| [3] | Berge, C., Principles of Combinatorics (1971), Academic Press: Academic Press New York · Zbl 0227.05002 |
| [4] | G. Brightwell and P. Winkler, Counting linear extensions is #-complete, Bellcore preprint.; G. Brightwell and P. Winkler, Counting linear extensions is #-complete, Bellcore preprint. |
| [5] | Burago, Y. D.; Zalgaller, V. A., Geometric Inequalities (1988), Springer: Springer Berlin · Zbl 0633.53002 |
| [6] | Chvátal, V.; Hammer, P. L., Aggregation of inequalities in integer programming, Ann. Discrete Math., 1, 145-162 (1977) · Zbl 0384.90091 |
| [7] | Cohen, J.; Hickey, T., Two algorithms for determining volumes of convex polyhedra, J. ACM, 26, 401-414 (1977) · Zbl 0403.68067 |
| [8] | Duchet, P., Classical perfect graphs, Ann. Discrete Math., 21, 67-96 (1984) · Zbl 0558.05038 |
| [9] | Eggleston, H. G., Convexity (1958), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0086.15302 |
| [10] | Ehrhart, E., Sur les polyèdres rationnels homothétiques à \(n\) dimensions, C.R. Acad. Sci. Paris, 254, 616-618 (1962) · Zbl 0100.27601 |
| [11] | Ehrhart, E., Sur un problème de géométrie diophantienne linéaire, J. Reine Angew. Math., 226, 1-29 (1967) · Zbl 0155.37503 |
| [12] | Ehrhart, E., Sur un problème de géométrie diophantienne linéaire, J. Reine Angew. Math., 227, 25-49 (1967) · Zbl 0155.37503 |
| [13] | Golumbic, M. C., Threshold graphs and synchronizing parallel processes, (Hajnal, A.; Sós, V. T., Combinatorics, Colloquia Mathematica Societatis Jánas Bolyai, 18 (1978), North-Holland: North-Holland Amsterdam), 419-428 · Zbl 0398.05058 |
| [14] | Gruber, P. M.; Lekkerkerker, C. G., Geometry of Numbers (1987), North-Holland: North-Holland Amsterdam · Zbl 0611.10017 |
| [15] | Grötschel, M.; Lovasz, L.; Schrijver, A., Polynomial algorithms for perfect graphs, Ann. Discrete Math., 21, 325-356 (1984) · Zbl 0554.05041 |
| [16] | Khachiyan, L., Complexity of polytope volume computation, DIMACS Tech. Rept. 90-59 (1990) |
| [17] | Knessl, C.; Keller, J. B., Stirling number asymptotics from recursion equations using the ray method, Stud. Appl. Math., 84, 43-56 (1991) · Zbl 0735.05006 |
| [18] | Lawrence, J., Polytope volume computation, Math. Comp., 57, 259-271 (1991) · Zbl 0734.52009 |
| [19] | Lee, J., Subspaces with well-scaled frames, Linear Algebra Appl., 114/115, 21-56 (1989) · Zbl 0675.90061 |
| [20] | Macdonald, I. G., The volume of a lattice polyhedron, Proc. Cambridge Philos. Soc., 59, 719-726 (1963) · Zbl 0126.18103 |
| [21] | Moser, L.; Wyman, M., Stirling numbers of the second kind, Duke Math. J., 25, 29-43 (1958) · Zbl 0079.09102 |
| [22] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 |
| [23] | Orlin, J., The minimal integral separator of a threshold graph, Ann. Discrete Math., 1, 415-419 (1977) · Zbl 0361.05039 |
| [24] | Schrijver, A., Linear and Integer Programming (1986), Wiley: Wiley New York · Zbl 0665.90063 |
| [25] | Stanley, R., Eulerian partitions of a unit hypercube, (Aigner, M., Higher Combinatorics (1977), Reidel: Reidel Dordrecht), 49 · Zbl 0359.05001 |
| [26] | Stanley, R., Two order polytopes, Discrete Comput. Geom., 1, 9-23 (1986) · Zbl 0595.52008 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
