Characterization and equilibrium of bichromatic max-sum matchings
We study maximum-sum red-blue matchings and matching equilibrium for finite planar point sets. For a red-blue perfect matching $M = \{(a_i,b_i) : 1 \le i \le n\}$, we define the gain of a directed red cycle as the change in total weight produced by cyclically shifting the corresponding blue partners. We prove that $M$ is maximum-sum if and only if every directed red cycle has nonpositive gain, and we derive a geometric sufficient condition for optimality from cyclic intersections of distance-difference regions. We then characterize balanced matchings, in which all red-blue perfect matchings…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.10070
curl -X POST /api/v1/records/arxiv/2607.10070/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.10070/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'