Parameterized maximization

Abstract

Maximization problems are usually considered as parameterized problems taking as parameter the entity which has to be maximized. In contrast, we study here another parameterization, given by the dual bounding constant in the case of an integer linear program formulation. This way, it makes sense to consider parameterized maximization problems such that it can be well motivated to expect the parameter to be small. We give examples of fixed parameter tractable maximization problems, as well as of problems which are not expected to be fixed parameter tractable unless FPT=W[1], a hypothesis which is generally considered unlikely in parameterized complexity.