Integer Linear Programmering (ILP) kan ses som det arketypiska problemet för NPfullständiga optimeringsproblem, och ett brett spektrum av problem inom artificiell intelligens löses i praktiken via en översättning till ILP. Trots sitt stora utbud av tillämpningar, är bara få dragbara fragment av ILP kända, förmodligen den mest framträdande av vilka bygger på begreppet total enodularitet. Med helt olika tekniker identifierar vi nya dragbara fragment av ILP genom att studera strukturella parameteriseringar av begränsningsmatrisen inom ramen för parameteriserad komplexitet. I synnerhet visar vi att ILP är fast-parameter dragbar när parameteriseras av träddjupet av begränsningsmatrisen och det maximala absoluta värdet av någon koefficient som förekommer i ILP instans. Tillsammans med matchande hårdhetsresultat för den mer allmänna parametern trädbredd ger vi en översikt över komplexiteten hos ILP w.r.t. Dekompositionsparametrar som definieras på begränsningsmatrisen.
Ganian och Ordyniak REF visade fast-parameter dragbarhet för den kombinerade parametern träddjup och det största absoluta värdet i begränsningsmatrisen, och kontrasterade detta med ett W[1]-härdighet resultat när träddjupet byts mot trädbredd.
The Complexity Landscape of Decompositional Parameters for ILP
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}