.png){kind=icon}
返回
Approximation Algorithms for Integer Programming with Resource Augmentation
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.20.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
求解一般整数规划（IP）是NP难的。IP的经典算法[Papadimitriou, J.ACM '81]的运行时间为n(O(m))(m·max{Δ, ∥b∥∞})(O(m²))，其中m为约束数量，n为变量数量，Δ和∥b∥∞分别为约束矩阵和约束右端向量中元素的最大绝对值。该运行时间关于m呈指数增长，当m为常数时为伪多项式时间。近年来，针对所谓n重IP的FPT（固定参数可解）算法研究十分广泛，这类问题可能具有大量约束，但其约束矩阵满足特定的分块结构。值得注意的是，这些FPT算法将Δ以及某些小子矩阵的行列数作为参数。若Δ不被视为参数，则即使其他参数均为常数，运行时间仍为伪多项式时间。本文探索求解IP时时间和精度的权衡。我们证明，对于任意小ε > 0，存在一个针对m约束的IP算法，其运行时间为f(m, ε)·poly(|I|)，并返回一个近似可行解，该解对约束的违反程度不超过εΔ。此外，对于n重IP，我们建立了类似结果——算法运行时间取决于小子矩阵的行列数以及1/ε，并返回轻微违反约束的解。同时，两种解均保证其目标值不劣于满足约束的最优目标值。作为应用，我们的结果可用于获得多维背包问题以及调度问题的加性近似方案。
Keyword:
Approximation algorithms
Resource augmentation
Integer programs
n-fold IPs
期刊
机构
查看更多机构
引用论文
暂无论文信息