Hierarchical threshold structure in Max-Cut with geometric edge weights
Abstract
We study a family of weighted Max-Cut instances on the complete graph $K_n$ in which edge weights decrease geometrically in lexicographic order: the $i$-th edge has weight $r^{N-i}$ where $N=\binom{n}{2}$. For $r\ge 2$, the lexicographically first cut is optimal; for $r=1$, all edges have equal weight and the balanced partition wins. In this paper we study the intermediate regime $1< r
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 9 March 2026
- Language
- EN
- Document type
- Preprint