Randomized rounding for the largest simplex problem

DOI10.1145/2746539.2746628MaRDI QIDQ2941583zbMATH OpenOpenAlexFDO

Authors Aleksandar Nikolov

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0036

zbMATH Keywords

convex optimizationcomputational geometryapproximation algorithmsdiscrepancy theory

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: The maximum volume $j$-simplex problem asks to compute the $j$-dimensional simplex of maximum volume inside the convex hull of a given set of $n$ points in $mathbb{Q}^d$. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of $e^{j/2+o(j)}$. The problem is known to be $mathrmNP$-hard to approximate within a factor of $c^j$ for some constant $c>1$. Our algorithm also gives a factor $e^{j+o(j)}$ approximation for the problem of finding the principal $jimesj$ submatrix of a rank $d$ positive semidefinite matrix with the largest determinant. We achieve our approximation by rounding solutions to a generalization of the $D$-optimal design problem, or, equivalently, the dual of an appropriate smallest enclosing ellipsoid problem. Our arguments give a short and simple proof of a restricted invertibility principle for determinants.

Recommendations

• On largest volume simplices and sub-determinants
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• Largest \(j\)-simplices in \(n\)-polytopes

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(26)

• A randomized polynomial-time simplex algorithm for linear programming
• Generalized scaling for the constrained maximum-entropy sampling problem
• A new contraction technique with applications to congruency-constrained cuts
• Near-optimal discrete optimization for experimental design: a regret minimization approach
• Fast algorithms for maximizing the minimum eigenvalue in fixed dimension
• Advances on strictly \(\varDelta \)-modular IPs
• Tridiagonal maximum-entropy sampling and tridiagonal masks
• Advances on strictly -modular IPs
• An improved private mechanism for small databases
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Approximation algorithms for \(D\)-optimal design
• An improved analysis of local search for max-sum diversification
• Gaussian process landmarking on manifolds
• Convex relaxation for the generalized maximum-entropy sampling problem
• scientific article; zbMATH DE number 7758358 (Why is no real title available?)
• Subdeterminant maximization via nonconvex relaxations and anti-concentration
• An outer-approximation algorithm for maximum-entropy sampling
• An outer-approximation algorithm for maximum-entropy sampling
• The augmented factorization bound for maximum-entropy sampling
• On the gap between hereditary discrepancy and the determinant lower bound
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Maximizing determinants under partition constraints
• Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
• Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
• On the parameterized intractability of determinant maximization
• The worst-case running time of the random simplex algorithm is exponential in the height

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Randomized rounding for the largest simplex problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941583)