A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP

• URL: http://arxiv.org/abs/2302.06582v5
• Date: Wed, 3 Jul 2024 02:54:12 GMT
• Title: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming [46.390064640459]
  The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications.<n>We propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches.
  arXiv  Detail & Related papers  (2026-08-11T12:58:02Z)
• Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
  We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
  arXiv  Detail & Related papers  (2026-07-03T08:48:35Z)
• Koopman Subspace Pruning in Reproducing Kernel Hilbert Spaces via Principal Vectors [5.373672902884401]
  This paper presents an approach for computing principal angles and vectors to enable Koopman subspace pruning within a Reproducing Kernel Hilbert Space (RKHS) geometry.<n>We first outline an exact computational routine, which is subsequently scaled for large datasets using randomized Nystrom approximations.<n>Based on these foundations, we introduce the Kernel-SPV and Approximate Kernel-SPV algorithms for targeted subspace refinement via principal vectors.
  arXiv  Detail & Related papers  (2026-04-01T23:13:13Z)
• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization [55.002497070656624]
  Broximal Point Method (BPM) offers an idealized optimization framework based on iteratively minimizing the objective function over norm balls centered at the current iterate.<n>It enjoys striking global convergence guarantees, converging linearly and in a finite number of steps for proper, closed and convex functions.<n>In this note, we ask whether the convergence theory of BPM can be extended to this more general, non-Euclidean setting.
  arXiv  Detail & Related papers  (2025-10-01T12:32:52Z)
• Riemannian Optimization for Distance Geometry: A Study of Convergence, Robustness, and Incoherence [6.422262171968397]
  The Euclidean Distance Geometry (EDG) problem arises in a broad range of applications, including sensor network localization, molecular conformation, and manifold learning.<n>In this paper, we propose a framework for solving the EDG problem by formulating it as a low-rank matrix completion task over the space of positive semi-definite Gram matrices.<n>The available distance measurements are encoded as expansion coefficients in a non-orthogonal basis, and optimization over the Gram matrix implicitly enforces geometric consistency through the triangle inequality.
  arXiv  Detail & Related papers  (2025-07-31T18:40:42Z)
• Enforcing Latent Euclidean Geometry in Single-Cell VAEs for Manifold Interpolation [79.27003481818413]
  We introduce FlatVI, a training framework that regularises the latent manifold of discrete-likelihood variational autoencoders towards Euclidean geometry.<n>By encouraging straight lines in the latent space to approximate geodesics on the decoded single-cell manifold, FlatVI enhances compatibility with downstream approaches.
  arXiv  Detail & Related papers  (2025-07-15T23:08:14Z)
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  The problem of finding suitable point embedding Euclidean distance information point pairs arises both as a core task and as a sub-machine learning learning problem. In this paper, we aim to solve this problem given a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-22T13:02:12Z)
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  Two algorithms are proposed to solve the Euclidean Distance Geometry problem. First algorithm converges linearly to the true solution. Second algorithm demonstrates strong numerical performance on both synthetic and real data.
  arXiv  Detail & Related papers  (2024-10-08T21:19:22Z)
• Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler [23.166642097170545]
  We develop a non-Euclidean analog of the recent proximal sampler of [LST21], which naturally induces regularization by an object known as the log-Laplace transform (LLT) of a density. We show our warm-started sampler improves the value oracle complexity of differentially private convex optimization in $ell_p$ and Schatten-$p$ norms for $p in [1, 2]$ to match the Euclidean setting [GLL22], while retaining state-of-the-art excess risk bounds.
  arXiv  Detail & Related papers  (2023-02-13T04:08:41Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension [12.354076490479514]
  We show that Dual Principal Component Pursuit (DPCP) can provably solve problems in the it unknown subspace dimension regime. We propose a very simple algorithm based on running multiple instances of a projected sub-gradient descent method (PSGM) In particular, we show that 1) all of the problem instances will converge to a vector in the nullspace of the subspace and 2) the ensemble of problem instance solutions will be sufficiently diverse to fully span the nullspace of the subspace.
  arXiv  Detail & Related papers  (2022-01-22T15:36:03Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  We introduce an explicit factorization of low rank couplings as a product of textitsub-coupling factors linked by a common marginal. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.
  arXiv  Detail & Related papers  (2021-03-08T13:18:45Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.