A Polynomial Algorithm for Minimizing $k$-Distant Submodular Functions
| Autor: | Mizutani, Ryuhei |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | This paper considers the minimization problem of relaxed submodular functions. For a positive integer $k$, a set function is called $k$-distant submodular if the submodular inequality holds for every pair whose symmetric difference is at least $k$. This paper provides a polynomial time algorithm to minimize $k$-distant submodular functions for a fixed positive integer $k$. This result generalizes the tractable result of minimizing 2/3-submodular functions, which satisfy the submodular inequality for at least two pairs formed from every distinct three sets. Comment: 13 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|