Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

This is inspired by a recent questionrecent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

added 130 characters in body
Source Link

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

Source Link

Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.