On polynomial kernels for sparse integer linear programs
作者：
Highlights：
• This work initiates a rigorous study of preprocessing for Integer Linear Programs.
• We prove upper and lower bounds via the theoretical notion of kernelization.
• Known lower bounds inherited from other problems only apply to dense instances.
• We show that sparsity alone is not sufficient to guarantee positive results.
• On sparse instances the domain size is the determining factor for kernelization.
摘要
•This work initiates a rigorous study of preprocessing for Integer Linear Programs.•We prove upper and lower bounds via the theoretical notion of kernelization.•Known lower bounds inherited from other problems only apply to dense instances.•We show that sparsity alone is not sufficient to guarantee positive results.•On sparse instances the domain size is the determining factor for kernelization.
论文关键词：Parameterized complexity,Kernelization,Integer linear programs
论文评审过程：Received 29 January 2015, Revised 29 September 2015, Accepted 19 December 2015, Available online 12 January 2016, Version of Record 1 April 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2015.12.002
