Convex integer maximization via Graver bases

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

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

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 algorithmsalgebraic algorithmic scheme

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The quadratic Graver cone, quadratic integer minimization, and extensions, The power of pyramid decomposition in Normaliz, Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube, \(n\)-fold integer programming in cubic time, \(N\)-fold integer programming and nonlinear multi-transshipment, Convex integer optimization by constantly many linear counterparts, Efficient edge-skeleton computation for polytopes defined by oracles, Efficient solutions for weight-balanced partitioning problems, Graver basis and proximity techniques for block-structured separable convex integer minimization problems

Uses Software

• 4ti2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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