arXiv cs.AI· Marko Djukanovi\'c, Sta\v{s}a Vuji\v{c}i\'c Stankovi\'c, \v{Z}iga Zebec, Christian Blum·· 1 天前AI 评分20
用优化算法求解最小红蓝分离集问题，并应用于人类与 AI 文本区分
Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation
AI 导读
研究针对计算几何中的最小红蓝分离集问题（MRBSSP）提出紧凑的集合覆盖 ILP 形式、安全预处理规则、GRASP 启发式，以及基于逻辑的 Benders 分解（LBBD）和新型 Branch-and-Benders-Cut（BBC）两种精确算法。
正文 · AI 翻译
摘要：我们研究源自计算几何的所谓最小红蓝分离集问题（MRBSSP）。具体而言，我们提出了一种紧凑的集合覆盖 ILP 公式、安全的预处理规则、一种贪心随机自适应搜索过程（GRASP），以及两种精确方法：一种基于逻辑型 Benders 分解（LBBD）方法，第二种代表一种新颖的分支与 Benders 割（BBC）方法。这两种精确方法与 ILP 进行比较——同时与文献中的 GRASP 和变邻域搜索（VNS）进行比较。在多达 500 个顶点的 250 个随机图上的实验揭示了互补优势：ILP 产生最佳可行解，LBBD 提供最强的下界和最小的平均最优性差距，而 BBC 最频繁地证明最优性。我们进一步引入了一个 NLP 应用，通过基于词汇的图特征区分人类和 AI 生成的文本。在 42 个实例上，BBC 实现了最小的平均最优性差距，证明了 16 个最优解，而 GRASP 优于 VNS。对最优词汇分离器的结构分析在 272 个测试中识别出 113 个强制特征和 151 个可替换特征，突显了最优解之间的巨大变异性。总体而言，我们的结果证明了互补优化策略的有效性以及基于词汇的最优区分的可解释性。
| 评论： | 36 页，5 幅图 |
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2610.41081 [cs.AI] |
| （或 arXiv:2610.41081v1 [cs.AI] 为此版本） | |
| https://doi.org/10.48550/arXiv.2610.41081 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Marko Djukanovic Dr. [查看电子邮件]
[v1]
2026 年 10 月 29 日星期四 23:52:02 UTC（3,932 KB）
来源：arXiv cs.AI · arxiv.org