Integrality Gap

释义 Definition

整数性差距（整数间隙）：在组合优化/整数规划中，用来衡量整数解最优值与其线性规划（或其他凸）松弛的最优值之间差距的指标，常以比值表示。

• 对最小化问题，常见定义：\(\text{IG}=\frac{\text{OPT}_{IP}}{\text{OPT}_{LP}}\ge 1\)
• 对最大化问题，常见定义：\(\text{IG}=\frac{\text{OPT}_{LP}}{\text{OPT}_{IP}}\ge 1\)
  （不同文献可能在最大化/最小化时采用不同约定，但核心含义相同：松弛与整数最优之间的“差”有多大。）

发音 Pronunciation (IPA)

/ˌɪntɪˈɡrælɪti ɡæp/

例句 Examples

The integrality gap of this relaxation is 2.
这个松弛的整数性差距是 2。

Even with a strong LP relaxation, the integrality gap can remain large, which limits how good an approximation algorithm based on rounding can be.
即使线性规划松弛很强，整数性差距仍可能很大，从而限制了基于舍入的近似算法所能达到的效果。

词源 Etymology

integrality 来自 integral（“整数的/整体的”），在优化语境里指“解必须取整数”的性质；gap 表示“差距”。合起来即“整数约束带来的最优值与松弛最优值之间的差距”。该术语广泛用于近似算法与优化理论中，用于刻画“松弛的紧致程度”。

相关词 Related Words

• Approximation
• Linear Programming
• Integer Programming
• Relaxation
• Rounding
• Polytope
• Duality
• Vertex Cover
• Max-Cut
• NP-hard

文献与作品 Literary Works

• The Design of Approximation Algorithms（Williamson & Shmoys）——用大量实例讨论松弛与integrality gap对近似比的限制。
• Approximation Algorithms（Vazirani）——在LP松弛、舍入与近似分析中频繁出现该术语。
• Combinatorial Optimization: Polyhedra and Efficiency（Schrijver）——从多面体/整数规划角度涉及相关概念与差距现象。
• Goemans & Williamson, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems”（1995）——虽更常被引用于SDP近似，但相关讨论中常与“松弛质量/差距”并列提及。