Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tính toán đa thức Ehrhart của một polytope lưới lồi
Tóm tắt
Chúng tôi chứng minh rằng việc tính toán bất kỳ số lượng hệ số cao nhất cố định nào của đa thức Ehrhart của một polytope nguyên có thể được rút gọn trong thời gian đa thức xuống việc tính toán các thể tích của các mặt.
Từ khóa
Tài liệu tham khảo
A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Preprint, TRITA/MAT-92-0036, Royal Institute of Technology, Stockholm, 1992.
A. I. Barvinok, A polynomial-time algorithm for counting integral points in polyhedra when the dimension is fixed,Proceedings of 34th Symposium on the Foundations of Computer Science (FOCS ’93), IEEE Computer Society Press, New York, 1993, pp. 566–572.
W. Cook, M. Hartmann, R. Kannan, and C. McDiarmid, On integer points in polyhedra,Combinatorica 12 (1992), 27–37.
M. Dyer and A. M. Frieze, On the complexity of computing the volume of a polyhedron,SIAM J. Comput. 17(5) (1988), 967–974.
W. Fulton,Introduction to Toric Varieties, Annals of Mathematics Studies, Vol. 131, Princeton University Press, Princeton, NJ, 1993.
M. Grötschel, L. Lovasz, and A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, Vol. 2, Springer-Verlag, Berlin, 1988.
R. Kannan, Minkowski’s convex body theorem and integer programming.Math. Oper. Res.,12 (1987), 415–440.
J. Lawrence, Polytope volume computation,Math. Comp.,57(195) (1991), 259–271.
I. G. Macdonald, Polynomials associated with finite cell complexes.J. London Math. Soc. (2),4 (1971), 181–192.
R. Morelli, Pick’s theorem and the Todd class of a toric variety.Adv. in Math.,100(2) (1993), 183–231.
J. E. Pommersheim, Toric varieties, lattice points and Dedekind sums.Math. Ann.,295 (1993), 1–24.
R. P. Stanley,Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Monterey, CA, 1986.
