Integer linjära program (ILP) är en allmänt tillämpad ram för att hantera kombinatoriska problem som uppstår i praktiken. Det är känt, t.ex. genom framgången med CPLEX, att förbehandling och förenkling i hög grad kan påskynda processen med att optimera en ILP. Det nuvarande arbetet syftar till att främja den teoretiska förståelsen av förbehandling för ILPs genom att initiera en rigorös studie inom ramen för parameteriserad komplexitet och kärnorisering. Ett känt resultat av Lenstra (Matematics of Operations Research, 1983) visar att genomförbarheten av någon ILP med n variabler och m begränsningar kan bestämmas i tid O(c n 3 ·m c ′ ). Således, genom en folklore argument, medger någon sådan ILP en kärnorisering till en likvärdig instans av storlek O(c n 3 ). Det är känt, att om inte NP-coNP/poly och polynomhierarkin kollapsar, är ingen kärnorisering med storleksbundet polynom i n möjlig. Denna lägre gräns gäller dock endast för fallet när begränsningar kan omfatta ett godtyckligt antal variabler eftersom det följer av lägre gränser för SAT och Hitting Set, vars avgränsade aritetsvarianter medger polynomiska kärnor. Vi anser att genomförbarhetsproblemet för ILPs Ax ≤ b där A är en r-row-sparse-matris parameteriserad av antalet variabler. Vi visar att kärnan i detta problem beror starkt på omfattningen av variablerna. Om intervallet är obundet så medger inte detta problem en polynomisk kärnorisering om inte NP  med coNP/poly. Om, å andra sidan, intervallet för varje variabel är polynomiskt avgränsad i n så får vi en polynomiell kärnorisering. Dessutom har detta också för det mer allmänna fallet när det maximala intervallet d är en ytterligare parameter, dvs. storleken som erhålls är polynom i n + d.
Kratsch REF studerar kärnan i glesa ILP:er med små koefficienter.
On Polynomial Kernels for Sparse Integer Linear Programs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}