[TECH] A Graph with θ(log(n)) approximation ratio for greedy vertex cover

We know that the greedy algorithm (which picks the vertex with next highest degree) to solve the vertex cover problem is not optimal. However we have 2-Approximation algorithm for the vertex cover problem (based on a integer linear programming formulation). Actually it was not very straight forward to for me prove that the greedy algorithm has an approximation ratio greater than 2. However after some thinking the following construction indeed proves that the greedy algorithms approximation ratio is > 2. In fact we can easily see (from the figure) that the greedy algorithm will first pick the node with highest degree i.e n (the magenta). Then it deletes all the edges adjacent on the magenta node and continues and clearly the greedy algorithm will have all the nodes in the blue bounding box. However its clear that if we choose the nodes in the oval region we get a minimum vertex cover of size n. The size of greedy vertex cover is n/2 + n/3 + n/4 .... n/n ≈ θ(nlog(n)) (for large n) and hence the approximation ratio for this graph is θ(log(n)).

[TECH] On The Uniqueness Of a Perfect Match In Undirected Acyclic graphs.

I was studying about several results related to Tiling Theory. Tiling Theory adds formalism to the question " Given a simple rectangular region (R) can we find a valid tiling by using tiles from a set (T) ". If our tile set (T) is a singleton set with a unit square then we can tile any region. However what if the the tile set contains only a 2x1 rectangle (domino)? what if the tile set contains a set of polymino's (tetris game)?. Although the question may seem very simple there is a rich combinatorial work based on this question. In fact the study about the tiling problem originated from Wang's Conjecture about periodic tiling. Actually the algorithmic research about tiling theory was dormant for quite some time, even the proof for 2x1 dominoes is fairly recent see this . I was reading about the proof and was really impressed by its elegance. Often people consider simple things useless or don't have enough respect for simple facts, however I always find that good results are based on several very simple facts. In fact I would like to highlight simple ideas in every algorithm I study about.

In this proof to prove that the problem is NP-complete for 2x1 domino's a simple fact that " There is exactly only one perfect matching (if at all one exists) in a Tree " is used. This can be proved intuitively as follows.

Let M be the perfect match in the Tree T, if M is not a unique perfect match then there should be some other perfect match lets call it M^'. If we observe the leaf nodes in T which have only one edge adjacent on them so both M and M^' should agree on the matched edges which have leaf nodes of T as the vertices . We can now delete all the leaf nodes and their adjacent edges and continue the argument until we don't have any leaf nodes. Thus from this argument its clear that both M and M^' are the same and hence there is only a unique perfect match if at all if one exists in a tree T.

[TECH] Converting Market Matrix Sparse Representation to Row Compressed Sparse Representation

I wanted to use some good benchmarks to illustrate the performance gains of the Fast Dual Update Algorithm for pre-ordering sparse matrices. University of Florida Sparse Library has a rich collection of sparse matrices from various domains. Unfortunately all the matrices are in Market Matrix format but not in Row Compressed format which I currently use.

The following is a handy script which converts the Market Matrix format to Row Compressed Format mm2rc.pl. The script uses a simple logic based on external sorting.