Re: [Tcllib-devel] ping gsoc graph work ...

[Andreas K. <and...@ac...>]

> Ok.
>  
> Next update will be on Sunday - both TSP algorithms, implementation + 
> tests.

Ok. Although I am a bit behind on my mail here. Looking at the time this mail 
missed me by a few minutes on Friday. And I am not reading office mail from the 
home system (*). Can I entice you to send your mails not only to me, but

	Tcllib Developers <tcl...@li...>

as well ? That will reach me at home too, as I subscribed both office and 
personal email adresses to the list.

> Considering approximation algorithms there are some inconvenient cases 
> about testing. For example, when I was trying to perform tests showing 
> case with Max Approximation factor, it strongly depends of what 
> algorithms ( which approximation algorithms use in their implementation 
> ), are going to return, e.g. in 2-approximation algorithm for TSP - when 
> we create input graph that is tight example, it will give the worst 
> solution, if the spanning tree found by for example Prim Algorithm will 
> have a proper look. Hence, for graphs I tested it found sligthly better 
> solutions.

Can you explain this in shorter sentences ? I tried to read and understand it 
several times and keep getting confused. Likely the problem is on my side, it 
is Monday morning, I did not sleep that well, my brain is buggered.

> Of course those Tight Example graphs, should and will be taken into 
> account in documentation.
>  
> About finding spanning tree - should there be option where user can 
> specify, if he wants use kruskal or prim to find minimum spanning tree? 

So the approximation algorithm is finding a spanning tree as part of its work ?

> It would make tests more resistant to changes, for example changing 
> spanning tree algorithm in implementation won't make all tests crush.

My understanding here is that by making the spanning tree algorithm STA used by 
the approx algorithm AA a configurable option of AA you can use both STAs we 
have in the tests of AA and thus make sure that the results are not influenced 
by the choice of STA ?


> 2-approximation algorithm is done. Christofides algorithm uses in it's 
> implementation Max Matching algorithm so I'm trying to simulate it for 
> now, as Max Matching implementation is placed in last week of the 
> timeline.

A bit of chiding here. A reason that the mentors ask the students for the 
timeline of their project is to have them think about and become aware of such 
dependencies.


 > I was thinking about implementing, only for now, greedy Max
> Matching but it doesn't return optimal solution, so it will decrease 
> good approximation of Christofides ( 3/2 ).

Another option would be to move Christofides back in the timeline after the 
Max-Matching and then move some other algorithm to the free spot.

I see from the most recent mail (I got today) that you have chosen to do 
Christofides, and faking the results you need from max-matching. Certainly also 
a way forward, with the understanding that Christofides needs re-checking when 
we have the actual max-matching implementation in Week 9+

Greedy max-matching ... Is my understanding correct that this would find a 
matching, but not necessarily the maximal one ? Or not the best maximal per the 
weights ?



~~~
(Ad *) I could now with our IMAP system, if I were to install Thunderbird at 
home. Except that at home I do wish to be away from work. Note here that the 
GSoC mentoring does not count as work, that is something I can do at home as 
well, and during the weekend.

Andreas.