A characterization theorem and an algorithm for a convex hull problem

DOI10.1007/S10479-014-1707-2zbMath1310.90072arXiv1204.1873OpenAlexW2073416959MaRDI QIDQ2341220

Bahman Kalantari

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

zbMATH Keywords

minimaxlinear programmingdualityconvex hullapproximation algorithmsFrank-Wolfe algorithmGilbert's algorithm

Mathematics Subject Classification ID

Linear programming (90C05)

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