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

DOI10.1137/040610623zbMATH Open1128.90041OpenAlexW1975921416MaRDI QIDQ5757350FDOQ5757350

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

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

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)

Cited In (22)

• Markov Bases: A 25 Year Update
• A formulation of the wide partition conjecture using the atom problem in discrete tomography
• 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
• The double exponential runtime is tight for 2-stage stochastic ILPs
• \(N\)-fold integer programming and nonlinear multi-transshipment
• 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
• Huge multiway table problems

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)