<p>This problem is known as the <em>(Undirected) Orienteering problem</em> (I'm unaware of any work that examined distances that come from 2D Euclidean embedding).</p>

<p>It is NP-hard (and moreover, $APX$-hard) and <a href="http://web.engr.illinois.edu/~chekuri/papers/orienteering2.pdf" rel="nofollow">there exists a $2+\epsilon$ approximation</a> for it.</p>

CC BY-SA 3.0
2014-10-02T09:14:37.290Z
Thank you for naming the problem. I couldn't find it anywhere.
Jan Hadáček
CC BY-SA 3.0
2014-12-27T04:22:12.300Z
The journal version of the above mentioned $(2+\epsilon)$-approximation is available at the link below. It has additional results. http://web.engr.illinois.edu/~chekuri/papers/orienteering-journal.pdf
Chandra Chekuri
CC BY-SA 3.0
2014-10-02T07:17:27.747Z
2014-10-02T07:17:27.747Z
R B
<p>As RB mentioned, this is the Orienteering problem. For points on a plane, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979</a> gives a PTAS.</p>

CC BY-SA 3.0
2014-10-02T09:20:43.493Z
2014-10-02T09:20:43.493Z
vgta
<p>We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a <strong>subset of nodes</strong> which satisfies all of the following properties:</p>

<ol>
<li>The total length of the cycle is less than D</li>
<li>The number of nodes included in the cycle is maximal</li>
<li>If there are more solutions satisfying 1. and 2., choose the one having the smallest cycle length</li>
</ol>

<p>Note that weights of edges satisfy triangle inequality.</p>

<p>I know how to solve a standard shortest Hamiltonian cycle problem. However, I don't know how to choose a subset of points to start with. The naive solution would involve enumerating all subsets of points (NP) and attempting to construct a Hamiltonian cycle on every such subsets (NP again). </p>

<p>It seems totally intractable, even for a small number of nodes (I expect ~15 nodes). The only heuristic I can think of is constructing a minimum spanning tree for every subset, using the length of a MST as a lower-bound estimate and skipping subsets that obviously break constraint #1.</p>

<p>I hope a better solution exists, ideally without enumerating all subsets of nodes.</p>

<graph-algorithms><hamiltonian-paths>
Hamiltonian cycle on a subset of 2D points, constrained by maximum total length
Jan Hadáček
# Hamiltonian cycle on a subset of 2D points, constrained by maximum total length

(Asked by: username_0 on 2014-10-01)

We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a **subset of nodes** which satisfies all of the following properties:

1. The total length of the cycle is less than D
2. The number of nodes included in the cycle is maximal
3. If there are more solutions satisfying 1. and 2., choose the one having the smallest cycle length

Note that weights of edges satisfy triangle inequality.

I know how to solve a standard shortest Hamiltonian cycle problem. However, I don't know how to choose a subset of points to start with. The naive solution would involve enumerating all subsets of points (NP) and attempting to construct a Hamiltonian cycle on every such subsets (NP again).

It seems totally intractable, even for a small number of nodes (I expect ~15 nodes). The only heuristic I can think of is constructing a minimum spanning tree for every subset, using the length of a MST as a lower-bound estimate and skipping subsets that obviously break constraint #1.

I hope a better solution exists, ideally without enumerating all subsets of nodes.

**Tags:** graph-algorithms, hamiltonian-paths


---

## 2 answers

### Answer by username_1 on 2014-10-02. Score: 2 | Accepted answer

This problem is known as the *(Undirected) Orienteering problem* (I'm unaware of any work that examined distances that come from 2D Euclidean embedding).

It is NP-hard (and moreover, $APX$-hard) and [there exists a $2+\epsilon$ approximation](http://web.engr.illinois.edu/~chekuri/papers/orienteering2.pdf) for it.

> **Comments:**
> **username_0**: Thank you for naming the problem. I couldn't find it anywhere.  
> **username_2**: The journal version of the above mentioned $(2+\epsilon)$-approximation is available at the link below. It has additional results. http://web.engr.illinois.edu/~chekuri/papers/orienteering-journal.pdf  

---

### Answer by username_3 on 2014-10-02. Score: 3

As RB mentioned, this is the Orienteering problem. For points on a plane, <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979> gives a PTAS.


---

