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

Nuevo Algoritmo para nn-pliegues Combinatorios y Aplicaciones

Información Básica

  • ID del Artículo: 2409.04212
  • Título: New Algorithm for Combinatorial nn-folds and Applications
  • Autores: Klaus Jansen, Kai Kahler, Lis Pirotton, Malte Tutas (Universidad de Kiel)
  • Clasificación: cs.DS (Estructuras de Datos y Algoritmos)
  • Fecha de Publicación: Septiembre de 2024 (preimpresión en arXiv)
  • Enlace del Artículo: https://arxiv.org/abs/2409.04212

Resumen

Este artículo estudia problemas de programación lineal entera (ILP) con nn-pliegues combinatorios que poseen una estructura especial, donde la mitad inferior de la matriz AA consiste únicamente en vectores (1,…,1)(1,\ldots,1). Los autores proponen un método de divide y conquista que descompone el problema original mediante la reducción iterativa del tamaño del vector del lado derecho. El algoritmo puede determinar la viabilidad y resolver la solución óptima en complejidad temporal (nrΔ)O(r)log⁡(∥b∥∞)(nr\Delta)^{O(r)}\log(\|b\|_\infty), donde nn es el número de bloques, rr es el número de filas del bloque superior, y Δ=∥A∥∞\Delta=\|A\|_\infty. El artículo también demuestra la efectividad del algoritmo en tres aplicaciones importantes: (1) programación de máquinas uniformes, (2) problema de cadena más cercana, (3) problema de desbalance de grafos.

Antecedentes de Investigación y Motivación

Importancia del Problema

La programación lineal entera es uno de los problemas NP-difíciles centrales en la informática, incluido por Karp en los 21 problemas NP-completos clásicos. Aunque los problemas generales de ILP presentan desafíos computacionales, las subclases de ILP con estructura especial pueden resolverse mediante algoritmos más eficientes.

Limitaciones de Métodos Existentes

Para ILP con nn-pliegues, la mejor complejidad temporal del algoritmo actual es (nt)(1+o(1))⋅2O(rs2)(rsΔ)O(r2s+s2)(nt)^{(1+o(1))} \cdot 2^{O(rs^2)}(rs\Delta)^{O(r^2s+s^2)}. Para ILP con nn-pliegues combinatorios (es decir, cuando s=1s=1), la dependencia de parámetros del algoritmo existente es (rΔ)O(r2)(r\Delta)^{O(r^2)}.

Motivación de la Investigación

Los autores descubren que se puede aprovechar la estructura especial del ILP con nn-pliegues combinatorios (el bloque inferior contiene solo vectores de unos) para diseñar algoritmos más eficientes. Mediante estrategias de divide y conquista y programación dinámica, se puede mejorar la dependencia de parámetros de O(r2)O(r^2) a O(r)O(r).

Contribuciones Principales

  1. Diseño de Nuevo Algoritmo: Se propone un algoritmo de divide y conquista especializado para ILP con nn-pliegues combinatorios, con complejidad temporal (nrΔ)O(r)log⁡(bdef)(nr\Delta)^{O(r)}\log(b_{\text{def}})
  2. Mejora Teórica: Se mejora la dependencia de parámetros de (rΔ)O(r2)(r\Delta)^{O(r^2)} a (nrΔ)O(r)(nr\Delta)^{O(r)}
  3. Verificación de Aplicaciones: Se verifica la efectividad del algoritmo en tres problemas importantes:
    • Programación de máquinas uniformes: alcanza pmax⁡O(d)∣I∣O(1)p_{\max}^{O(d)}|I|^{O(1)}, coincidiendo con la cota inferior bajo ETH
    • Problema de cadena más cercana: mejora obtenida en el caso de tipos de columnas acotados
    • Problema de desbalance de grafos: mejora en la dependencia de parámetros de cobertura de vértices
  4. Innovación Técnica: Se introduce nuevo análisis de estructura de soluciones y métodos combinatorios

Explicación Detallada del Método

Definición de la Tarea

El ILP con nn-pliegues combinatorios se define como: max⁡{cTx∣Ax=b,x∈Z≥0h}\max\{c^T x | Ax = b, x \in \mathbb{Z}_{\geq 0}^h\}

donde la matriz de restricciones AA posee estructura especial:

undefined