Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.25664 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910030809268224 |
|---|---|
| author | Bérczi, Kristóf Chandrasekaran, Karthekeyan Király, Tamás Szabo, Daniel P. |
| author_facet | Bérczi, Kristóf Chandrasekaran, Karthekeyan Király, Tamás Szabo, Daniel P. |
| contents | Narayanan showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, and approximation algorithms. In this work, motivated by two applications, we develop a theory of $\{s,t\}$-separating principal partition sequence of a submodular function. We define this sequence, show its existence, and design a polynomial-time algorithm to construct it. We show two applications: (1) approximation algorithm for the $\{s,t\}$-separating submodular $k$-partitioning problem for monotone and posimodular functions and (2) polynomial-time algorithm for the hypergraph orientation problem of finding an orientation that simultaneously has strong connectivity at least $k$ and $(s,t)$-connectivity at least $\ell$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25664 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions Bérczi, Kristóf Chandrasekaran, Karthekeyan Király, Tamás Szabo, Daniel P. Data Structures and Algorithms Narayanan showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, and approximation algorithms. In this work, motivated by two applications, we develop a theory of $\{s,t\}$-separating principal partition sequence of a submodular function. We define this sequence, show its existence, and design a polynomial-time algorithm to construct it. We show two applications: (1) approximation algorithm for the $\{s,t\}$-separating submodular $k$-partitioning problem for monotone and posimodular functions and (2) polynomial-time algorithm for the hypergraph orientation problem of finding an orientation that simultaneously has strong connectivity at least $k$ and $(s,t)$-connectivity at least $\ell$. |
| title | $\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.25664 |