High-multiplicity N-fold IP via configuration LP
针对高重数N重整数规划，提出首个固定参数算法，利用配置线性规划的新近邻定理，在编码规模的多项式时间内求解，适用于块数远多于块类型的调度问题。
Abstract N -fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicity N -fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N -fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N -fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N -fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N -fold IP models for various scheduling problems.