Metraipolis › archive › dc_e870880ff90d
Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation — arXiv:2610.41081
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41081
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T07:50:31.813Z
- SHA-256 of the archived text
a698720962a510102f84d2dca0e2fa5b1830d89afe4ad1599e03af90d7d5539a- Stable URL of this page
https://metraipolis.com/documento/dc_e870880ff90d
How to cite
Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation — arXiv:2610.41081 — arXiv (en), https://arxiv.org/abs/2610.41081 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e870880ff90d (Metraipolis archive dc_e870880ff90d, sha256 a698720962a510102f84d2dca0e2fa5b1830d89afe4ad1599e03af90d7d5539a)
BibTeX
@misc{dce870880ff90d,
title = {Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation — arXiv:2610.41081},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41081},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e870880ff90d; sha256 a698720962a510102f84d2dca0e2fa5b1830d89afe4ad1599e03af90d7d5539a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41081. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the so-called Minimum Red''Blue Separating Set Problem (MRBSSP) which arises from computational geometry. In particular, we propose a compact Set-Cover ILP formulation, safe preprocessing rules, a Greedy Randomized Adaptive Search Procedure (GRASP), and two exact approaches: one is based on Logic-Based Benders Decomposition (LBBD) approach, and the second represents a novel Branch-and-Benders-Cut (BBC) approach. These two exact approaches are compared to ILP--alongside GRASP and the Variable Neighborhood Search (VNS) from literature. Experiments on 250 random graphs with up to 500 vertices reveal complementary strengths: ILP yields the best feasible solutions, LBBD provides the strongest lower bounds and smallest mean optimality gap, and BBC certifies optimality most frequently. We further introduce an NLP application distinguishing human- and AI-generated texts through vocabulary-based graph features. On 42 instances, BBC achieves the smallest mean optimality gap, certifying 16 optima, while GRASP outperforms VNS. Structural analysis of optimal vocabulary separators identifies 113 mandatory and 151 replaceable features across 272 tests, highlighting substantial variability among optimal solutions. Overall, our results demonstrate the effectiveness of complementary optimization strategies and the interpretability of optimal vocabulary-based discrimination. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno). Categorie arXiv: Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2610.41081 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T07:49:31.028Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).