Kasturi Meeting

Set Cover in Geometric Setting - Disks - Varying size
LP Relaxation solve - scale weights - Weight of discs at any point >= 1/c Weight of disks
Pick a subset R so that if any point is covered by 1/c disks then it is covered by a disk in R
1/c net - clogc approx algo.
To try constant time for case of weighted disks (even if they are unit size)
------------------------------------------------------------------------------------------------
To bound a random algorithm it is ok to show a bound for a particular deterministic algo

Communication Complexity

Communication Models: 2 party model, 2 parties communicate to evaluate a function, each party has part of input, unlimited compuational power.

Communication Complexity - Amount of communication required to perform a task.

Techniques in Approximation Algorithms

Picking up the heaviest job

Jobs scheduled before have less processing time and early release dates.

Jobs scheduled after have less delivery time.

For NP Theory Quick Look Up

Good reference: http://www.nist.gov/dads/

Variance of Average

The variance of the average of N random variables is 1/N times the variance of each of (one of) the random variables. Hence it is always a good practice to take the average of a random variable over several experiments in order to reduce the variance.