How to install LaTeX in windows

Step1:
Download editor from TexnicCenter(http://www.texniccenter.org/).

Step2:
Download MiKTex from MiKTeX site(http://miktex.org/).

Step3:
Install MiKTeX.

Step4:
Install Texnic.
Provide ClassPath for MiKTeX as C:\Program Files\MiKTeX 2.8\miktex\bin.

Step5: Build(ctrl+F7), View(F5)

Bin Packing

Farnandez DelaVega Approach:

1. LP is based on configurations (m-tuple where m is the types of items).

2. No. of configurations exponential to m. To reduce configurations/constraints ignore items with size e/2.

3. Linear grouping. OPT(I')+k are sufficient to pack items after rounding and discarding on (n/k) groups. First group discarded rest are rounded to the highest size in the group.

m= n/k <>

Rounded items are packed in OPT+2/(e^2).

Discarded items need e.OPT.(e.OPT is given to pack k extra items k.SIZE(I).)

Small discarded items are in 1 bin.

(1+e)OPT+ 2/(e^2) +1 bins.

================================================================

Karp-Karmarkar Approach:

1. a_n>= 1/SIZE(I). -- Smaller pieces are packed later.

2. Geometric Grouping:

pack until total size exceeds 2. So, 2 <= size of gp <=3

G_i is i'th group with n_i elements.

Discard G_1, G_r and n_i - n_(i-1) in G_i.

3. Number of distinct pieces is <= SIZE(I)/2.

Discarded pieces total size = O(log (SIZE(I)))

Approximation Algorithms

Recently I started studying Approximation Algorithms in details. Though this area was touched in our UG Algo course, the browsing was really nominal. Let me introduce some basic terms in Approx Algo for future references:

Some NPC problems allow poly-time algo that achieves smaller approximation ratios by using more and more computation time. Here comes the notion of Approximation Scheme.

It provides (1+e)-Approximation Algo for each e>0.

PTAS(Polynomial Time Approximation Scheme): For any fixed e, the scheme runs in polynomial in the size of the input instance, not in p(1/e).

FPTAS(Fully PTAS): For any fixed e, the scheme runs in polynomial in the size of the input instance as well as 1/e.

APTAS(Asymptotic PTAS):

p.OPT(I)+d -> 1 as OPT(I)-> infinity, Asymptotic Guarantee

if d=0, it is PTAS.


APTAS can run in linear in n, but exponentially on e. Its output never exceeds (1+e)OPT(I)+f(e).

Computational Geometry

1. Voronoi Diagram/Delaunay Triangulation
2. Art Gallery/Visibility
3. Convex Hull
4. Borsuk-Ulam/ham-Sandwich
5. Helly-redon
6. Plane Sweep
7. DCEL/Line Arrangement
8. LP
9. Motion Planing
10. Trapezoidal Map
11. Triangulation

Data Structures:
k-d trees, orthogonal range trees, interval trees and segment trees.

Some interesting HARD problems

Each of these problems need some in depth analysis and attention for a grad "theory" student:

Set Cover Problem
Bin Packing Problem
Facility Location Problem
Knapsack Problem
TSP
Hamiltonian Path Problem
Vertex Cover Problem
Partition Problem
Graph Coloring
Steiner Tree

Thing to Study for Theoretical Computer Science

I am making a list of the subjects that I need to study. Most of these subjects are related to mathematics and theoretical computer science.

1. Approximation Algorithms:
Specially usage of LP-Duality and local search in different problems.
Vijay Vazirani's book(a preliminary version is available on net) is a good reference for this.

2. Randomized Algorithms:
Use of Probabilistic Methods, Lovasz local lemma and Markov Model.
Raghavan-Motwani is a good source for this.

3. Algebraic Topology:
Munkres is a good source for General Topology. Allen Hatcher is a good reference for point-set and Algebraic topology.

4. Algebra/Group Theory/Linear Algebra:
Herstein is a good source.

5. Convex Optimization/Linear Programming:

6. Information theory:

7. Game Theory:

8. Theory of Computation and Complexity.

9. Analysis:
For measure theory etc. -- more like a maths background.

10. Quantum Computation:
A new field. May need help of a Physicist friend.

11. Probability and Statistics:
Have a brush with UG textbook. :)

12. Combinatorics and Combinatorial Algorithms:

-- Will add more later.

Dynamic Algorithm

I have created this blog account long time back.

But never found time and energy to jot down my thoughts.

Recently Sam-da(Sambuddha Roy, My colleague at IRL) suggested me to write a blog on the problems that I am working on.

Hence, the effort starts. :)

Today I will talk about Dynamic Geometric Algorithms(DGA). I need to do a literature survey whether there exists any algorithms like this. But first, let's start from scratch.

So, what is this DGA? Generally, all the geometric algorithms that I have studied are for static points. I didnot find any algorithm that discusses the same when the points are moving. So, my question is given n moving points, how will their convex hull(CH) or Voronoi Diagram(VD) or Ham-Sandwich cut will change? It appears that for Ham Sandwich cut things are simple. But I am not too sure about VD and CH.

SO, these are the open problems to me now:

1. Given start position of n moving points can we do some precomputation so that at t=T for any given point we can say which point is its closest?

2. Given start position of n moving points can we do some precomputation so that at t=T we can say which points are on the convex hull?

I have to think more on this domain of dynamic algorithms.

Your suggestion and algorithms are welcome.

Signing off,

AK