A characterization theorem and an algorithm for a convex hull problem
From MaRDI portal
Publication:2341220
DOI10.1007/s10479-014-1707-2zbMath1310.90072arXiv1204.1873OpenAlexW2073416959MaRDI QIDQ2341220
Publication date: 23 April 2015
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.1873
minimaxlinear programmingdualityconvex hullapproximation algorithmsFrank-Wolfe algorithmGilbert's algorithm
Related Items (7)
Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries ⋮ Robust vertex enumeration for convex hulls in high dimensions ⋮ Space exploration via proximity search ⋮ An algorithmic separating hyperplane theorem and its applications ⋮ QuickhullDisk: a faster convex hull algorithm for disks ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ First-order methods for the convex hull membership problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Smooth minimization of non-smooth functions
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- A new polynomial-time algorithm for linear programming
- Sets of efficient points in a normed space
- Small-dimensional linear programming and convex hulls made easy
- An optimal convex hull algorithm in any fixed dimension
- On linear programming and matrix scaling over the algebraic numbers
- Semidefinite programming and matrix scaling over the semidefinite cone.
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- An algorithmic separating hyperplane theorem and its applications
- Output-sensitive results on convex hulls, extreme points, and related problems
- A randomized algorithm for fixed-dimensional linear programming
- The many facets of linear programming
- A subexponential bound for linear programming
- A characterization theorem and an algorithm for a convex hull problem
- A procedure of Chvátal for testing feasibility in linear programming and matrix scaling
- A randomized polynomial-time simplex algorithm for linear programming
- Mollified Zone Diagrams and Their Computation
- Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge
- The Efficiency of the Simplex Method: A Survey
- Linear Programming in Linear Time When the Dimension Is Fixed
- Diagonal Matrix Scaling and Linear Programming
- Sequential greedy approximation for certain convex optimization problems
- Linear Optimization Queries
- A combinatorial bound for linear programming and related problems
- Coresets for polytope distance
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex Set
This page was built for publication: A characterization theorem and an algorithm for a convex hull problem
