An alternative algorithm for counting lattice points in a convex polytope

被引：9
作者：
Lasserre, JB
Zeron, ES
机构：
[1] CNRS, LAAS, F-31077 Toulouse, France
[2] Inst Politecn Nacl, Ctr Invest & Estudios Avanzados, Dept Math, Mexico City 07000, DF, Mexico
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 2005年 / 30卷 / 03期
关键词：
convex polytopes; lattice points; generating functions; counting lattice points;
D O I：
10.1287/moor.1050.0145
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We provide an alternative algorithm for counting lattice points in the convex polytope {x is an element of R-n vertical bar Ax = b, x >= 0}. It is based on an exact (tractable) formula for the case A E that we repeatedly use for the general case A is an element of Z(mxn).
引用
收藏
页码：597 / 614
页数：18
相关论文
共 16 条
[1]   Counting integer flows in networks [J].
Baldoni-Silva, W ;
De Loera, JA ;
Vergne, M .
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2004, 4 (03) :277-314
[2]  
BALDONISILVA W, 2001, ARXIVMATHCO0103097, P81
[3]  
Barvinok A., 1999, Math. Sci. Res. Inst. Publ., V38, P91
[4]   COMPUTING THE VOLUME, COUNTING INTEGRAL POINTS, AND EXPONENTIAL-SUMS [J].
BARVINOK, AI .
DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 10 (02) :123-141
[5]   Counting lattice points by means of the residue theorem [J].
Beck, M .
RAMANUJAN JOURNAL, 2000, 4 (03) :299-310
[6]   The Ehrhart polynomial of the Birkhoff polytope [J].
Beck, M ;
Pixton, D .
DISCRETE & COMPUTATIONAL GEOMETRY, 2003, 30 (04) :623-637
[7]   The Frobenius problem, rational polytopes, and Fourier-Dedekind sums [J].
Beck, M ;
Diaz, R ;
Robins, S .
JOURNAL OF NUMBER THEORY, 2002, 96 (01) :1-21
[8]   Residue formulae, vector partition functions and lattice points in rational polytopes [J].
Brion, M ;
Vergne, M .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1997, 10 (04) :797-833
[9]  
COCHET C, 2003, THESIS U PARIS 7 PAR
[10]   Effective lattice point counting in rational convex polytopes [J].
De Loera, JA ;
Hemmecke, R ;
Tauzer, J ;
Yoshida, R .
JOURNAL OF SYMBOLIC COMPUTATION, 2004, 38 (04) :1273-1302
12