A randomized algorithm for matrix sparsification

Matrix sparsification is of prime interest for many applications as it reduces computation time of many matrix operations by many folds which in turn makes many computer applications less computationally complex. In this presentation, I will present a simple random algorithm for the sparsification of matrices. This algorithm and its analysis was given by Sanjeev …

The Group Steiner Tree Problem

Today we will present a randomized polylogarithmic approximation algorithm for the group Steiner tree problem. The problem was introduced by Reich andWidmayer [1]. It arises in wire routing with multi-port terminals in physical VLSI design. The idea of using randomized rounding to solve the group Steiner tree problem was introduced by the paper of Garg, …

Matroids

Matroid is a pair $latex M=(N,I)$ where N is a finite set of elements and I is family of subsets of N called Independent set such that: $latex \phi \in I$ If $latex A \subset B $ and $latex B \in I$ then $latex A \in I$. (Hereditary property)  If $latex A,B \in I$ and $latex |A| <|B|$ and …

Lecture 28 A 1.5 Approximation for Metric Uncapacitated Facility Location

Scribes: Zohair Raza Hassan & Masooma Kazmi Please note that the following approximation algorithm and its analyses are discussed in two papers - the original [BA10], and a paper by the some of the same authors [BM10] which provides a different (and easier) analysis which we used in this presentation. Metric Uncapacitated Facility Location Given a …

The Deep-Cut Ellipsoid Method

Problem Statement: Consider the convex problem: $latex min f(x)$ s.t.  $latex x \in X$ where f is a convex function over the closed and convex set X. We assume that objective function f is subdifferentiable over X and that problem is solvable with $latex X^*$ being its optimal set and $latex f^*$ being its optimal …

Lecture 24: Correlation Clustering

  Definition Correlation clustering is a method for clustering a set of objects into the optimum number of clusters without specifying the number in advance. Given a weighted graph $latex G=(V,E)$ where the edge is characterized by two weights. The positive edge weight $latex w^+$ and negative edge weight $latex w^-$ respectively indicate how similar …

Lecture 22: Max-Cut using SDP

Topic: Randomized 0.88-Approximation Algorithm for Max-Cut Problem using Semi-Definite Program Definitions Strict Quadratic Program: An NP-hard optimization problem in which all degrees of variables lie in {0,2}. Vector Program: A program in which all variables are vectors $latex x_i \in \mathbb{R}^n$, and the objective function and constraints are linear functions of the dot product of vectors …

Lecture 27 – Graph Coloring Problem

Let's just define some terms. Proper Coloring $latex f :V \rightarrow C$ $latex f(i)  \neq f(j) \forall (i,j) \in E$ Chromatic No. $latex X(G) = min_{|C|} \exists$ a proper coloring with C colors FACT 0 $latex X(g) \leq \Delta +1$ where $latex \Delta$ = max degree in G Theorem 1 (Brooks Theorem) $latex X(G) \leq …

Lecture 23 : Max 2 SAT

Max 2-SAT SAT CNF (Conjuctive Normal Form) with two literals in each clause. Find an assignment of $latex n$ vars ($latex v_i$) that satisfies max no. of clauses. In last lecture we saw an algorithm that uses a pair of simple randomized algorithms within a randomized algorithm and it gave us $latex \frac{3}{4}$ OPT result. …

Lecture 20-21 Semi-definite Programming

Max Cut Problem Recall from previous lectures that a cut $latex C= (S,T)$ is a partition of vertices of a given graph into nonempty subset $latex S, T$. With a slight abuse of notation we also refer to the edges going across these two parts as the cut as well i.e. the set { $latex …