Approximating Submodular Matroid-Constrained Partitioning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913922645229568 |
|---|---|
| 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 | The submodular partitioning problem asks to minimize, over all partitions $P$ of a ground set $V$, the sum of a given submodular function $f$ over the parts of $P$. The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, $k$-cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by $P$, and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition $P$ in which there exists some basis that is separated by $P$. We explore the approximability of this problem and its variants, reaching the state of the art for the special case of symmetric submodular functions, and provide results for monotone and general submodular functions as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19507 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating Submodular Matroid-Constrained Partitioning Bérczi, Kristóf Chandrasekaran, Karthekeyan Király, Tamás Szabo, Daniel P. Data Structures and Algorithms Discrete Mathematics The submodular partitioning problem asks to minimize, over all partitions $P$ of a ground set $V$, the sum of a given submodular function $f$ over the parts of $P$. The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, $k$-cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by $P$, and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition $P$ in which there exists some basis that is separated by $P$. We explore the approximability of this problem and its variants, reaching the state of the art for the special case of symmetric submodular functions, and provide results for monotone and general submodular functions as well. |
| title | Approximating Submodular Matroid-Constrained Partitioning |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2506.19507 |