Linear Complementarity Problem

Linear Complementarity Problem (LCP) is a generalization of Linear Programming and a special case of quadratic programming. I stumbled upon LCP theory due to my interest in complexity problems in game theory and PPAD-completeness. As we will see these concepts are very closely related. Let M be a square matrix and q an n dimensional [...]

Read Full Post »

Held Karp Relaxation

The Traveling Salesman Problem (TSP) is undoubtedly the most important and well-studied problem in Combinatorial Optimization. Today’s post is a quick overview of the Held-Karp Relaxation of TSP. TSP : Given a complete undirected graph with non-negative costs for each edge , find a hamiltonian cycle of G with minimum cost. It is well-known that [...]

Read Full Post »

Scarf’s Lemma

Proof and Applications of Scarf’s Lemma……. Today’s post is about Scarf’s Lemma, my recent obsession. I learnt about Scarf’s Lemma while reading Haxell & Wilfong’s paper [HW'08] on Fractional Stable Paths Problem (FSPP). I will write about FSPP in a future post. Today’s post is about the elegant proof of Scarf’s Lemma and its wonderful [...]

Read Full Post »