few problems, approaches and solutions

Monthly Archives: August 2008

min-cost perfect matching

If you would like to play with a minimum-cost perfect matching, klein-tardos is a C++ implementation. The intent of the implementation was to know how the algorithm works. Also, most of the C++ I know is from my experience with this problem. So use should probably be limited to understanding and experimentation of the algorithm. My implementation is based on the algorithm presented in Algorithm Design by Kleinberg, Tardos. priqueue.h is an implementation of priority queue with deletion. indexedList.h provides an abstraction for two lists with a reverse function, which switches element from one list to other. It is used to represent the outgoing and incoming list of a vertex. Reverse function could be used to switch an edge from outgoing list to incoming list.

The algorithm in general is called Hungarian algorithm. The implemented algorithm is different from the once here, here and here. Each iteration finds and augments the shortest augmenting path from the bipartite graph using the Dijkstra’s algorithm. But essentially, it also uses the same fundamental concepts to solve the problem. The idea is to create a matching which doesn’t have negative cycle in its residual graph. A little more formal treatment would be.

Consider a bipartite graph G = (V,E) having cost associated with each edge. If M is a matching in G, GM denotes corresponding residual graph for M. Quoting from Algorithm Design.

Let M be a perfect matching. If there are no negative-cost directed cycles C in GM, then M is a minimum-cost perfect matching.

Prof. Golin’s notes explain the same concept as Equality graph.
Hungarian algorithm counts on this fact to find the minimum-cost matching. A more general version of this statement is also the basis for minimum-cost flow algorithms.

Hungarian algorithm, in each iteration, builds a larger matching while maintaining GM free from negative-cost directed cycles. In the end, algorithm reaches the perfect matching which also is a minimum-cost matching.

Tougher part is to avoid the negative-cost cycles. Thats where the labeling comes in (Feasible labeling in Prof. Golin’s notes). After each augmentation the graph is relabeled, with reduced costs, which don’t change the solution, and also keep the GM free of negative loops.

If you want to know more, you should read the above mentioned notes and if possible Algorithm Design. I have tried to make the core part quite visible in the implementation. Infact, the main loop of the algorithm is just

void min_weight_assignment() {
    initiate_node_prices();

    for (int i=0; i<x.size(); i++) {
        dijkstra_spath(s);  // shortest paths from source
        augment_spath();
        reduce_node_prices();
    }
}

An observation. As I mentioned, all approaches are almost equivalent. The matrix method seems to be different from the others, but the similarity could be seen by considering column nodes as left nodes in bipartite graph, and the row nodes as right once.

my desktop customizations

I have Ubuntu installed on my machine. Its nice and easy to work on. Even then, I have my own set of customizations to add to the system.

The most drastic customization is disabling the window decorations. I have always found it of no use, except for controlling the window, which could easily be made into key-bindings. So now I have the luxury of more screen space, used for the purpose it should be.
Most of my time is spent in terminal, browser or acrobat reader. So again, there are some customizations to achieve better screen usage for these applications. I set my terminal to be a little translucent. Apart from the aesthetic appeal, it allows me to monitor whats going on in the background, if needed. Many a times I use F11 to go fullscreen with terminal. I use emacs for coding, blogging etc. Rather than using the default emacs window, I prefer using terminal to work with emacs (ex: emacs -nw). Coding with the background visible, has its own appeal. Also I can go fullscreen while coding, without much effort (F11). Using the terminal as frontend has another advantage of changing the font size on the run. When I want to have a birds eye view of the code, I just do Ctr-Minus (the minus sign on keyboard). Ctr-0 to go back to the default font size.
Now comes the browser. Again, in need for more screen space, I have Hide Menu extension to hide the whole menu bar. I also remove the Bookmarks Toolbar and Use small Icons and use F11 when convenient. For Acrobat Reader, I frequently use the Ctr-h and F9 key-bindings. Ctr-h hides most bars except the Menu bar and F9 hides the Menu bar. There are many more small customizations I have on my system. Aliases, shortcuts etc. The once presented here are just to pass on some ideas. There are many better places to know more about them.
Here are a few complimentary screen shots of my desktops. In case you are interested to know, I steal my backgrounds from wallpaper.deviantart.com.