arXiv preprint ·
Determinant maximization subject to a partition matroid constraint via stable distributions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given vectors $v_i \in {\mathbb R}^d$, we consider the problem of choosing a set $I$ independent in a partition matroid in order to maximize the determinant $\det (\sum_{i \in I} v_i v_i^T)$. Our main result is a polynomial-time approximation algorithm that finds a solution of value $det ( \sum_{i \in I} v_{i} v_{i}^T) \geq e^{-O(d)} OPT$, where $OPT = \max_{I^*} det ( \sum_{i \in I^*} v_{i} v_{i}^T)$. For partition matroids of rank $m \leq d$, we give a similar result for approximating the $m$-dimensional volume spanned by the chosen vectors, within a factor of $e^{O(m)}$. This matches earlier known algorithms that estimate the optimal value but do not find the corresponding solution, up to a constant in the exponent. Similar to these estimation algorithms, our algorithm is based on the saddle-point relaxation proposed by Nikolov and Singh. A new ingredient is a randomized transformation based on $1/2$-stable distributions, which converts the saddle-point relaxation into a more convenient multilinear relaxation.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
A quantitative tree-likeness bound from average hyperbolicity
A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.