From jsbm@ams.sunysb.edu Sun Sep 28 14:25:35 2003 Date: Sun, 28 Sep 2003 14:34:13 -0400 To: Karl Juhnke Cc: jsbm@ams.sunysb.edu, Alper Yildirim , algorithms-list@cs.sunysb.edu Subject: Re: proof of the general conjecture from today Mime-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.3.28i From: Joseph Mitchell X-Status: X-Keywords: An apology and a retraction: the proof is not yet done (and when it is, it will only apply to geometric instances). Thanks for the flood of emails from several "concerned citizens" who realized quickly that the "proof" I sent around (written in 5 minutes) was bogus. It reduces the problem to another one: Show that the union U has length at least (n-1) times OPT (e.g., by showing that one can extract (n-1) tours from its union). Yes, we must use geometry somewhere; M. Dror has a counterexample for non-geometric instances. So, putting an erroneous "proof" out for discussion had a very positive effect!! Keep up the thoughts and keep us all posted on progress. Joe From jsbm@ams.sunysb.edu Wed Oct 1 13:38:59 2003 Date: Wed, 1 Oct 2003 13:47:24 -0400 (EDT) From: jsbm@ams.sunysb.edu Subject: Re: proof of the general conjecture from today To: yangfuli@yahoo.com, matya , valentin , alper , Esther Arkin , george@georgehart.com, ghart@optonline.net, saurabh@eecs.oregonstate.edu, saurabh@cs.orst.edu cc: jsbm MIME-Version: 1.0 X-Status: X-Keywords: So, Estie, Matya and I checked, and the Petersen graph example (all edges have length 1, and then make it a complete graph by adding edges of length 2 -- this exactly satisfies triangle inequality) seems to be a counterexample for the non-geometric case, as suspected: marginal costs of 2 per node (total of 20), versus OPT=11. Note that we have a simple proof (due to a few people, e.g., Saurabh) that sum of marginals is at most 2*OPT. Thus, Petersen graph is pretty close to tight (factor 2)... we think maybe generalized Petersen graphs give a factor approaching 2 in the limit. (So Saurabh's conjecture about improving 2*OPT is not holding in general graphs) Let's try to understand/prove the geometric case! Joe From kotya3d@yahoo.com Wed Oct 1 13:33:34 2003 Date: Wed, 1 Oct 2003 10:38:02 -0700 (PDT) From: Valentin Polishchuk Subject: Re: try this possible counterexample... To: jsbm@ams.sunysb.edu MIME-Version: 1.0 X-Status: A X-Keywords: Since it's hypohamiltonian (deletion of any vetrex makes it Hamiltonian), TSP(P\i) = 9 TSP(P) = 11, so Sum (TSP\i) = 90 < 11*9 = 99! But, Sum (TSP\i) > 88 = 11*8! Valentin --- jsbm@ams.sunysb.edu wrote: > > Moshe Dror suggests that the Petersen graph (edges > of lengths 1), > plus edges of length 2 to make it complete, gives a > counterexample > for the non-geometric case. > > Can you check it? (I am doing so too....) > What are the marginals? > > Joe > > > __________________________________ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com ? From estie@ams.sunysb.edu Wed Oct 1 14:53:01 2003 To: jsbm@estiepc.ams.sunysb.edu Subject: example where sum of marginals/2opt goes to 1 Cc: george@georgehart.com, ghart@optonline.net, kotya@ams.sunysb.edu, matya@cs.bgu.ac.il, saurabh@cs.orst.edu, saurabh@eecs.oregonstate.edu, yangfuli@yahoo.com, yildirim@ams.sunysb.edu From: Esther Arkin Date: Wed, 01 Oct 2003 14:57:28 -0400 X-Status: X-Keywords: I think I have an example of a graph, satisfying triangle inequality, so that the sum of the marginals is "almost" 2 opt, meaning that the ratio between sum marginals over 2 opt goes to 1 as n, the number of nodes increases to infinity: Build a circuit of n nodes (1,2,...,n), and another circuit (1',2',...,n') also on n nodes with edges (i,i') of length 1, and the edges of the two circuits also have length 1. All other edges have length 2. n must be odd for my example. Now opt =2n+1, as the graph of the 2 circuits plus connector edges (i,i') is not hamiltonian, you must used at least one edge of length 2. Removing any 1 node (it is symmetric) you get a Hamiltonian graph, so opt on all but one node is 2n-1, and so each marginal is 2. Sum of all marginals is 4n (as there are 2n nodes). 4n/ 2(2n+1) goes to 1 as n goes to infinity. This makes Saurabh's (or whoever it was) 2 proof tight. Estie From estie@ams.sunysb.edu Wed Oct 1 14:58:43 2003 To: jsbm@estiepc.ams.sunysb.edu Subject: never mind, wrong example Cc: george@georgehart.com, ghart@optonline.net, kotya@ams.sunysb.edu, matya@cs.bgu.ac.il, saurabh@cs.orst.edu, saurabh@eecs.oregonstate.edu, yangfuli@yahoo.com, yildirim@ams.sunysb.edu From: Esther Arkin Date: Wed, 01 Oct 2003 15:03:09 -0400 X-Status: X-Keywords: Never mind, I made a mistake. The original 2 cycle graph DOES have a hamilton circuit, so opt is 2n. From kotya3d@yahoo.com Wed Oct 1 15:26:49 2003 Date: Wed, 1 Oct 2003 12:31:14 -0700 (PDT) From: Valentin Polishchuk Subject: general example To: jsbm@ams.sunysb.edu, yangfuli@yahoo.com, matya , alper , Esther Arkin , george@georgehart.com, ghart@optonline.net, saurabh@eecs.oregonstate.edu, saurabh@cs.orst.edu Cc: kotya@ams.sunysb.edu MIME-Version: 1.0 X-Status: X-Keywords: Actually, any hypohamiltonian graph G serves as an example. If it has n nodes, than OPT is n+1 (take a HC in G\1, as soon as the HC passes through a node, adjasent to 1 - go to 1 and go back to the HC). The f(i) 's are all 2 then. It's known that for all but finitely n there exist hypohamiltonian graphs on n nodes, e.g., P(n,2) are for n = 5 (mod 6). P(n,2) are very much alike the graphs from Estie's example - just the nodes in the inner circle are connected in the "every other" way, to form a "star". Valentin --- Valentin Polishchuk wrote: > Yes, in the generalized petersen graph P(n,2) the > ratio tends to 2 if n = 6K+5 for a natural K. > > Valentin > > > --- jsbm@ams.sunysb.edu wrote: > > > > So, Estie, Matya and I checked, and the Petersen > > graph example > > (all edges have length 1, and then make it a > > complete graph > > by adding edges of length 2 -- this exactly > > satisfies > > triangle inequality) > > seems to be a counterexample for the non-geometric > > case, > > as suspected: > > marginal costs of 2 per node (total of 20), > > versus OPT=11. > > > > Note that we have a simple proof (due to a few > > people, > > e.g., Saurabh) that sum of marginals is at most > > 2*OPT. > > Thus, Petersen graph is pretty close to tight > > (factor 2)... > > we think maybe generalized Petersen graphs give > > a factor approaching 2 in the limit. > > (So Saurabh's conjecture about improving 2*OPT is > > not holding in > > general graphs) > > > > Let's try to understand/prove the geometric case! > > > > Joe > > > > > > > > > __________________________________ > Do you Yahoo!? > The New Yahoo! Shopping - with improved product > search > http://shopping.yahoo.com __________________________________ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com From dimitris@cs.sunysb.edu Fri Nov 7 13:13:51 2003 Date: Fri, 7 Nov 2003 13:12:53 -0500 (EST) From: Dimitris Papamichail X-X-Sender: dimitris@compserv3 To: Joseph Mitchell Subject: Re: reading group Friday: guest Moshe Dror MIME-Version: 1.0 X-Status: A X-Keywords: Hello Prof. Mitchell, looking through my emails I could not locate the petersen graph counterexample for the TSP conjecture (the one that makes the factor 2 bound tight). Is it possible that you forward to me that page that demonstrates that? If the proof is also available, I would be interested to see it (the one about the triangle-inequality but not euclidean distance case). Thanks a lot. Dimitris PS: Am I assuming correctly that all graphs we are dealing with are complete (including the petersen graph, but the edges not presented have weights that obey the triangle inequality)? PS2: I think that the conjecture not only holds for convex polygons, but for the superclass of polygons that, for any node i, the TSP-i is sharing n-2 edges with the TSP and its last edge connects the neighbors of i in the TSP. And I think proving that does not need any euclidean space arguments, but only the triangle inequality. From jsbm@ams.sunysb.edu Mon Nov 10 11:39:23 2003 Date: Mon, 10 Nov 2003 11:46:45 -0500 (EST) From: jsbm@ams.sunysb.edu Subject: Re: 3D L1 TSP conj. counterex. To: Valentin Polishchuk cc: estie@ams.sunsyb.edu, yangfuli@yahoo.com, jsbm MIME-Version: 1.0 X-Status: X-Keywords: On 10 Nov, Valentin Polishchuk wrote: > Hello, > > I think that the following 6 points provide a counterexample to the > TSP conjecture in 3D: > > -1 0 0 ; 1 0 0 ; 0 1 0 ; -1 0 1; 1 0 1 ; 0 1 1 . > > In L1 metric, OPT is 10, e.g., 1 2 3 6 5 4 1, see 3DL1TSP.jpg > > OPT on S\6 is 8, e.g., 1 3 2 5 4 1, see without_point.jpg, so f(6) = 2 > and the marginals' sum is 12 > 10 = OPT. > > > This counterexample is based on a 6-node counterexample for general > graphs which Karl and I found some time ago. > > Valentin Very nice! I checked some of the arithmetic just now. Have you looked at the same example for L_2 metric? I did a non-exhaustive quick check, and it seems that in L_2 the conjecture still holds for these 6 points, right? Joe