Parameterized maximization

DSpace Repository

Show simple item record

dc.contributor Tübingen / Wilhelm-Schickard-Institut für Informatik de_DE Fernau, Henning de_DE 2004-04-21 de_DE 2014-03-18T10:12:36Z 2004-04-21 de_DE 2014-03-18T10:12:36Z 2001 de_DE
dc.identifier.other 111265835 de_DE
dc.identifier.uri de_DE
dc.description.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. en
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-nopod de_DE
dc.rights.uri de_DE
dc.rights.uri en
dc.subject.classification Tübingen / Wilhelm-Schickard-Institut für Informatik de_DE
dc.subject.ddc 004 de_DE
dc.title Parameterized maximization en
dc.type Report (Bericht) de_DE 2012-10-11 de_DE
utue.publikation.fachbereich Sonstige - Informations- und Kognitionswissenschaften de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
dcterms.DCMIType Text de_DE
utue.publikation.typ report de_DE 1199 de_DE
utue.opus.portal wsi de_DE
utue.opus.portalzaehlung 2001.22000 de_DE
utue.publikation.source WSI ; 2001 ; 22 de_DE
utue.publikation.reihenname WSI-Reports - Schriftenreihe des Wilhelm-Schickard-Instituts für Informatik de_DE
utue.publikation.zsausgabe 2001, 22
utue.publikation.erstkatid 2919855-0


This item appears in the following Collection(s)

Show simple item record