Wednesday, September 17, 2008

[TECH] Cauchy's inequality a great tool for approximation algorithms

Its been really long since I made a post, all these day's I'm doing a lot of theory and trying to come up with approximation algorithms to the Border Length Minimization Problem. After a long time I did prove the problem is NP-hard by reducing the T.S.P problem to the B.L.M.P problem. I'm now trying to find some approximation algorithms for the problem. I thought if I could strengthen my skills on inequalities it would be really great and I found a great problem book for inequalities by Michael Steele which has a good collections of problems on inequalities. In this post I provide my solutions to some of the problems which seemed interesting.

\multicolumn{3}{c}{\text{The following is...
\Rightarrow \text{L.H.S} \leq \sqrt{6} && \\

No comments: