{ s , t } \{s,t\} -Separating Principal Partition Sequence of Submodular Functions
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Daniel P. Szabo · 2025
Read { s , t } \{s,t\} -Separating Principal Partition Sequence of Submodular Functions by Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Daniel P. Szabo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25664.txt.
Description
Kristof Berczi, Karthekeyan Chandrasekaran, Tamas Kiraly, and Daniel P Szabo build a new chain of splits for submodular maps. Their 2025 paper in pure math grows on work by Narayanan. Such chains of splits help with fast methods and with grouping tasks. Their chain is made to keep two named points, s and t, on split sides.
They define the chain, prove it is there, and give a fast way to build it. The build runs in time that grows in a tame, polynomial way. Two uses show why the chain counts. First, it gives good near-best splits for a class of split tasks. Those tasks cover maps that rise in one way, and maps with a like sign rule. Second, it gives a fast way to aim the edges of a hypergraph. The aim task asks for strong links all round, and strong s-to-t links at once.
Catalog record
| CREATOR | Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Daniel P. Szabo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 141 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25664