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
Date: Tue, 28 Apr 2009 06:31:36
To: Algorithm Geeks
Subject: [algogeeks] Re: which NP-complete proble
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/))
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 ser
Having read the "permanent" on wikipedia site, I think there is
little correlation with this problem.
Thanks for your clarification, and i realize the special case of my
problem can reduce to this partition problem:
Given a set of 2*k positive numbers(where n is 2), how to split this
set into tw
so there is no problem, it works if you take logarithm you have the
partition 18:18, which is optimal as the sum us 36
the permanent:
the determinant is calculated by taking all permutations , and for each
permutation you multiply some elements of matrix, given by that permutation.
and then you su
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 wrote:
> sorry, I fail to understand "the permanent" :-(
>
> If numbers are powers of 2, and the input are these exponent.
>
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 c
why my reply is always delayed for a long-long time?
confusing...
post this msg to see if my previous reply was posted successfully
On Mar 10, 12:14 am, Miroslav Balaz wrote:
> so the permanent is like determinant but without sign in summand.
>
> I have found something interesting in your peobl
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-PA
I don't have polynomial algorithm for this problem, after asking for
help from many persons who are skilled at algorithm design.
So I suspect this problem is another NP-complete problem.
Your hint is great that this problem is possibly neither NP-complete
nor P.
You says, "The only problem i know
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
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 \ne
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 wrote:
> Can't you just sort the numbers, and than multiply first k numbers, than
> second etc. ?
>
> 2009/3/8 Ji
Can't you just sort the numbers, and than multiply first k numbers, than
second etc. ?
2009/3/8 Jim
>
> 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
14 matches
Mail list logo
