New answers tagged

0 votes

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

If you need a mathematical guarantee, you should run $k-1$ times the $N$-solver algorithm. In other words, repeat the following approach for each vertex $v_i\ \ i=2,...,k$ and take the best solution. ...
user avatar
0 votes

Better results for minimum vertex cover algorithms

I proposed a better approximation algorithm for vertex cover problem (a 1.999999-approximation algorithm by solving a well-known SDP model and a randomized procedure). It is not published, yet. But, I ...
user avatar
1 vote
Accepted

approximation ratio of TSP problem where the weights are bounded by an inequality

Summary: Start with a minimum spanning Tree (MST). Then modify it slightly to a Hamiltonian circuit. Mini-step traversal of $(T,s)$ Let $T$ be a tree. Definitions: For two vertices $u$ and $v$, let $d(...
user avatar
  • 34.1k

Top 50 recent answers are included