A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
The convex hull cheapest insertion heuristic produces good solutions to the Euclidean Traveling Salesperson Problem, but it has never been extended to the non-Euclidean problem. This paper uses multidimensional scaling to first project the points from a non-Euclidean space into a Euclidean space, enabling the generation of a convex hull that initializes the algorithm. To evaluate the proposed algorithm, non-Euclidean spaces are created by adding separators to the TSPLIB data-set, or by using the L1 norm as a metric.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Federated Classification in Hyperbolic Spaces via Secure Aggregation of Convex Hulls
Hierarchical and tree-like data sets arise in many applications, including language processing, graph data mining, phylogeny and genomics. It is known that tree-like data cannot be embedded into Euclidean spaces of finit…
Federated Learninggraph partitioningPrivacy PreservingQuantizationConvex Hull Monte-Carlo Tree Search
This work investigates Monte-Carlo planning for agents in stochastic environments, with multiple objectives. We propose the Convex Hull Monte-Carlo Tree-Search (CHMCTS) framework, which builds upon Trial Based Heuristic …
Multi-Armed BanditsDual feature-based and example-based explanation methods
A new approach to the local and global explanation is proposed. It is based on selecting a convex hull constructed for the finite number of points around an explained instance. The convex hull allows us to consider a dua…
Feature ImportanceBetween steps: Intermediate relaxations between big-M and convex hull formulations
This work develops a class of relaxations in between the big-M and convex hull formulations of disjunctions, drawing advantages from both. The proposed "P-split" formulations split convex additively separable constraints…
ClusteringFormDesign of a novel convex hull based feature set for recognition of isolated handwritten Roman numerals
In this paper, convex hull based features are used for recognition of isolated Roman numerals using a Multi Layer Perceptron (MLP) based classifier. Experiments of convex hull based features for handwritten character rec…