I googled around and couldn't find a good source for the K-Median Theorem.
So, could you provide a good link?
On Tue, Nov 8, 2011 at 2:55 PM, sagar sindwani <sindwani.sa...@gmail.com>wrote:
> Use K-Median theorem with k=N
>
>
> On Mon, Nov 7, 2011 at 11:33 PM, Gene <gene.ress...@gmail.com> wrote:
>
>> Can you explain how a heap helps get the answer? Just to put the
>> elements in a heap requires O ( N^2 log (N) ) time.
>>
>> On Nov 7, 4:12 pm, vikas <vikas.rastogi2...@gmail.com> wrote:
>> > I think the best we can have is nlogn solution with the heap approach.
>> >
>> > On Nov 6, 10:27 pm, Dave <dave_and_da...@juno.com> wrote:
>> >
>> >
>> >
>> > > @Mohit: Here is a counterexample:
>> >
>> > > 10 11 52 53 54
>> > > 20 21 112 113 114
>> > > 30 31 122 123 124
>> > > 40 41 132 133 134
>> > > 50 91 142 143 144
>> >
>> > > The median is 91, and it is not on the anti-diagonal.
>> >
>> > > Dave
>> >
>> > > On Nov 6, 3:11 am, mohit verma <mohit89m...@gmail.com> wrote:
>> >
>> > > > @Gene
>> > > > As i said in my earlier post right to left diagonal partitions the
>> martix
>> > > > into 2 equal number of elements. So now the median must be in this
>> > > > diagonal. Now our focus is on finding median of this diagonal only.
>> > > > I think this works fine. Can u give some test case for which it
>> fails?
>> >
>> > > > On Sun, Nov 6, 2011 at 3:02 AM, Gene <gene.ress...@gmail.com>
>> wrote:
>> > > > > Unfortunately this isn't true. See the example I gave earlier:
>> >
>> > > > > 1 2 3
>> > > > > 2 4 5
>> > > > > 3 4 6
>> >
>> > > > > Thje median is 3.
>> >
>> > > > > 1 2 2 3 >3< 4 4 5 6
>> >
>> > > > > Niether one of the 3's lies on the diagonal.
>> >
>> > > > > When you pick any element P on the diagonal, all you know is that
>> > > > > anything to the right and downward is no less than P and
>> everything to
>> > > > > the left and upward is no greater. This leaves the upper right
>> and
>> > > > > lower left rectangles of the matrix unrelated to P.
>> >
>> > > > > On Nov 5, 3:51 am, ankit agarwal <ankit.agarwal.n...@gmail.com>
>> wrote:
>> > > > > > Hi,
>> >
>> > > > > > I think the median will always lie on the diagonal
>> > > > > > a[n][1] ---- a[1][n]
>> > > > > > because the elements on the LHS making the upper triangle will
>> > > > > > always be less than or equal to the elements on the diagonal
>> > > > > > and the RHS, elements in the lower triangle will be greater
>> than or
>> > > > > > equal to them.
>> >
>> > > > > > so sort the diagonal and find the middle element, that will be
>> the
>> > > > > > median.
>> >
>> > > > > > Thanks
>> > > > > > Ankit Agarwal
>> >
>> > > > > > On Nov 5, 1:29 am, Gene <gene.ress...@gmail.com> wrote:
>> >
>> > > > > > > Here's an idea. Say we pick any element P in the 2D array A
>> and use
>> > > > > > > it to fill in an N element array X as follows.
>> >
>> > > > > > > j = N;
>> > > > > > > for i = 1 to N do
>> > > > > > > while A(i, j) > P do
>> > > > > > > j = j - 1;
>> > > > > > > end;
>> > > > > > > X(i) = j;
>> > > > > > > end;
>> >
>> > > > > > > This algorithm needs O(N) time.
>> >
>> > > > > > > The elements of X split each row with respect to P. That is,
>> for each
>> > > > > > > i = 1 to N,
>> >
>> > > > > > > A(i, j) <= P if 0 < j <= X(i), A(i,j) > P if X(i) < j <=
>> N.
>> >
>> > > > > > > Now the strategy is to create two length N arrays a =
>> [0,0,...0]; and
>> > > > > > > b = [N,N,...]. We'll maintain the invariant that a[i] <
>> Median <= b[i]
>> > > > > > > for some i. I.e, they "bracket" the median.
>> >
>> > > > > > > We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N -
>> > > > > > > b(i) ). These tell us how many elements there are left and
>> right of
>> > > > > > > the bracket.
>> >
>> > > > > > > Now reduce the bracket as in binary search: Guess a value P,
>> compute
>> > > > > > > X. If L(X) >= R(X), set b = X else set a = X.
>> >
>> > > > > > > Keep guessing new P values in a way that ensures we reduce
>> the number
>> > > > > > > of elements between a and b by some fixed fraction. If we
>> can do
>> > > > > > > that, we'll get to 1 element in O(N log N) time.
>> >
>> > > > > > > The remaining problem is picking good P's. Certainly the
>> first time is
>> > > > > > > easy. Just take A(N/2, N/2). This has approximately (at
>> least) N^2/4
>> > > > > > > elements larger than it and N^2/4 smaller due to the sorted
>> rows and
>> > > > > > > columns. This is what we need to get O(N log N) performance.
>> >
>> > > > > > > But after the first split, things get trickier. The area
>> between a and
>> > > > > > > b takes on the shape of a slash / /, so you can't just pick a
>> P that
>> > > > > > > moves a and b together by a fixed fraction of remaining
>> elements.
>> >
>> > > > > > > Not to worry! You can quickly look up the (at most) N row
>> medians in
>> > > > > > > the bracket, i.e.
>> >
>> > > > > > > { A(i, (a[i] + b[i] + 1) / 2) | a[i]<b[i] , i = 1 to N }
>> >
>> > > > > > > and use the well known O(N) median selection algorithm to get
>> a median
>> > > > > > > of this. This has the quality we want of being somewhere
>> roughly in
>> > > > > > > the middle half of the remaining elements. The logic is the
>> same as
>> > > > > > > the selection algorithm itself, but in our case the rows are
>> pre-
>> > > > > > > sorted.
>> >
>> > > > > > > In all, each partitioning step requires O(N), and a fixed
>> fraction
>> > > > > > > (about 1/2) of the elements will be eliminated from the
>> bracket with
>> > > > > > > each step. Thus O(log n) steps will be needed to bring the
>> bracket to
>> > > > > > > size 1 for an overall cost of O(N log N).
>> >
>> > > > > > > I don't doubt that there's a simpler way, but this one seems
>> to work.
>> > > > > > > Anyone see problems?
>> >
>> > > > > > > On Nov 3, 3:41 pm, sravanreddy001 <sravanreddy...@gmail.com>
>> wrote:
>> >
>> > > > > > > > any better solution than O(N^2) in worst case?
>> > > > > > > > How do we take advantage of sorting and find in O(N lg N)-
>> Hide
>> > > > > quoted text -
>> >
>> > > > > > - Show quoted text -
>> >
>> > > > > --
>> > > > > You received this message because you are subscribed to the
>> Google Groups
>> > > > > "Algorithm Geeks" group.
>> > > > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > > > To unsubscribe from this group, send email to
>> > > > > algogeeks+unsubscr...@googlegroups.com.
>> > > > > For more options, visit this group at
>> > > > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > > > --
>> > > > Mohit- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Anup Ghatage
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
