Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 13 of 13 for “"Triangle inequality."”.
-
Geometric methods of accelerating triangle-inequality-based k-means.
One of the most frequent ways how to cluster data is k-means. The standard way of solving the problem is iterative Lloyd's algorithm. This algorithm performs many redundant calculations. Elkan's and Hamerly's algorithms, the heap algorithm and many others eliminate this redundancy by maintaining a …
-
Studies on ultraquasi-pseudometrics and orderings
… as it is easily obtained by altering the usual triangle inequality property, still yield interesting results. Indeed, a natural question that should arise is how does switching to the strong triangle inequality affect some of the results we already know about quasi-pseudometrics. On some points …
-
Epistemic Utility
… for the view that these divergences satisfy the triangle inequality. As such, the argument that these divergences are symmetric and the argument that they satisfy the triangle inequality stand or fall together. But the triangle inequality is inconsistent with Pettigrew’s other constraints. Thus, …
-
Metric Representations Of Networks
… metric-like spaces -- governed by a generalized triangle inequality -- and then leveraging this structure to facilitate the analysis. Networks encode relationships between pairs of nodes, however, the relationship between two nodes can be independent of the other ones and need not be defined for …
-
Faster k-means clustering.
… uniform random data. Finally, we reformulate the triangle inequality to constrain the search space for a point's nearest center to an annular region centered at the origin. For uniform random data, annulus k-means is competitive with or much faster than other algorithms in low dimension (d < 20), …
-
The Injective Envelope as the Space of Extremal Functions
… which satisfy two inequalities derived from the triangle inequality. One of these inequalities, along with a minimality requirement, is used to define the extremal functions. We compare the extremal functions to other classes of functions defined similarly using one of the two inequalities from …
-
An examination of heuristic algorithms for the travelling salesman problem
… were programmed for symmetric TSPs where the triangle inequality holds, and were tested on micro computer. The best of the quickest heuristics was the furthest insertion heuristic, finding tours 3 to 9% above the best known solutions (2 minutes for 100 nodes). Better results were found by …
-
Characterizations and Probabilistic Representations of Effective Resistance Metrics
… complete algebraic characterization in terms of triangle inequality defects. A more geometric condition is given by showing that a metric space can only be an effective resistance if its minimal graph realization contains no incomplete cycles. We also show that our algebraic characterization can …
-
Approximation algorithms for variants of the traveling salesman problem
… added constraint that edges of the graph observe triangle inequality, it has been shown that it is possible achieve a good approximation to the optimal solution [2]. TSP has a number of variants that have been deeply researched over the years. Approximations of varying degrees have been achieved …
-
Random obtuse triangles and convex quadrilaterals
… deals with finding the probability that a random triangle is obtuse in nature. We initially discuss the various ways of choosing a random triangle. The problem is at first analyzed based on random angles (adding to 180 degrees) and random sides (obeying the triangle inequality) which is a direct …
-
Changing edges in graphical model algorithms
… semi-metric edge in a graph, which violates the triangle inequality, indicates that there is another latent relation between the pair of nodes connected by the edge. We show the equivalence between modelling a sporting event using a stochastic Markov chain and an algebraic diffusion process, and …
-
Multiscale Modelling of Cancer Response to Viral Therapy
… embeddings for Holder continuous functions, the triangle inequality, the continuity of the norm, and the property of the Lebesgue Integral and Bochner Integral.
-
Computational and Statistical Detection of High-Dimensional Latent Space Structure in Random Networks
… spherical random geometric graph is the signed triangle count. We contribute to the existing literature by confirming that the signed triangle count is computationally optimal among low-degree polynomial tests. Our main technical ingredient is a strategy for bounding Fourier coefficients of …