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

DOI10.1137/040610623MaRDI QIDQ5757350zbMATH OpenOpenAlexFDO

Authors 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 programmingcombinatorial optimizationcontingency tablesdisclosureinteger programmingapproximation algorithmstoric idealconvex polytopesMarkov basisdata securitymulticommodity flowsprivacymultiway tablestrongly polynomial timetransportation problemsstatistical tablecofinetiality

Mathematics Subject Classification ID

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

Recommendations

• Integer Programming and Combinatorial Optimization
• The Complexity of Three-Way Statistical Tables
• scientific article; zbMATH DE number 3854809
• Graphs of transportation polytopes
• On the dimension of polytopes of planar three-index transportation problems

Cited in

(22)

• Huge multiway table problems
• A formulation of the wide partition conjecture using the atom problem in discrete tomography
• Markov Bases: A 25 Year Update
• A polynomial oracle-time algorithm for convex integer minimization
• The Graver complexity of integer programming
• \(N\)-fold integer programming
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Integer Programming and Combinatorial Optimization
• Graphs of transportation polytopes
• Robust integer programming
• \(N\)-fold integer programming and nonlinear multi-transshipment
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
• The quadratic Graver cone, quadratic integer minimization, and extensions
• Convex integer optimization by constantly many linear counterparts
• Huge unimodular \(n\)-fold programs
• \(n\)-fold integer programming in cubic time
• Convex integer maximization via Graver bases
• Properties of the \(d\)-dimensional Earth mover's problem
• Estimating the number of zero-one multi-way tables via sequential importance sampling
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757350)