An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909779795902464 |
|---|---|
| author | Laddha, Aditi Pittu, Madhusudhan Reddy |
| author_facet | Laddha, Aditi Pittu, Madhusudhan Reddy |
| contents | Computing the permanent of a non-negative matrix is a computationally challenging, \#P-complete problem with wide-ranging applications. We introduce a novel permanental analogue of Schur's determinant formula, leveraging a newly defined \emph{permanental inverse}. Building on this, we introduce an iterative, deterministic procedure called the \emph{permanent process}, analogous to Gaussian elimination, which yields constructive and algorithmically computable upper bounds on the permanent. Our framework provides particularly strong guarantees for matrices exhibiting approximate diagonal dominance-like properties, thereby offering new theoretical and computational tools for analyzing and bounding permanents. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08121 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality Laddha, Aditi Pittu, Madhusudhan Reddy Discrete Mathematics Combinatorics Computing the permanent of a non-negative matrix is a computationally challenging, \#P-complete problem with wide-ranging applications. We introduce a novel permanental analogue of Schur's determinant formula, leveraging a newly defined \emph{permanental inverse}. Building on this, we introduce an iterative, deterministic procedure called the \emph{permanent process}, analogous to Gaussian elimination, which yields constructive and algorithmically computable upper bounds on the permanent. Our framework provides particularly strong guarantees for matrices exhibiting approximate diagonal dominance-like properties, thereby offering new theoretical and computational tools for analyzing and bounding permanents. |
| title | An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2509.08121 |