N-fold integer programming
From MaRDI portal
Publication:951095
DOI10.1016/J.DISOPT.2006.06.006zbMATH Open1151.90025arXivmath/0605242OpenAlexW2001104373MaRDI QIDQ951095FDOQ951095
Authors: Jesús A. De Loera, Raymond Hemmecke, Shmuel Onn, Robert Weismantel 
Publication date: 29 October 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Abstract: In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {em n-fold integer programming problems} are polynomial time solvable. Our proof involves two heavy ingredients discovered recently: the equivalence of linear optimization and so-called directed augmentation, and the stabilization of certain Graver bases. We discuss several applications of our algorithm to multiway transportation problems and to packing problems. One important consequence of our results is a polynomial time algorithm for the -dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem.
Full work available at URL: https://arxiv.org/abs/math/0605242
Recommendations
computational complexitycontingency tablecombinatorial optimizationconfidentialitybin packingMarkov basiscutting stocktransportation polytopeprivacygraver basismultiway tabletest setaugmentationHilbert basisMarkov complexityprimal methodgraver complexityn-fold
Cites Work
- Title not available (Why is that?)
- A Linear Programming Approach to the Cutting-Stock Problem
- Approximation algorithms for multi-index transportation problems with decomposable costs
- Higher Lawrence configurations.
- Integer Programming with a Fixed Number of Variables
- On the foundations of linear and integer linear programming I
- Title not available (Why is that?)
- A finiteness theorem for Markov bases of hierarchical models
- Title not available (Why is that?)
- Signature classes of transportation polytopes
- The Complexity of Three-Way Statistical Tables
- All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
- Title not available (Why is that?)
- Convex combinatorial optimization
- Three-dimensional Statistical Data Security Problems
- Markov bases of three-way tables are arbitrarily complicated
- Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
- On the positive sums property and the computation of Graver test sets
- Conditions for the existence of solutions of the three-dimensional planar transportation problem
- The Complexity of Generic Primal Algorithms for Solving General Integer Programs
- On properties of multi-dimensional statistical tables
- Integer Programming and Combinatorial Optimization
Cited In (44)
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Lower bounds on the graver complexity of \(M\)-fold matrices
- Markov Bases: A 25 Year Update
- Theory and Applications of n-Fold Integer Programming
- A polynomial oracle-time algorithm for convex integer minimization
- The Graver complexity of integer programming
- Computational complexity of three-dimensional discrete tomography with missing data
- Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes
- Compact representation of near-optimal integer programming solutions
- A heuristic method for solving integer-valued decompositional multiindex problems
- High-multiplicity \(N\)-fold IP via configuration LP
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- Efficient solutions for weight-balanced partitioning problems
- Near-linear time algorithm for \(n\)-fold ILPs via color coding
- The double exponential runtime is tight for 2-stage stochastic ILPs
- Title not available (Why is that?)
- Robust integer programming
- Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
- Portfolio-optimization models for small investors
- FPT algorithms for a special block-structured integer program with applications in scheduling
- Subset selection in sparse matrices
- The algebra of reversible Markov chains
- The double exponential runtime is tight for 2-stage stochastic ILPs
- \(N\)-fold integer programming and nonlinear multi-transshipment
- A polynomial-time algorithm for optimizing over \(N\)-fold 4-block decomposable integer programs
- Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
- Title not available (Why is that?)
- The quadratic Graver cone, quadratic integer minimization, and extensions
- Convex integer optimization by constantly many linear counterparts
- The complexity of vector partition
- When is rounding allowed in integer nonlinear optimization?
- Title not available (Why is that?)
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Huge unimodular \(n\)-fold programs
- Block-structured integer programming: can we parameterize without the largest coefficient?
- \(n\)-fold integer programming in cubic time
- Unboundedness of Markov complexity of monomial curves in \(\mathbb{A}^n\) for \(n \geq 4\)
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Faster Algorithms for Integer Programs with Block Structure
- Convex integer maximization via Graver bases
- A colorful Steinitz lemma with application to block-structured integer programs
- Combinatorial \(n\)-fold integer programming and applications
- Combinatorial \(n\)-fold integer programming and applications
- Huge multiway table problems
Uses Software
This page was built for publication: \(N\)-fold integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q951095)
