Archive for February, 2009

Here is a powerful bitwise trick from a riddle.
Assume a RAM model has words of sufficient long. So a integer vector (x[0],x[1],…,x[n-1]) can be encoded as a word X=x[0]*2^0+x[1]*2^w+x[2]*2^(2w)+… , here w is called width and satisfies 2^w>x[i]. The powerful bitwise trick is to change the width freely in O(1) time. Say we want to change the width of X from w to w’. Let temp_w=max(w,w’) * (n+1). We first enlarge the width of X to temp_w by letting X=X*2^0+ X*2^(temp_w-w)+X*2^(2*(temp_w-w))+… and masking out the unwanted bits of X. Then we narrow the width of X to w’ by letting X=X%(2^(temp_w-w’)-1), which works due to temp_w>=n*w’.

A good application of the above trick is to count the number of ‘1’s in the binary representation of  a integer in O(1) time. Assume the integer X has n bits and let 2^m>n and 2^(m-1)<=n. We consider n as an encoded vector of width 1 and length n and change the width of X to m and X%(2^m-1) is just the answer. The above method need that a word on the RAM has at least (n-1)(n+1)m+1 bits due to the large intermediate temp_w.

In fact the needed word bits can be further reduced to (n-1)m+1, where m=ceil(log n), for this problem.  Assume m and n are relatively prime, otherwise we can do some preprocessing to assure it. Let X’=X*2^0+X*2^n+…+X*2^(n*(m-1)), which is a concatenation of m copies of original X. Then we pick the 0-th, m-th , 2m-th, …, and (n-1)*m-th bits of X’ by masking out other bits. Then the answer is X’%(2^m-1). The fact gcd(m,n)=1 leads to that the 0-th, m-th ,…,(n-1)*m-th bits of X’ contains exactly the original bits of X, although not in the original order.


Read Full Post »

Here is a task schedule problem which can be perfectly solved by network flow techniques.
Given n tasks and m processors, we need to assign each task to exactly one processor. The cost of the i-th processor processes the j-th task is X(i,j) and the communication cost between the i-th task and the j-th task is C(i,j)*|P(i)-P(j)|, if they are assigned to processor P(i) and P(j), respectively. How to find a schedule minimizing the total cost?
It can be transformed into a tricky minimum cut problem in a undirected graph.  First construct n vertex-disjoint paths between source and destination vertex. Each path contains m edges and the i-th path is denoted by (s, v(i,1), v(i,2),…, v(i,m-1), t). The edge weight of the j-th edge on the i-th path is X(i,j)+L, where L is a very large number. Under such construction, the minimum cut must contain exactly one edge from each path and it naturally represent which processor the corresponding task is assigned to. Besides that, v(i,k) is connected with v(j,k) (j!=i) by an edge of weight C(i,j) to reflect communication cost.
Note that the communication cost being the form of C(i,j)*|P(i)-P(j)| is vital to the above model. How about that it’s  just C(i,j)? In that case, can it be solved by network flow techniques?

Read Full Post »

The bottleneck spanning tree problem is to find a tree rooted at a given vertex s minimizing the maximum weight of edges in the tree. For undirected graph, the problem can be simply solved in linear time. For directed graph, Gabow and Tarjan gave an O(m log*n) time algorithm. 

Let E(a,b) be the edge set consisting edges with weight  >a and <=b.
Initialize low and high the minimum and maximum of edge weights.
A. In the i-th iteration, partition E(low,high) into k=f(i) sets E1,E2,…,Ek of almost equal size. Let E0=E(-inf,low). Here f(i) is recursively defined as f(1)=2, f(n)=2^f(n-1).
B. Find the minimum j such that the union edge set E0UE1U…UEj contains a spanning tree.

C. If j=0, return low. Otherwise, let low and high be the minimum and maximum in Ej.
Note that the step A and be done in O( |E(low,high)| log f(i) ) = O(|E(a,b)| f(i-1)) = O(m) time by a median finding and divide-conquer method. Step B can be done in O(m) time.  The number of iteration is O(log*m)=O(log*n). The algorithm is better than Dijkstra’s algorithm, which has a time complexity O(m+nlogn), when the graph is dense.

The bottleneck maximum matching in bipartite graphs problem is to find the maximum cardinality matching with minimum bottleneck edge weight.  A simple combination of binary search and Hopcoft and Carp’s matching algorithm yields an O(m sqrt(n) logn) time algorithm. In fact that can be simply improved to O(m sqrt(nlogn)).
First, Hocropt and Carp’s algorithm has a good property: a matching M of size |M|>=|M*|-n/k can be found in O(km) time. This comes from that after k iterations, the augment paths in the residue graph have lengths at least k+1 and they are vertex-disjoint, so the number of augment paths is at most 2n/(k+2).
Using the above property and binary searching, we can find an bottleneck approximate maximum matching M such that |M| >= |M*|-n/k with minimum bottleneck edge. The remaining part is to augment M to M* by a successive BFS augmenting. When an augmenting fails, an edge with larger weight is added and the BFS starts from the newly added vertex. By that, each vertex is visited at most once in each successful augmenting phase and the total time is O(nm/k). Let k=sqrt(nlogn), we get the promised time complexity.

Read Full Post »

How to count the number of irreducible fractions not greater than R(R<=1) and with denominator not greater than N?
One method is to enumerate denominator D and count integers not greater than D*R and coprime with D. the sub-problem can be solved by utilizing inclusion-exclusion principle to count integers divisible by any prime factor of D in the range [1, D*R] . Assume D has K different prime factors, then it needs to enumerate 2^K factor of D. For appropriate large D, 2^K << sqrt(D), so the bottleneck is integer factorization of D.  The total time complexity is N*sqrt(N).
Another method is much more elegant. Let F(D) be number of irreducible fractions not greater than R and with denominator D. A recursive relation can be obtained: F(D) = floor(R*D) – Sum{ F(d) | D is properly divisible by d }. (This method comes from a related paper. )

Read Full Post »