An optimization problem worthy of our attentionby Stephen Tashi Tags: attention, optimization, worthy 

#1
Jan1313, 11:15 AM

Sci Advisor
P: 3,167

Perhaps forum members can advance science by solving this optimization problem from The Protein Engineer http://proteneer.com/blog/?p=1557
My statement of it: Let M be a N x N symmetric matrix such that N is divisible by 3, all the diagonal entries are 0 and each other entry is either 0 or 1. We think of the matrix entry M[i][j] as representing whether an object i interacts with another object j. Imagine M partitioned into 3x3 submatrices ("tiles"). The "cost" of M is defined as the number of tiles that have at least one nonzero entry. ( I don't undestand the practical reason why the cost is defined that way.) The information in M can be arranged differently by changing the order in which the objects are listed. (i.e. let s be a permutation of the numbers 1,2,...n and define a new matrix M' to have entries M'[i][j] = M[s(i)][s(j)] ) Find an algorithm with determines a matrix M' that has minimum cost and contains the same information as the matrix M. 



#2
Jan1313, 04:07 PM

P: 1,022

Basically, the problem seems to be how do you partition the vertex set of a graph into 3element sets such that the number of edges within all the partitioning subsets is minimized.
My first thought was, the obvious brute force strategy, where you just compute the cost for each permutation. Since there are a lot of permutations, that's computationally expensive. You can do a little better if you only compute one for each partition, but I think there are still a lot of partitions of a big set into 3element sets. A somewhat related problem is this. Say there are n vertices where n is divisible by 3 and let k = n/3. You could then ask whether the graph is kpartite. That would correspond to a cost of zero. My thought was that maybe graph theorists have thought about ways to determine whether a graph is kpartite and that maybe that would help with this problem. Let's do a special case. Say we have a graph with 6 vertices. Then k = 2 and the question is whether the graph is bipartite, which would correspond exactly to the question of whether you can apply the permutations to the matrix to get a cost of zero. The answer is if and only if there are no odd cycles. It's clear that a bipartite graph can't have odd cycles, but the converse is a little more difficult to prove. As it happens, I was wanting to review that very result and the proof. It's not very hard, and I think it's constructive, so there should be an algorithm. Anyway, maybe you could consider this problem as an extension of the question of whether something is kpartite. Like, is it kpartite after you remove one edge, two edges, etc. If you had algorithms for that, it might give you algorithms to minimize that cost. Just a thought. 



#3
Jan1313, 04:10 PM

P: 1,022

Well, of course, there's a big difference here that I forgot about, which is that the size of the partitioning sets has to be 3, but I still wonder if something like that might help.



Register to reply 
Related Discussions  
Worthy Tribute, US Space Shuttle  General Discussion  0  
Determining Worthy Universities  Academic Guidance  1  
Solving Freefall Problem With Special Attention to Units  Introductory Physics Homework  3  
Is this story Caltech worthy?  Academic Guidance  7  
Phd... means what, what makes an idea pHD worthy?  Academic Guidance  1 