Very good! Teamwork. Just keep doing what you're doing and we can solve this I 
think.
Sent from my Verizon Wireless BlackBerry

-----Original Message-----
From: Martin Michael Musatov <marty.musa...@gmail.com>

Date: Tue, 28 Apr 2009 06:31:36 
To: Algorithm Geeks<algogeeks@googlegroups.com>
Subject: [algogeeks] Re: which NP-complete problem can reduce to this problem?



PROCESSORS P(NP, NP)

RANGE X(N), Y(N)
DISTRIBUTE X ONTO P(BLOCK, *)
DISTRIBUTE Y ONTO P(*, BLOCK)
SHADOW (1) X, Y

REAL A X, Y

ON (P)
! Initialize the array...

OVERALL(I = X, J = Y)
A [I, J] = ...
ENDOVERALL

DO ITER = 1, NITER
DO ICOLOUR = 0, 1
CALL DA_WRITE_HALO(A, (/CYCL, CYCL/), (/1, 1/))

OVERALL(I = X)
OVERALL(J = Y(MOD(ICOLOUR + I, 2) : : 2))
A [I, J] = (A [I, J - 1] + A [I, J +1] + &
& A [I - 1, J] + A [I + 1,J]) / 4
ENDOVERALL
ENDOVERALL
ENDDO
ENDDO
ENDON

On Mar 14, 7:06 am, Jim <arkma...@gmail.com> wrote:
> Replication is common in distributed data store system to achieve
> availability.
> Say, there are k*n data server, the problem is to split these servers
> into n groups, where replication is applied, and maximize the average
> availability. Each group shares the same replication number - k.
> Different servers have different fail rates.
>
> amit wrote:
> > Where did you find this problem? Does it have a practical application
> > you know of?
> > It is interesting. Do you have any thoughts about its solution?
>
> > On Mar 10, 11:50 pm, Jim <arkma...@gmail.com> wrote:
> > > sorry, I fail to understand "the permanent" :-(
>
> > > If numbers are powers of 2, and the input are these exponent.
> > > but I think they are different problems.
> > > say, the original numbers are 2, 4, 8, 16, 32, 64, 128, 256,
> > > the minimal partition is [8, 16, 32, 64] [2, 4, 128, 256]
> > > sum is 524288.
>
> > > while the corresponding exponent inputs are
> > > 1, 2, 3, 4, 5, 6, 7, 8
> > > and there are so many partition problems, which maximum partition
> > > produce the result, [1,2,7,8] [3,4,5,6]?
>
> > > thanks
>
> > > Miroslav Balaz wrote:
> > > > so the permanent is like determinant but without sign in summand.
>
> > > > I have found something interesting in your peoblem.
>
> > > > It is NP-complete if you have n=2, and numbers are powers of two, but on
> > > > input is only exponent.
> > > > som if there is number 2^100, only 100 is on input. One can directly 
> > > > reduce
> > > > MAX-PARTITION to this problem. This alone has no value, because it is
> > > > different problem, because the input if of log n size, as if it was in 
> > > > your
> > > > problem.
>
> > > > 2009/3/9, Jim <arkma...@gmail.com>:
>
> > > > > After asking for helps from many persons who are skilled at algorithm
> > > > > design, I suspect this problem is a NP-complete.
> > > > > The only problem you speak of which contains multiplication is
> > > > > computing a "permanent", what is this problem?
> > > > > could you post any details or links about it?
>
> > > > > You are probably right that this problem is neither NP-complete nor P.
> > > > > Great hint.
>
> > > > > Thank you very much.
>
> > > > > On Mar 9, 12:07 am, Miroslav Balaz <gpsla...@googlemail.com> wrote:
> > > > > > Do you have polynomial algorithm for that problem?
> > > > > > We don't need one another NP-copmlete problem. There is enough of 
> > > > > > them.
>
> > > > > > And there are more interresting problems for which we don't know
> > > > > reduction.
> > > > > > The rule of thumb is, that if you pick random problem from NP that 
> > > > > > it is
> > > > > not
> > > > > > from P.
> > > > > > Assuming P \neq NP, there may be problems in NP that are not 
> > > > > > NP-complete
> > > > > and
> > > > > > are not in P.
>
> > > > > > This problem contains ARITHMETIC MULTIPLICATION.
> > > > > > The only problem i know which contains multiplication is computing a
> > > > > > "permanent", but that is PSPACE complete, i think, but i am not 
> > > > > > sure.
> > > > > > You should try to find proof of  NP completeness of knapsack
> > > > > > problem(google).
>
> > > > > >  If you want to make any success, you should first try case when all
> > > > > numbers
> > > > > > are power of two.
>
> > > > > > 2009/3/8 Jim <arkma...@gmail.com>
>
> > > > > > > it's incorrect. for example:
> > > > > > > 23, 24, 26, 30, 32, 63, 64, 90, n = 2, k = 4
> > > > > > > the minimum split is [26, 30, 32, 90] [23, 24, 63, 64]
> > > > > > > the sum is 4472064
>
> > > > > > > On Mar 8, 10:08 pm, Miroslav Balaz <gpsla...@googlemail.com> 
> > > > > > > wrote:
> > > > > > > > Can't you just sort the numbers, and than multiply first k 
> > > > > > > > numbers,
> > > > > than
> > > > > > > > second etc. ?
>
> > > > > > > > 2009/3/8 Jim <arkma...@gmail.com>
>
> > > > > > > > > Given a set of k*n positive numbers, we can split this set 
> > > > > > > > > into n
> > > > > > > > > partitions, each partition with k numbers. Now, we multiply 
> > > > > > > > > the
> > > > > > > > > numbers in each partition, got n products, then we have a sum 
> > > > > > > > > of n
> > > > > > > > > products. How can we split this set to minimize this total 
> > > > > > > > > sum?
>
> > > > > > > > > It's easy to show this problem is NP. Since we can recast this
> > > > > > > > > optimization problem as a decision problem, how can we split 
> > > > > > > > > this
> > > > > set
> > > > > > > > > and let this sum is not greater than a given number t, which 
> > > > > > > > > is no
> > > > > > > > > harder than original optimization one. Given an instance of 
> > > > > > > > > this
> > > > > > > > > decisive problem, we can easily compute this sum within O(n) 
> > > > > > > > > time.
>
> > > > > > > > > The key part is which known NP-complete problem reduces to 
> > > > > > > > > this
> > > > > > > > > problem. Unfortunately, I have no idea about this polynomial
> > > > > > > > > reduction. (find a minimum weighted maximal matching with a
> > > > > > > > > hypergraph?)
>
> > > > > > > > > Any hints will be appreciated, thanks.



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

Reply via email to