On Block-Structured Integer Programming and Its Applications

Integer programming in a variable dimension is a crucial research topic that has received a considerable attention in recent years. A series of fixed parameter tractable (FPT) algorithms have been developed for a variety of integer programming that has a special block structure, and such results were later applied successfully in many classical combinatorial optimization problems to derive FPT or approximation algorithms. From a theoretical point of view, it is important to understand the overall landscape, and distinguish the structures of integer programming that are tractable vs. intractable or unknown so far. From the application point of view, it is important to understand how the structure of such integer programming is related to the structure of concrete combinatorial optimization problems. The goal of this survey is to summarize recent progress in theory and application of integer programming that has a block structure and point to important open problems in this research direction.