{ 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

CREATORKristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Daniel P. Szabo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE141 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-25664

Browse the full library · About the Tower of Babel