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

[Lars H. <Lar...@re...>]

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.

> And it also describes it as finding maximal, not maximum, the latter 
> being NP-hard.
> 
>>
>> But now that I think about it... is this really what you want? The 
>> next steps being
>>
>>> - let the j be the min index, such that |Mj| <= k.
>>>
>>> - return Mj.
>>
>> it would seem more natural to seek a set which is somehow minimum here 
>> (as that would make it easier to meet this condition) than to pick the 
>> maximum. Indeed, given that
> 
> The pdf explains a bit more, maybe that helps.

Yes, it does. The algorithm approximates the minimal cost from _below_ 
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.

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

Lars Hellström