Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation

arXiv:2610.41081v1 Announce Type: new Abstract: 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.

Abstract: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.

Artificial Intelligence (cs.AI)

arXiv:2610.41081 [cs.AI]

(or arXiv:2610.41081v1 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2610.41081 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

În afara temei aiqbench

Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation

Subiecte conexe