Walking the Approximate Longest Path

  • + 0 comments

    The problem statement doesn't make sense:

    1. Permutations p1...pn were chosen uniformly at random among all permutations.
    2. For each i in {1, 2, ..., n-1}, edge (p[i], p[i+1]) was added to the graph.

    This makes no sense because p[i] is a PERMUTATION. It's a series of cities including all cities exactly once. You can't have an edge between two permutations.

    Perhaps the intended meaning was this:

    1. A random permutation "c" of n cities is chosen.
    2. For each i in {1, 2, ..., n-1}, edge (c[i], c[i+1]) was added to the graph.

    The term "approximate" is used because a solution will be accepted if it's close (at least 80% of n).