Re: Disjoint circle merge NP complete for L^n error?

Thanks very much Torben for looking at this.

You describe the natural heuristic in P for which we already have good
data structures and algorithms worked out. This heuristic can produce
arbitrarily bad results because any "merge iteration" can both break
overlaps that already existed and create new ones (this can be seen in
the proof). In the worst case, it puts ALL the data points in a single
circle when only ONE PAIR needs to be merged.

The key point is that we need to be sure there is no optimal algorithm
in P before we implement a heuristic that could do dumb things. Hence
the need for the NP-hardness proof. This IS the scenario in the Intro
of Garey and Johnson!

So we have the proof for a specific case L^\infty and need to extend it
to L^n.

I differ with you on the need for more information. The problem is
completely described in the proof at the link. The error function
merely defines a "good" partition of data points. Smaller error is
good. We only need to erase MAX and replace with SUM in the proof
problem statement and either fix it or give an optimal (guaranteed
minimum error partition) algorithm in P.

For those unfamiliar with L^n metrics, MAX and SUM are merely two
cases. In this problem the L^n form of error would be

error(S) = \root{n}{ \sum_{i} |p_i - p|^n }

One can easily check that with n=1 this is SUM and with n->\infty it is
MAX. I'm pretty sure that if both these are in NP then all L^n metrics
are also. That's why we're focused on SUM. On the other hand if SUM
is in P, that's pretty fascinating and surprising in its own right, and
we will have to start checking n=2,3,...

Thanks again!

.

Relevant Pages

  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: C# generic containers from a "C++ perspective"
    ... If you implement the floating-point and integer algorithms ... Maintain the sum of all the items in an accumulator. ... That is the fundamentally-broken algorithm that I was expecting you to ...
    (microsoft.public.dotnet.languages.csharp)
  • SumIf across columns instead of rows
    ... to I have a set of metrics that are laid out horizontally in a spreadsheet, ... similar formula so I don't have type each cell into a Sum function? ...
    (microsoft.public.excel.worksheet.functions)