Parameterized maximization

DSpace Repository


Dokumentart: Report
Date: 2001
Source: WSI ; 2001 ; 22
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Tübingen / Wilhelm-Schickard-Institut für Informatik
Show full item record


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.

This item appears in the following Collection(s)