integrality gap
时间: 2024-04-24 18:27:47 浏览: 8
integrality gap是指在整数规划问题中,最优整数解与最优线性规划解之间的差距。在引用\[1\]中提到的问题中,integrality gap为2,即最优整数解的值是最优线性规划解的两倍。这个问题与Max-Sat问题相关。引用\[2\]中给出了一个关于整数规划的函数FING的定义,其中x是一个n维的0-1向量,r是一个取值在有限域Zp上的常数。而引用\[3\]中提到,在relaxation过程中,将x和y的取值范围改为实数\[0,1\]。综合这些信息,我们可以得出结论,这个问题的integrality gap为2,与Max-Sat问题有关。
#### 引用[.reference_title]
- *1* *2* *3* [高级算法部分笔记](https://blog.csdn.net/lengjiayi/article/details/112393551)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]