论文用互补优化方法求解红蓝分离集，并用于区分人机文本。
资讯摘要
论文研究计算几何中的最小红蓝分离集问题（MRBSSP），提出紧凑的集合覆盖整数线性规划（ILP）形式、安全预处理规则、GRASP 启发式，以及基于逻辑的 Benders 分解（LBBD）和分支-切割（BBC）两种精确方法。在最多 500 个顶点的 250 个随机图上，ILP 给出最佳可行解，LBBD 下界最强、平均最优性差距最小，BBC 最常证明最优性。作者还将该方法用于基于词汇图特征区分人类与 AI 生成文本。
要点速读
- 论文提出集合覆盖 ILP、预处理规则、GRASP，以及 LBBD 和 BBC 两种精确方法，并与文献中的 VNS 比较。
- 在 250 个随机图上，ILP 可行解最佳，LBBD 下界最强、平均最优性差距最小，BBC 最常证明最优。
- 在 42 个人机文本区分实例上，BBC 平均最优性差距最小并证明 16 个最优解，GRASP 优于 VNS。
中文摘要由 AI 根据公开来源生成，可能存在理解偏差；具体能力、数字、开放时间等信息请以原文为准。
采集于 2026/11/3 08:00:27（北京时间）。 arXiv 日期为本次公告时间，论文初次投稿日期请查看原文版本记录。