2020/02/18 by Jana Cslovjecsek, Friedrich Eisenbrand, Cslovjecsek, Jana +7
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.CC #math.OC
paper · pdf · doi:10.48550/arxiv.2002.07745
arxiv created 2020/08/03 · arxiv updated 2020/08/04
We consider integer and linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent and efficiently solvable sub-problems if a small number of constraints is deleted. A prominent example are n-fold integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within ℓ1-distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with n-fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.