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

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

Lars Hellström wrote:
> Andreas Kupries skrev:
>> Lars Hellström wrote:
>>> Michał Antoniewski skrev:
>>>> - for each Gi^2 we seek for maximum independent set Mi. Just to clear:
>>>> finding maximal is of course NP hard, we seek for maximum set.
>>> You've got maximum and maximal the wrong way round here. Finding one 
>>> maximal (w.r.t set inclusion) independent set is easy (add vertices 
>>> until you've covered the graph). Finding one that achieves the maximum 
>>> cardinality is hard.
>> Yes. I just googled for
>>     weighted metric k-center
>> and found the PDF
>>
>> http://www.corelab.ntua.gr/courses/approx-alg/material/k-center.pdf
>>
>> which seems to be the basis of Michal description, it is very similar.
> 
> Very similar indeed! Should probably be provided as reference.

Assuming that the link stays up.

>> The pdf explains a bit more, maybe that helps.
> 
> Yes, it does. The algorithm approximates the minimal cost from _below_ 

Right.

> rather than above, as far as the selection of edges is concerned; I 
> hadn't expected that. Also, I hadn't fully noticed the "G must be a 
> complete graph" condition... This, of course, means any nonempty set of 
> vertices is dominating (= a vertex cover), so one can't get it wrong, 
> only suboptimal.

Interesting. Didn't know that.

> 
> Concerning that "complete graph" condition, though... Stylistically, 
> it's a bit backwards to have a command that takes a graph as input, if 
> only complete graphs are valid input.

 > (Stretching a bit, it's kind of
> like having a command accepting a list of numbers as input, with the 
> constraint that the numbers must all be equal to 1.) Even if the 
> implementation very naturally exercises [struct::graph]s, one might 
> want to take the time to think about whether a [struct::graph] is the 
> most natural form for the input. If the implementation needs to 
> preprocess the graph so that it is metrically complete, then maybe the 
> output from the command that computes all shortest distances would be 
> more practical, but if it can do the completion implicitly (which seems 
> plausible for this algorithm; add uw at cost c(uv)+c(vw) to the queue 
> once uv and vw have been processed) then a [struct::graph] as input 
> becomes much more appropriate.

That sounds like a good way of completing a graph. Better than just adding Inf 
edges which kills the metric, often.

 > In the latter case, the command
> documentation should take the "distance in general graph" point of 
> view, rather than speaking about costs of individual edges.

Andreas