English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider integer and linear programming problems for which the linearconstraints exhibit a (recursive) block-structure: The problem decomposes intoindependent and efficiently solvable sub-problems if a small number ofconstraints is deleted. A prominent example are $n$-fold integer programmingproblems and their generalizations which have received considerable attentionin the recent literature. The previously known algorithms for these problemsare based on the augmentation framework, a tailored integer programming variantof local search. In this paper we propose a different approach. Our algorithmrelies on parametric search and a new proximity bound. We show thatblock-structured linear programming can be solved efficiently via an adaptationof a parametric search framework by Norton, Plotkin, and Tardos in combinationwith Megiddo's multidimensional search technique. This also forms a subroutineof our algorithm for the integer programming case by solving a strongrelaxation of it. Then we show that, for any given optimal vertex solution ofthis relaxation, there is an optimal integer solution within $\ell_1$-distanceindependent of the dimension of the problem. This in turn allows us to find anoptimal integer solution efficiently. We apply our techniques to integer andlinear programming with $n$-fold structure or bounded dual treedepth, twobenchmark problems in this field. We obtain the first algorithms for thesecases that are both near-linear in the dimension of the problem and stronglypolynomial. Moreover, unlike the augmentation algorithms, our approach ishighly parallelizable.

Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time