Theory and computation of sparse cutting planes
MetadataShow full item record
Cutting plane plays an important role in the theory and computation of integer programming. Nowadays, most state-of-the-art integer programming solvers tend to bias their cutting plane selection towards sparse ones, which emphasizes the significance of sparse cutting planes. In this thesis, we conduct a comprehensive study of sparse cutting planes and prove several theoretical results. We also develop a new approximation algorithm for sparse packing integer programs.