Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a graph whose nodes are bit vectors of length "n" (the graph
contains all 2^n nodes), the edges are defined to be connecting all
the pairs of nodes which differ only at one bit position (Hamming
distance = 1 between n1 and n2 means n1n2 is an edge).
The problem is to produce a partition "k" (say a power of 2), such
that total the number of outgoing edges from the partition are
minimized and the partitioning is load balanced (each partition has
roughly the same number of nodes)
The approaches that I have tried:
(i) A naive partitioning by simply masking of the last lg(k) bits
and assigning to one partition
Load balanced but many outgoing links from each partition
(ii) Assuming that I find seed nodes and grow from them by adding
the nodes in the increasing order of hamming distance I can reduce the
outgoing edges but I am not able to find correct seed nodes.
Assume that n is very large and the way the input output is going
to be tested is through a query interface that asks the placement of
node x and the output is the partition number.
An approximate algorithm would be really helpful
Ex: for n=4 and k=2
{0000,0001,0010, 0100, 1000, 0011, 0101}
{1111, 1110, 1101, 1011, 0111, 1100, 1010}
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
