On Block-Structured Integer Programming and Its Applications

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer International Publishing
Pages153-177
Number of pages25
DOIs
StatePublished - 2019

Publication series

NameSpringer Optimization and Its Applications
Volume147
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

Fingerprint Dive into the research topics of 'On Block-Structured Integer Programming and Its Applications'. Together they form a unique fingerprint.

Cite this