N-fold integer programming and nonlinear multi-transshipment

DOI10.1007/S11590-010-0231-9zbMATH Open1213.90180arXiv0903.4577OpenAlexW2040148572MaRDI QIDQ628649FDOQ628649

Authors: Raymond Hemmecke, Shmuel Onn, Robert Weismantel 

Publication date: 14 March 2011

Published in: Optimization Letters (Search for Journal in Brave)

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.

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

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
• scientific article; zbMATH DE number 3227644
• Multi-index fixed charge bi-criterion transshipment problem

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Higher Lawrence configurations.
• Integer Programming with a Fixed Number of Variables
• On the foundations of linear and integer linear programming I
• A polynomial oracle-time algorithm for convex integer minimization
• The Graver complexity of integer programming
• A finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The Complexity of Three-Way Statistical Tables
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• 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
• Convex integer maximization via Graver bases

Cited In (7)

• \(N\)-fold integer programming
• Using inverse optimization to learn cost functions in generalized Nash games
• Computing equilibria for integer programming games
• Title not available (Why is that?)
• The quadratic Graver cone, quadratic integer minimization, and extensions
• \(n\)-fold integer programming in cubic time
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding

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)