Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula
Bérczi, Gehér, Imolay, Lovász, and Schwarcz (SIAM J. Discrete Math. 40(2026), 308--335) asked whether every set function of bounded variation is a difference of two bounded submodular functions, and how to determine the optimum in a monotonic sum-decomposition of a planar graph cut function. In this paper, we answer both questions and obtain quantitative extensions. For the first question, we characterize the continuous profiles $f:[0,1]\to\R$ for which $A\mapsto f(m(A))$ is a bounded submodular difference on an atomless probability space. More precisely, we express the minimum oscillation…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.40032
curl -X POST /api/v1/records/arxiv/2610.40032/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.40032/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'