paralell assignment problem
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050209 (09:43) 
From:  Radu Grigore <radugrigore@g...> 
Subject:  Re: [Camllist] Re: paralell assignment problem 
On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore <radugrigore@gmail.com> wrote: > On Tue, 08 Feb 2005 09:12:32 0800 (PST), skaller > <skaller@users.sourceforge.net> wrote: > > > However it isn't clear (to me) that just picking an arbitrary > > assignment to split into two using a temporary > > actually minimises the number of temporaries. > > I'm mildly convinced that it works. OK, I took 1h to think about this problem more carefully. Now I'm almost convinced that it is NP :) I'll use the example given in the previous mail: a = b+c b = c c = a+b We can read the first equation as "a must be computed before b and c". So we can construct a graph whose edges mean "source should be computed before target". In this case it is: a > b a > c b > c c > a c > b If this graph has no cycles the problem is simple: just do a topological sort and the problem is solved in O(V+E). If the graph has cycles then we need to break them by introducing temporaries. Without looking at the form of RHS expressions, that is without considering computing an expression partially then we are left with two uses for temporaries: 1. hold the original value of a variable 2. hold the result of an expression and write it later to the destination Point (1) requires one extra assignment, while point (2) requires two extra assignments. The effect is however the same: one of the variable's value can be computed as soon as desired. Therefore we will only use (1). [NOTE that your approach used (2) and hence is clearly suboptimal]. The effect of (1) (and (2)) on the constructed graph is that all inedges of a variable are removed. So we have reduced the problem to this: "Given a graph mark as few nodes as possible such that the after removing inedges of marked nodes we obtain a tree". Now, that looks a lot like SETCOVER. In the example above we have these cycles: 1: abc 2: bc 3: ac The set is {1, 2, 3} and the subsets from which we have to choose are a:{1, 3}, b:{2}, c:{1, 2, 3}. The minimum cover is clearly c:{1, 2, 3} and hence the solution is to create a temporary for the original value of c. After removing all inedges of c and topologically sorting the graph we get: c, a, b. So this is the order in which we should do the other assignments. Yes  we reached the correct solution. Now, it looks like that starting from a SETCOVER problem one can build a graph with the right relationship between nodes and cycles and then an assignment problem. I can't give a (semi)formal argument but I have tried on a few instances and the process of construction seems to be fairly algorithmic (although hard to formalize  at least in an email  since I used pictures). This is why I say your problem looks NP. An acceptable algorithm might be this one: 1. detect strongly connected components (optional) 2. within each SCC find all cycles and group them in subsets according to the nodes they have in common 3. within each SCC solve SETCOVER (for cycle sets given by common nodes) 4. sort topologically the graph after removing the inedges of nodes marked at step 3 Step 2 is clearly exponential in the number of variables (consider a complete graph). For step 3 you probably want to use an approximation algorithm. It looks like there are ones with good complexity (but I do not know them so I can't tell anything about the constants). In any case, have a look at: http://www.nada.kth.se/~viggo/wwwcompendium/node146.html If you use the lg C algorithm (C = cycles) then the overall complexity is something like O(2^V), where V is the number of variables.  regards, radu http://rgrig.idilis.ro/