Huge Unimodular $n$-Fold Programs

DOI10.1137/151004227zbMath1336.90062arXiv1501.00665OpenAlexW2964307467MaRDI QIDQ3455242

Shmuel Onn, Pauline Sarrabezolles

Publication date: 4 December 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingbin packingunimodulargraver basismultiway tableNP intersect coNP

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Unnamed Item ⋮ Scheduling meets \(n\)-fold integer programming

Cites Work

• A polynomial oracle-time algorithm for convex integer minimization
• A finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Nonlinear discrete optimization. An algorithmic theory
• Higher Lawrence configurations.
• \(n\)-fold integer programming in cubic time
• Huge multiway table problems
• Carathéodory bounds for integer cones
• A Polynomial-Time Algorithm for Optimizing over N-Fold 4-Block Decomposable Integer Programs
• 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
• Polynomiality for Bin Packing with a Constant Number of Item Types
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs