\(N\)-fold integer programming
From MaRDI portal
Publication:951095
DOI10.1016/j.disopt.2006.06.006zbMath1151.90025arXivmath/0605242OpenAlexW2001104373MaRDI QIDQ951095
Jesús A. De Loera, Shmuel Onn, Raymond Hemmecke, Robert Weismantel
Publication date: 29 October 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0605242
computational complexityprimal methodcombinatorial optimizationaugmentationprivacyconfidentialityHilbert basisbin packingcontingency tableMarkov basiscutting stocktransportation polytopegraver basismultiway tabletest setMarkov complexitygraver complexityn-fold
Related Items
Huge Unimodular $n$-Fold Programs, Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory, On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond, The complexity of vector partition, Portfolio-optimization models for small investors, The quadratic Graver cone, quadratic integer minimization, and extensions, High-multiplicity \(N\)-fold IP via configuration LP, The algebra of reversible Markov chains, A polynomial oracle-time algorithm for convex integer minimization, A colorful Steinitz lemma with application to block-structured integer programs, Block-structured integer programming: can we parameterize without the largest coefficient?, \(n\)-fold integer programming in cubic time, \(N\)-fold integer programming and nonlinear multi-transshipment, Unnamed Item, Convex integer optimization by constantly many linear counterparts, Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding, The Graver complexity of integer programming, Computational complexity of three-dimensional discrete tomography with missing data, Faster Algorithms for Integer Programs with Block Structure, Efficient solutions for weight-balanced partitioning problems, Graver basis and proximity techniques for block-structured separable convex integer minimization problems, A heuristic method for solving integer-valued decompositional multiindex problems, Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes, Unnamed Item, Robust integer programming, When is rounding allowed in integer nonlinear optimization?, The double exponential runtime is tight for 2-stage stochastic ILPs, Subset Selection in Sparse Matrices, The double exponential runtime is tight for 2-stage stochastic ILPs, Unboundedness of Markov complexity of monomial curves in \(\mathbb{A}^n\) for \(n \geq 4\), Convex integer maximization via Graver bases, Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, A Polyhedral Frobenius Theorem with Applications to Integer Optimization, Huge multiway table problems, Lower bounds on the graver complexity of \(M\)-fold matrices
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Signature classes of transportation polytopes
- A finiteness theorem for Markov bases of hierarchical models
- Conditions for the existence of solutions of the three-dimensional planar transportation problem
- Approximation algorithms for multi-index transportation problems with decomposable costs
- 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
- Markov bases of three-way tables are arbitrarily complicated
- Integer Programming with a Fixed Number of Variables
- A Linear Programming Approach to the Cutting-Stock Problem
- On the foundations of linear and integer linear programming I
- Three-dimensional Statistical Data Security Problems
- 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
- The Complexity of Generic Primal Algorithms for Solving General Integer Programs
- Integer Programming and Combinatorial Optimization
- All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
