Convex integer maximization via Graver bases

DOI10.1016/j.jpaa.2008.11.033zbMath1284.05026arXivmath/0609019MaRDI QIDQ1017675

Robert Weismantel, Raymond Hemmecke, Jesús A. De Loera, Shmuel Onn, Uriel G. Rothblum

Publication date: 12 May 2009

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0609019

zbMATH Keywords

polynomial time algorithms; algebraic algorithmic scheme

Mathematics Subject Classification ID

05A17: Combinatorial aspects of partitions of integers

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

\(N\)-fold integer programming and nonlinear multi-transshipment, The quadratic Graver cone, quadratic integer minimization, and extensions, \(n\)-fold integer programming in cubic time, Graver basis and proximity techniques for block-structured separable convex integer minimization problems, Convex integer optimization by constantly many linear counterparts

Uses Software

• 4ti2

Cites Work

• The Graver complexity of integer programming
• Signature classes of transportation polytopes
• A finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Conditions for the existence of solutions of the three-dimensional planar transportation problem
• On clustering problems with connected optima in Euclidean spaces
• Optimal partitions having disjoint convex and conic hulls
• Some complexity results for polynomial ideals
• Approximation algorithms for multi-index transportation problems with decomposable costs
• Variation of cost functions in integer programming
• Higher Lawrence configurations.
• On properties of multi-dimensional statistical tables
• On the positive sums property and the computation of Graver test sets
• Convex combinatorial optimization
• An adaptive algorithm for vector partitioning
• Markov bases of three-way tables are arbitrarily complicated
• The Vector Partition Problem for Convex Objective Functions
• On the foundations of linear and integer linear programming I
• The Complexity of Three-Way Statistical Tables
• Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• A Polynomial Time Algorithm for Shaped Partition Problems
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item