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

approximation algorithmscofinetialitycombinatorial optimizationcontingency tablesconvex polytopesdata securitydisclosureinteger programminglinear programmingMarkov basismulticommodity flowsmultiway tableprivacystatistical tablestrongly polynomial timetoric idealtransportation problems

Mathematics Subject Classification ID

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

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

(23)

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

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)