Approximating TSP on Metrics with Bounded Global Growth

Approximating TSP on Metrics with Bounded Global Growth
Chan and Gupta (SODA 2008)

We want to look at k-Clustering on the same metric
About this new metric
- not local
- Every local neighborhood need not be well-behaved
- less restricted
- few dense regions
- well-behaved on average
- global notion of dimension
- correlation dimension
- generalizes doubling dimension
We want to see if we can come up with a QPTAS
What about k-clustering on metrics induced by graphs with bounded treewidths ? On just trees ? Im pretty sure it can be solved exactly in linear time.
Is the tree metric a special case of doubling metric ? If not what is hierarchy of metric spaces ? If any ?

Read Clarkson's survey about dimensions in metric spaces.

Read Kunal Talwar's Bypassing The Embedding

Study About Embedding

Revise Hierarchical Routing in Doubling Metrics

Read Bartal and Fackarenpoel decomposition

Doubling Metric is indeed a generalization of Euclidean metric. Read Gupta Krauthgamer Lee paper on bounded geometries.

Work of Indyk, Linial and Matousek on applications of metrics in algorithms

Indyk and Matousek's Chapter 8

History of Computational geometry

Convex Hulls
Voronoi
Triangulation
Low dimensional optimization
Davenport-Schnizel Sequences
Zone Theorems

Erlebach Paper (SODA 2008)

Erlebach paper (SODA 2008)
Unique Coverage Problem
- NP-hard for unit-disk model - proven by reduction from Independent Set
- extended to budgeted low-covering problem
- For bounded ply, FPTAS
- approx. algo works by looking at squares of size $\delta * \delta$. If a $\frac{1}{c}$ algo exists for these there exists a $\frac{\delta^2}{(1+\delta)^2}$ approximation algorithm. In particular there exists 1/2-approx algo for a square of size 1/2*1/2 Hence a 1/18-approx algo for general case. - Use of envelopes of disks and triples for this proof
Minimum Membership Set Cover Problem
- NP-hard
- not PTAA with ratio better than 2
- for Unit Square, 5-approx if optimum objective value bounded by constant
- Algo: (for unit SQUARES, NOT unit DISKS) use of horizontal slabs, envelopes, sweep-lines, bound on maximum membership
- - 2 approx for any slab
- - proper admissible tuples of squares per sweep line (point)
- - 5 approx in general
What is rectilinear embedding ?

My broader goals

To work in applied algorithmics
- To look at applied algorithms in computational geometry
- - Computational Geometry in relation to cartography
- - Computational Geometry in relation to meshes
- - - Read this http://www.ics.uci.edu/~eppstein/pubs/BerEpp-CEG-95.pdf
- - Computational Geometry in relation to polyhedral models
- - Computational Geometry in relation to air traffic management
- - Look at WACG
To do implementation/heuristic work

Maybe I should talk to Kasturi about this

Why Unique Coverage Does Not Work For Our Problem

We are trying to reduce interference. The unique coverage problem also tries the same. However it does not apply to our case because we are dealing with directional antennas.

Debmalya's Paper

Reading Debmalya's paper. He calls the problem Topology Construction (TC). He shows why fixing an MST as an underlying topology does not work.

The key here is that he assigns obstructions to every edge and hence the heights required to cover that edge vary. This is as against our assumption where we consider obstacles to be uniform and uniformly distributed over all edges to give a much simpler height function (indeed a constant one). It remains to be seen whether in practice this is a reasonable simplifying assumption to be made.

With his height function we can no longer think of the space as Euclidean space anymore. He shows under his setting that selecting a MST as the set of edges to be covered is $\Omega(n)$ worse than optimal. \textbf{However we still need to look at this problem in the Euclidean case. We need to keep the directedness aside and look at this problem too.}

\textbf{Some simplifying assumptions that hold in our case and that he does not consider:
1. Two tall towers can see each other regardless of the distance.}

\textbf{An interesting idea is to start off with a network graph - this could be the graph with edges if between vertices if power transmission is possible (not too far) but how do you fit in interference in this ?}

\textbf{Hehehehe ... interestingly it seems they have defined the problem well for us and left it open for us to work on the geometric version of the problem !!!}

Problems I Am Looking At

Here are some of the problems I intend to consider.

1. The k-Watchtower problem: To find relation with Motorola problem. Probably not useful. Take a look nevertheless. Priority: LOW
2. Global Dimension: Read paper. See what it is. See if our algorithm can be applied to it. Priority: Medium
3. Find out what different metrics people use in practice. Check out results. In particular find out about unweighted metrics. Priority: Medium
4. See if charitable auctions hypothesis can be applied to Motorola 2 problem. Read charitable auctions paper. Priority: Low
5. See if social influence technique in paper is applied to quarantining in disease control model. Read paper. Priority: Very Low
6. Read Debmalya’s paper INFOCOM 2008 Priority: High
7. Try and contrast between approaches towards avoiding interference – our approach (we want redundant coverage) versus Erlebach approach (unique coverage) Priority: medium
8. Learn Linear Programming Priority: medium
9. Learn about Eigenvalues (Linear algebra in general) Priority: medium
10. Learn about MaxCut MinFlow Priority: medium
11. Learn about epsilon nets Priority: medium
12. Correlation between facial features and speech Priority: medium
13. Davenport schnitzel sequences Priority: medium