N-fold integer programming and nonlinear multi-transshipment

DOI10.1007/S11590-010-0231-9MaRDI QIDQ628649zbMATH OpenOpenAlexFDO

Authors Raymond Hemmecke, Shmuel Onn, Robert Weismantel

Publication date 14 March 2011

Published in Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationnonlinear optimizationtransportation problemgraver basismulticommodity flow\(N\)-fold product

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Abstract: Inspired by a paper of R. W. Rosenthal, we investigate generalized Nash-equilibria of integer programming games. We show that generalized Nash-equilibria always exist and are related to an optimal solution of a so-called N-fold integer program. This link allows us to establish some polynomial time complexity results about solving this optimization problem and its inverse counter-part.

Recommendations

• \(N\)-fold integer programming
• Theory and Applications of n-Fold Integer Programming
• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial \(n\)-fold integer programming and applications
• scientific article; zbMATH DE number 562287
• Solving non-linear multi-index transportation problems
• scientific article; zbMATH DE number 2246654
• scientific article; zbMATH DE number 64776
• scientific article; zbMATH DE number 3227644
• Multi-index fixed charge bi-criterion transshipment problem

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• A finiteness theorem for Markov bases of hierarchical models
• A polynomial oracle-time algorithm for convex integer minimization
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Convex integer maximization via Graver bases
• Higher Lawrence configurations.
• Integer Programming with a Fixed Number of Variables
• Markov bases of three-way tables are arbitrarily complicated
• Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On the foundations of linear and integer linear programming I
• The Complexity of Three-Way Statistical Tables
• The Graver complexity of integer programming
• \(N\)-fold integer programming

Cited in

(8)

• \(N\)-fold integer programming
• Near-linear time algorithm for \(n\)-fold ILPs via color coding
• Using inverse optimization to learn cost functions in generalized Nash games
• An inapproximability of transshipment problems with permutable transit vectors
• Computing equilibria for integer programming games
• The quadratic Graver cone, quadratic integer minimization, and extensions
• scientific article; zbMATH DE number 7561568 (Why is no real title available?)
• \(n\)-fold integer programming in cubic time

This page was built for publication: \(N\)-fold integer programming and nonlinear multi-transshipment

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