Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #984

Re: Worst Case Greedy Walk

Cross-posted to 4 groups.

Show all headers | View raw

On Wed, 02 Nov 2011 01:55:06 -0500, quasi <quasi@null.set> wrote:

>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).

What if we change R^2 to R^k, for some fixed positive integer
k < n?

Alternatively, we can allow S to be an arbitrary n-point
metric space, not necessarily embeddable in R^(n-1).

Also, we might consider removing the requirement that the 
distances are distinct. Of course, then we will get more 
than n distinct greedy full cycles.

>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)
>
>??

Let's consider two special case of Problem (3) above ...

First, suppose k = 1. In other words, the n points are
on the real line. Also, relax the restriction on distinct
distances. With these conditions, I think the following
claim holds:   

   b(S)/m(S) < 4/3 for all n.

   The maximum possible value of 
   b(S)/m(S) -> 4/3 as n -> oo.

Next, fix n = 4, but again relax the restriction on distinct 
distances. For k = 1,2,3 what are the maximum possible values 
for b(S)/m(S)? What if S is an arbitrary 4-point metric space, 
not necessarily embeddable in R^3?

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