Max-$k$-Cut via Node Features
We study the Max-$k$-Cut problem from a node-feature perspective, where each vertex is associated with a feature vector and edge weights are given by pairwise inner products. We first examine the semidefinite relaxation of Max-$k$-Cut from this perspective. Using a normal-cone argument, we derive a general sufficient condition for exactness of the Frieze--Jerrum relaxation and show that it is satisfied in two feature-structural regimes: perfect feature balance, where the aggregate feature vectors of the parts are equal, and feature dominance, where a small set of large nonnegative feature…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.08499
curl -X POST /api/v1/records/arxiv/2608.08499/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.08499/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'