We must know, we will know !
万物并作，吾以观复

This blog, we still talk about randomized algorithms. Today we will focus on some analysis tools in randomized algorithms. In this blog, we want to explore the probability that some extreme event happens, that is the random variable takes “large” value. So, Markov’s and Chebyshev’s inequalities are also called Tail Inequalities.

In this blog, we will show the power of LP problem and duality in mathematics. In this series of blog, we focus on the method that how to solve LP problem. But a “good” math can interacts to other branches of math. We gonna show how LP can be a tool to prove Farkas’ Lemma, which is the base of Convex Optimization.

This blog, we still talk about randomized algorithms. Today we will focus on Randomized Min-Cut Algorithm.

In this blog, we try to find the relation between primal and dual problems. In specific, we will introduce two theorems – Weak Duality and Strong Duality.

From this blog, we will touch on the randomized algorithms. And today we will focus on Randomized Quicksort Algorithm.

In the end of the series of LP blogs, we will introduce a very important structure in LP problem, that is the dual problem. Dual problem can give us another view of a LP problem. There are a lot of applications of Duality in algorithm, like Max flow and Min Cut problem. Additionally, you can find more application of primal-dual techniques in my another blog series.

In this blog, we will first introduce what is dual problem, how to convert the primal problem to its dual problem.

Now for Simplex algorithm, we only have the last piece of puzzle missing, that is we need to figure out how to find the initial basic feasible solution. In this blog, we will introduce several ways to implement it.

This blog is still talking about “rounding data” strategy and dynamic programing. And this blog will focus on the bin-packing problem.