Metraipolis › archive › dc_7ebe142d35ad
Efficient Algorithms for Subdeterminant Maximization under Partition Matroids — arXiv:2609.18103
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18103
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:09:18.205Z
- SHA-256 of the archived text
089e21826eadd276fac4f569c686a52a61ba27f25be763ed780e56a8309fb6fc- Stable URL of this page
https://metraipolis.com/documento/dc_7ebe142d35ad
How to cite
Efficient Algorithms for Subdeterminant Maximization under Partition Matroids — arXiv:2609.18103 — arXiv (en), https://arxiv.org/abs/2609.18103 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7ebe142d35ad (Metraipolis archive dc_7ebe142d35ad, sha256 089e21826eadd276fac4f569c686a52a61ba27f25be763ed780e56a8309fb6fc)
BibTeX
@misc{dc7ebe142d35ad,
title = {Efficient Algorithms for Subdeterminant Maximization under Partition Matroids — arXiv:2609.18103},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18103},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7ebe142d35ad; sha256 089e21826eadd276fac4f569c686a52a61ba27f25be763ed780e56a8309fb6fc},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18103. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves upon the current $k^{O(k)}$-approximation, and matches the current $e^k$-estimation guarantee, up to $O(1)$ factors in the exponent. Our algorithm is based on rounding the geometric max-min relaxation due to Nikolov-Singh'2016, using a continuous potential-driven process, and several new structural and analytic properties of this relaxation.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.18103 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.258Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).