All Linear and Integer Programs Are Slim 3‐Way Transportation Programs

DOI10.1137/040610623zbMath1128.90041OpenAlexW1975921416MaRDI QIDQ5757350

Jesús A. De Loera, Shmuel Onn

Publication date: 6 September 2007

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/040610623

zbMATH Keywords

linear programminginteger programmingcombinatorial optimizationtransportation problemsprivacymulticommodity flowsapproximation algorithmsconvex polytopescontingency tablestoric idealMarkov basisdata securitymultiway tablestrongly polynomial timedisclosurestatistical tablecofinetiality

Mathematics Subject Classification ID

Mixed integer programming (90C11) Computational aspects related to convexity (52B55) Combinatorics in computer science (68R05) Transportation, logistics and supply chain management (90B06) Linear inequalities of matrices (15A39) Contingency tables (62H17)

Related Items (20)

Huge Unimodular $n$-Fold Programs ⋮ Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory ⋮ Estimating the number of zero-one multi-way tables via sequential importance sampling ⋮ The quadratic Graver cone, quadratic integer minimization, and extensions ⋮ A polynomial oracle-time algorithm for convex integer minimization ⋮ \(n\)-fold integer programming in cubic time ⋮ \(N\)-fold integer programming and nonlinear multi-transshipment ⋮ A formulation of the wide partition conjecture using the atom problem in discrete tomography ⋮ Convex integer optimization by constantly many linear counterparts ⋮ The Graver complexity of integer programming ⋮ \(N\)-fold integer programming ⋮ Robust integer programming ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ Convex integer maximization via Graver bases ⋮ Properties of the \(d\)-dimensional Earth mover's problem ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Graphs of transportation polytopes ⋮ Random sampling of contingency tables via probabilistic divide-and-conquer ⋮ Huge multiway table problems ⋮ A characterization of odd-hole inequalities related to Latin squares

This page was built for publication: All Linear and Integer Programs Are Slim 3‐Way Transportation Programs