TY - JOUR
T1 - An algebraic-perturbation variant of Barvinok's algorithm
AU - Lee, Jon
AU - Skipper, Daphne
N1 - Funding Information:
1 Lee was partially supported by NSF grant CMMI-1160915; ONR grant N00014-14-1-0315. 2 Email: jonxlee@umich.edu 3 Email: dapskipper@gru.edu
Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - We give a variant of Barvinok's algorithm for computing a short rational generating function for the integer points in P := {x ∈ Rn : Ax ≤ b}; a use of which is to count the number of integer points in P. We use an algebraic perturbation, replacing each bi with bi+τi, where τ>0 is an arbitrarily small indeterminate. Hence, our new right-hand vector has components in the ordered ring Q[τ] of polynomials in τ. Denoting the perturbed polyhedron by P(τ)⊂R[τ]n, we use the facts that: P(τ) is full dimensional, simple, and contains the same integer points as P.
AB - We give a variant of Barvinok's algorithm for computing a short rational generating function for the integer points in P := {x ∈ Rn : Ax ≤ b}; a use of which is to count the number of integer points in P. We use an algebraic perturbation, replacing each bi with bi+τi, where τ>0 is an arbitrarily small indeterminate. Hence, our new right-hand vector has components in the ordered ring Q[τ] of polynomials in τ. Denoting the perturbed polyhedron by P(τ)⊂R[τ]n, we use the facts that: P(τ) is full dimensional, simple, and contains the same integer points as P.
KW - Barvinok's algorithm
KW - Generating function
KW - Integer
KW - Polyhedron
UR - http://www.scopus.com/inward/record.url?scp=84953378005&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84953378005&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2015.07.004
DO - 10.1016/j.endm.2015.07.004
M3 - Article
AN - SCOPUS:84953378005
SN - 1571-0653
VL - 50
SP - 15
EP - 20
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -