Theory and Applications of n-Fold Integer Programming

DOI10.1007/978-1-4614-1927-3_20MaRDI QIDQ2897311zbMATH OpenOpenAlexFDO

Authors Shmuel Onn

Publication date 10 July 2012

Published in Mixed Integer Nonlinear Programming (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationdata securitydiscrete optimizationgraver basegraver complexityinteger programmingmul-ticommodity flowmultiway tablenonlinear optimizationprivacy in databasestransportation problem

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We overview our recently introduced theory of n-fold integer programming which enables the polynomial time solution of fundamental linear and nonlinear integer programming problems in variable dimension. We demonstrate its power by obtaining the first polynomial time algorithms in several application areas including multicommodity flows and privacy in statistical databases.

Recommendations

• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial \(n\)-fold integer programming and applications
• \(N\)-fold integer programming
• Integer programming as a framework for optimization and approximability
• scientific article; zbMATH DE number 1104299
• scientific article; zbMATH DE number 2205356
• scientific article; zbMATH DE number 4089320
• scientific article; zbMATH DE number 562287
• scientific article; zbMATH DE number 42654
• Evaluating and tuning n-fold integer programming

Cited in

(16)

• Evolution and state-of-the-art in integer programming
• Efficient solutions for weight-balanced partitioning problems
• Future paths for integer programming and links to artificial intelligence
• \(n\)-fold integer programming in cubic time
• Combinatorial \(n\)-fold integer programming and applications
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• Huge multiway table problems
• Convex discrete optimization
• Huge unimodular \(n\)-fold programs
• A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs
• scientific article; zbMATH DE number 3982918 (Why is no real title available?)
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• Higher-dimensional sieving for the number field sieve algorithms
• Mathematical programming formulations for the collapsed k-core problem
• \(N\)-fold integer programming and nonlinear multi-transshipment
• \(N\)-fold integer programming

This page was built for publication: Theory and Applications of n-Fold Integer Programming

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