2025-11-22T13:49:16.309918

New Algorithm for Combinatorial $n$-folds and Applications

Jansen, Kahler, Pirotton et al.

Block-structured integer linear programs (ILPs) play an important role in various application fields. We address $n$-fold ILPs where the matrix $\mathcal{A}$ has a specific structure, i.e., where the blocks in the lower part of $\mathcal{A}$ consist only of the row vectors $(1,\dots,1)$. In this paper, we propose an approach tailored to exactly these combinatorial $n$-folds. We utilize a divide and conquer approach to separate the original problem such that the right-hand side iteratively decreases in size. We show that this decrease in size can be calculated such that we only need to consider a bounded amount of possible right-hand sides. This, in turn, lets us efficiently combine solutions of the smaller right-hand sides to solve the original problem. We can decide the feasibility of, and also optimally solve, such problems in time $(n r Î)^{O(r)} \log(\|b\|_\infty),$ where $n$ is the number of blocks, $r$ the number of rows in the upper blocks and $Î=\|A\|_\infty$. We complement the algorithm by discussing applications of the $n$-fold ILPs with the specific structure we require. We consider the problems of (i) scheduling on uniform machines, (ii) closest string and (iii) (graph) imbalance. Regarding (i), our algorithm results in running times of $p_{\max}^{O(d)}|I|^{O(1)},$ matching a lower bound derived via ETH. For (ii) we achieve running times matching the current state-of-the-art in the general case. In contrast to the state-of-the-art, our result can leverage a bounded number of column-types to yield an improved running time. For (iii), we improve the parameter dependency on the size of the vertex cover.

academic

組合的 $n$ -foldに対する新しいアルゴリズムと応用

基本情報

論文ID: 2409.04212
タイトル: New Algorithm for Combinatorial $n$ -folds and Applications
著者: Klaus Jansen, Kai Kahler, Lis Pirotton, Malte Tutas (キール大学)
分類: cs.DS (データ構造とアルゴリズム)
発表時期: 2024年9月 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2409.04212

要約

本論文は、行列 $A$ の下部ブロックが $(1,\ldots,1)$ ベクトルのみで構成される特殊構造を持つ組合的 $n$ -fold整数線形計画法(ILP)問題を研究している。著者らは分割統治法を提案し、右辺ベクトルのサイズを反復的に削減することで元の問題を分解する。本アルゴリズムは時間計算量 $(nr\Delta)^{O(r)}\log(\|b\|_\infty)$ で実行可能性を判定し最適解を求めることができる。ここで $n$ はブロック数、 $r$ は上部ブロックの行数、 $\Delta=\|A\|_\infty$ である。論文はさらに3つの重要な応用における本アルゴリズムの有効性を示している：(1)均一機械スケジューリング、(2)最近傍文字列問題、(3)グラフ不均衡問題。

研究背景と動機

問題の重要性

整数線形計画法は計算機科学における中核的なNP困難問題の1つであり、Karpの21個の古典的NP完全問題に含まれている。一般的なILP問題は計算上困難であるが、特殊構造を持つILP部分クラスはより効率的な求解アルゴリズムを実現できる。

既存手法の限界

$n$ -fold ILPに対する現在の最良アルゴリズムの時間計算量は $(nt)^{(1+o(1))} \cdot 2^{O(rs^2)}(rs\Delta)^{O(r^2s+s^2)}$ である。組合的 $n$ -fold ILP( $s=1$ の場合)に対しては、既存アルゴリズムのパラメータ依存性は $(r\Delta)^{O(r^2)}$ である。

研究動機

著者らは、組合的 $n$ -fold ILPの特殊構造(下部ブロックが全1ベクトルのみで構成される)を利用して、より効率的なアルゴリズムを設計できることを発見した。分割統治戦略と動的計画法を通じて、パラメータ依存性を $O(r^2)$ から $O(r)$ に改善できる。

核心的貢献

新しいアルゴリズム設計: 組合的 $n$ -fold ILPに特化した分割統治アルゴリズムを提案し、時間計算量は $(nr\Delta)^{O(r)}\log(b_{\text{def}})$
理論的改善: パラメータ依存性を $(r\Delta)^{O(r^2)}$ から $(nr\Delta)^{O(r)}$ に改善
応用検証: 3つの重要な問題でアルゴリズムの効果を検証：
- 均一機械スケジューリング： $p_{\max}^{O(d)}|I|^{O(1)}$ を達成し、ETH下界と一致
- 最近傍文字列問題：有界列タイプの場合に改善を獲得
- グラフ不均衡問題：頂点被覆パラメータ依存性を改善
技術的革新: 新しい解構造分析と組合的手法を導入

手法の詳細

問題定義

組合的 $n$ -fold ILPは以下のように定義される： $\max\{c^T x | Ax = b, x \in \mathbb{Z}_{\geq 0}^h\}$

ここで制約行列 $A$ は特殊構造を持つ： $A = \begin{pmatrix} A_1 & A_2 & \cdots & A_n \\ \mathbf{1}_{t_1}^T & 0 & \cdots & 0 \\ 0 & \mathbf{1}_{t_2}^T & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{1}_{t_n}^T \end{pmatrix}$

中核的なアルゴリズムアーキテクチャ

1. 分割統治戦略

アルゴリズムはトップダウンの分割統治法を採用し、元の問題を再帰的に分解する：

各反復で上部右辺ベクトル $b^{\uparrow}$ を半減させる
問題を2つの部分問題に分解：奇偶制約問題と小規模問題
$I = O(\log b_{\max}^{\downarrow})$ 回の反復を通じて基本ケースに到達

2. 解の構造分析

重要な技術的洞察：

サポート界限: Eisenbrand-Shmonin定理を利用し、各ブロックのサポートサイズは有界： $|supp(x_k)| \leq K = 2(r+1)\log(4(r+1)\Delta)$
下部RHS決定性: 式(3)を通じて各反復の下部右辺ベクトルを一意に決定
上部RHS有界性: 小部分問題の上部RHSは $D = nK\Delta$ で界定される