Re: Worst Case Greedy Walk

From	quasi <quasi@null.set>
Newsgroups	comp.programming, comp.theory, sci.math, comp.graphics.algorithms
Subject	Re: Worst Case Greedy Walk
Date	2011-11-02 01:55 -0500
Organization	none
Message-ID	<ook1b7hef13oadgd9g3ajp0ha5nsidv0t1@4ax.com> (permalink)
References	<10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com>

Cross-posted to 4 groups.

Show all headers | View raw

In this subthread, I'll pose a few other "greedy-walk" type
problems relating to the Traveling Salesman Problem (TSP).
While I know very little about TSP, I suspect that problems
along the lines of the ones I pose below are likely to have 
been studied, and if so, a reference would be of interest. 

I'll pose 3 problems ...

Given a set S of n points in the plane, n > 2, with all 
distinct pairwise distances (each point has a unique nearest 
neighbor).

By a "full cycle on S" we mean a closed path which starts
at a vertex of S, visits all other points of S exactly once,
and then returns to the starting point. 

Two full cycles on S will be considered the same if and only 
if they have the same starting point and visit the same points 
in the same order. By this version of "sameness", there are 
exactly n! full cycles on S.

By the length of a full cycle on S we mean the sum of the
n distances from each point to the next point in the cycle.

Problem (1):  Of all the full cycles on S, how many distinct 
total distances are possible? 

Since for each full cycle, there are 2n full cycles (including
the original one) with the same total distance (obtained by 
simply changing the starting point or the direction of travel),
the full cycles on S yield at most ((n-1)!)/2 distinct total
distances. Perhaps this crude upper bound can always actually
be achieved?

Next ...

By a "greedy full cycle on S" we mean a full cycle on S such 
that each of the n-1 points visited before the final return 
is chosen "greedily", that is, from a given point in the
cycle, the next point to be visited is the closest yet 
unvisited point of S other than the starting point, unless
there are no such points, in which case, the final visit
is a return to the starting point.

Thus, there are exactly n greedy full cycles on S.

Problem (2):  Of the greedy full cycles on S, can there be 
n distinct total lengths? If not, at most how many distinct 
total lengths are possible?

Finally ...

Let

m(S) = the least total length of a full cycle on S.

a(S) = the least total length of a greedy full cycle on S.

b(S) = the greatest total length of a greedy full cycle on S.

Obviously, m(S) <= a(S) <= b(S).

Problem (3):  Over all sets S, what are the maximum possible 
values, as a function of n, of the ratios

   b(S)/a(S)

   b(S)/m(S)

   a(S)/m(S)

??

quasi

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-10-31 08:11 -0700
  Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-10-31 21:24 -0700
    Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:41 -0700
      Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-11-01 20:32 -0700
  Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-01 07:21 +0000
    Re: Worst Case Greedy Walk James Dow Allen <jdallen2000@yahoo.com> - 2011-11-01 00:45 -0700
      Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 13:02 -0700
        Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-02 09:57 +1300
          Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-03 10:55 +1300
            Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-03 09:39 +1000
              Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-07 17:09 +1300
                Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-08 04:04 +1000
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 09:54 +1300
                Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2011-11-13 11:50 -0800
                Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-14 06:58 +1000
                Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2012-03-29 00:28 -0700
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 11:44 +1300
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 14:28 +1300
    Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:46 -0700
      Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-02 08:16 +0000
        Re: Worst Case Greedy Walk Patricia Shanahan <pats@acm.org> - 2011-11-02 05:27 -0700
  Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 14:29 -0700
    Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 15:30 -0700
    Re: Worst Case Greedy Walk Steve Thompson <thomps2048@yahoo.ca> - 2011-11-01 20:56 -0400
  Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 01:55 -0500
    Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 18:24 -0500
  Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-02 17:49 +1000

csiph-web