The Convex Hull Membership (CHM) tests whether \( p \in conv(S) \) , where p and the n points of S lie in \( \mathbb { R}^m \) . CHM finds applications in Linear Programming, Computational Geometry, and Machine Learning. The Triangle Algorithm (TA), previously developed, in \( O(1/\varepsilon ^2) \) iterations computes \( p^{\prime } \in conv(S) \) , either an \( \varepsilon \) - approximate solution , or a witness certifying \( p \not\in conv(S) \) . We first prove the equivalence of exact and approximate versions of CHM and Spherical -CHM, where \( p=0 \) and \( \Vert v\Vert =1 \) for each v in S . If for some \( M \ge 1 \) every non-witness with \( \Vert p^{\prime }\Vert \gt \varepsilon \) admits \( v \in S \) satisfying \( \Vert p^{\prime } - v\Vert \ge \sqrt {1+\varepsilon /M} \) , we prove the number of iterations improves to \( O(M/\varepsilon) \) and \( M \le 1/\varepsilon \) always holds. Equivalence of CHM and Spherical-CHM implies Minimum Enclosing Ball (MEB) algorithms can be modified to solve CHM. However, we prove \( (1+ \varepsilon) \) -approximation in MEB is \( \Omega (\sqrt {\varepsilon }) \) -approximation in Spherical-CHM. Thus, even \( O(1/\varepsilon) \) iteration MEB algorithms are not superior to Spherical-TA. Similar weakness is proved for MEB core sets. Spherical-TA also results a variant of the All Vertex Triangle Algorithm (AVTA) for computing all vertices of \( conv(S) \) . Substantial computations on distinct problems demonstrate that TA and Spherical-TA generally achieve superior efficiency over algorithms such as Frank–Wolfe, MEB, and LP-Solver.

We design a fast and robust algorithm named {All Vertex Traingle Algorithm (AVTA)} for detecting the vertices of the convex hull of a set of points in high dimensions. Our proposed algorithm is very general and works for arbitrary convex hulls. In addition to being a fundamental problem in computational geometry and linear programming, vertex enumeration in high dimensions has numerous applications in machine learning. In particular, we apply AVTA to design new practical algorithms for topic models and non-negative matrix factorization. For topic models, our new algorithm leads to significantly better reconstruction of the topic-word matrix than state of the art approaches. Additionally, we provide a robust analysis of AVTA and empirically demonstrate that it can handle larger amounts of noise than existing methods. For non-negative matrix we show that AVTA is competitive with existing methods that are specialized for this task.

Let G be an undirected graph with n vertices and m edges. A natural number λ is said to be a magic labeling, positive magic labeling, and fractional positive magic labeling, if the edges can be labeled with nonnegative integers, naturals, and rationale ≥1, respectively, so that for each vertex the sum of the labels of incident edges is λ. G is said to be regularizable if it has a positive magic labeling. Denoting the minimum positive magic labeling, the minimum fractional positive magic labeling, and the maximum vertex degree by λˆ *, λˆ *, and δ, respectively, we prove that λˆ * ≤ min {[n/2]δ, 2m, 2λˆ *). The bound 2m is also derivable from a characterization of regularizable graphs stated by Pulleyblank, and regularizability for graphs with nonbipartite components can be tested via the Bourjolly-Pulleyblank algorithm for testing 2-bicriticality in O(nm) time. We show that using the above bounds and maximum flow algorithms of Ahuja-Orlin-Tarjan regularizability (or 2-bicriticality) can be tested in T(n,m) = O(min{nm + n2&log nsquare;, nm log((n/m)&log nsquare; + 2)}), and λˆ *, as well as a 2-approximates solution to λˆ * can be computed in O(T(n, m)log n) time. For dense graphs, T(n, m) can be improved using parallel maximum flow algorithms. We exhibit a family of graphs for which [n/2]δ = 2λˆ * = 2λˆ *. Finally, given that the edges in G have nonnegative weights satisfying the triangle inequality, using a capacitated magic labeling solution, we construct a 2-approximate algorithm for the problem of covering all the vertices with optimal set of disjoint even cycles, each covering at least four vertices. © 1996 John Wiley & Sons, Inc.

The minimum-weight perfect matching problem for complete graphs ofnvertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integerk≤ log3n, and for any perfect matching algorithm that runs int(n) time and has an error bound of ƒ(n) times the optimal weight, anO(max{n2,t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + ƒ(3kn)) - 1 is given. By the selection ofkas appropriate functions ofn, heuristics that have better running times and/or error bounds than existing ones are derived.