- Yesterday I had a talk for the “approximation algorithms” course. The title of my talk was “Approximating the Number of Perfect Matchings in Bipartite Graphs” and I presented an algorithm of Jerrum and Sinclair, developed in 1988. I had spent a lot of time (3-4 days) preparing the slides (actually for this talk I learned to use the Beamer package to create LaTeX-based presentations, and the TikZ/PGF package for creating the graphics) and the result was very good, I liked my slides, and I got positive feedback from the audience. The slides can be found here. In a part of the algorithm I described, a Markov chain was used, and to introduce the concept to the audience, I used the intuition of “random walk on a graph” instead of the formal definition. The picture you see above was one of the slides used to illustrate the distribution of a random walker (a happy ghost in this picture) on the vertices of the underlying graph. I was really relieved after the talk since I am not used to present in English.
- The paper I posted about two months ago was accepted in Ars Combinatoria. Another paper which I worked on in the same team (when I was an undergrad) was also recently accepted to appear in Graphs and Combinatorics after some revisions, yoohooo !
- The Winter 2010 term is almost finished – I have one final exam (integer programming) and I have to submit the final report for approximation algorithms. I spent most of my time on the courses, and I also read a few papers of Nick (my supervisor).
- My plan for the next term: I will attend the First Montreal Spring School in Graph Theory in May, and when I return, I will focus on my research (random graphs) and read related stuff (some ideas: The probabilistic methods by Alon-Spencer, Randomized Algorithms by Motwani-Raghavan, Lectures on Random Graphs and Survey on Regular Random graphs by Nick). I won’t take any course but may audit computational geometry from computer science. What a pity I didn’t attend the “Multi-agent Systems” course offered in Winter 2010 in CS.
- A graph theory problem: Prove that there exists an integer k, such that for any connected graph G with more than 2 vertices, one can assign a label from {1,2,…,k} to each edge, such that the sum of the labels of edges incident to every vertex defines a proper coloring for the graph. It has been conjectured that k=3 works, and the currently best known bound is k=5. I think it is a cute problem, see here for more info.

## Posts Tagged ‘approximation algorithms’

### my approximation algorithms talk and some other news

April 8, 2010### The PTAS for Euclidean MST

January 29, 2010The Arora’s PTAS for Euclidean MST is huge. A breakthrough. A great paper full of original ideas. Although it is too complicated for me to understand fully, I can’t help admiring it. I wish I can write one paper like this in my academic life!

### Thomas’ tutorial and CO754 Assignment2

January 20, 2010I have recently studied Thomas’ lecture notes on tree-decompositions on graphs, which gives the reader an insight into the concepts of tree-decomposition, tree-width etc. It had a understand-through-solving-problems approach that I believe is very nice and instructive:

http://people.math.gatech.edu/~thomas/PAP/treenotes.pdf

But the interesting part was that once I saw the problems of the 2nd assignment of approximation algorithms, I found that one of the optional problems is straightforward as the idea was covered in the notes. Specifically, problem 4(b) is easy if you study paragraphs C5-C9 of the notes.