Tournament Ranking: Duality and Efficiency
The feedback arc set problem on tournaments arises in a rich variety of applications, and has been studied extensively in several research fields over the past six decades. It is well known that this problem is $NP$-hard and admits a polynomial-time approximation scheme (PTAS) in general. A tournament $T=(V, A)$ is called cycle Mengerian (CM) if, for every nonnegative integral weight function defined on $A$, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. In 2020 Chen et al. obtained a structural characterization of all CM tournaments; however,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.31565
curl -X POST /api/v1/records/arxiv/2606.31565/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.31565/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'