Vi anser att nya parameteriseringar av NP-optimering problem som har nontrivial lägre och / eller övre gränser på sin optimala lösning storlek. Den naturliga parametern, menar vi, är kvantiteten över den nedre gränsen eller under den övre gränsen. Vi visar att för varje problem i MAX SNP, det optimala värdet begränsas nedan av en obunden funktion av indata-storleken, och att ovanstående garanti parameterisering med avseende på denna lägre gräns är fast-parameter dragbar. Vi observerar också att approximationsalgoritmer ger icke-triviala lägre eller övre gränser på lösningsstorleken och att ovanstående eller lägre garantifråga med avseende på dessa gränser är fastparameterdragbar för en subklass av NPoptimiseringsproblem. Vi introducerar sedan begreppet "täta" nedre och övre gränser och uppvisar ett antal problem för vilka ovanstående-garanti och under-garanti parameteriseringar med avseende på en snäv gräns är fast-parameter dragbar eller W-hård. Vi visar att om vi parameteriserar "tillräckligt" ovanför eller under de snäva gränserna, då dessa parameteriserade versioner är inte fastparameterdragbara om inte P = NP, för en subklass av NP-optimering problem. Vi listar också flera vägar att utforska i detta paradigm.
Det problem som vi behandlar i detta dokument hamnar i en klass av problem som införts av Mahajan, Raman och Sikdar REF.
Parameterizing above or below guaranteed values
{'venue': 'J. Comput. System Sci', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}