0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I got an answer at CS. It's a variation of Undirected Orienteering Problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.