Theory and Applications of N-Fold Integer Programming

2009/11/21 by Shmuel Onn, Onn, Shmuel
Computer Science · Mathematics · #05A #15A #51M #52A #52B #52C #62H #68Q #68R #68U #68W #90B #90C #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #cs.DS #math.CO #math.OC #msc:05A #msc:15A #msc:51M #msc:52A #msc:52B #msc:52C #msc:62H #msc:68Q #msc:68R #msc:68U #msc:68W #msc:90B #msc:90C

paper · pdf · doi:10.48550/arxiv.0911.4191

IMA Volume on Mixed Integer Nonlinear Programming, Frontier Series, Springer, to appear

openalex publication_date 2009/11/21 · arxiv created 2009/12/03 · arxiv updated 2010/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Combinatorial n-fold integer programming and applications
• An Algorithmic Theory of Integer Programming
• Algebraic Recipes for Integer Programming
• Short Rational Generating Functions For Multiobjective Linear Integer Programming
• Integer Programming with a Fixed Number of Variables