TY - JOUR

T1 - Convex integer maximization via Graver bases

AU - De Loera, J. A.

AU - Hemmecke, R.

AU - Onn, S.

AU - Rothblum, U. G.

AU - Weismantel, R.

N1 - Funding Information:
First author was supported in part by NSF grant DMS-0608785. Second author was supported in part by the European TMR network ADONET 504438. Third and fourth authors were supported in part by a grant from ISF — the Israel Science Foundation. Fifth author was supported in part by the European TMR network ADONET 504438.

PY - 2009/8

Y1 - 2009/8

N2 - We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where c is a convex function on Rd and w1 x, ..., wd x are linear forms on Rn, max {c (w1 x, ..., wd x) : A x = b, x ∈ Nn} . This method works for arbitrary input data A, b, d, w1, ..., wd, c. Moreover, for fixed d and several important classes of programs in variable dimension, we prove that our algorithm runs in polynomial time. As a consequence, we obtain polynomial time algorithms for various types of multi-way transportation problems, packing problems, and partitioning problems in variable dimension.

AB - We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where c is a convex function on Rd and w1 x, ..., wd x are linear forms on Rn, max {c (w1 x, ..., wd x) : A x = b, x ∈ Nn} . This method works for arbitrary input data A, b, d, w1, ..., wd, c. Moreover, for fixed d and several important classes of programs in variable dimension, we prove that our algorithm runs in polynomial time. As a consequence, we obtain polynomial time algorithms for various types of multi-way transportation problems, packing problems, and partitioning problems in variable dimension.

UR - http://www.scopus.com/inward/record.url?scp=63149088767&partnerID=8YFLogxK

U2 - 10.1016/j.jpaa.2008.11.033

DO - 10.1016/j.jpaa.2008.11.033

M3 - Article

AN - SCOPUS:63149088767

SN - 0022-4049

VL - 213

SP - 1569

EP - 1577

JO - Journal of Pure and Applied Algebra

JF - Journal of Pure and Applied Algebra

IS - 8

ER -