# MCCP PTAS

###### tags:`thesis`

[TOC]

## resources

[An Empirical Analysis of Approximation Algorithms for
Euclidean TSP ](https://arxiv.org/abs/1705.09058)

[C++ TSP-Arora-Implementation
](https://github.com/barbaramartina/C---TSP-Arora-Implementation/tree/master)

## Graph manipulation

1. 縮放graph
- 把圖切成大小為 O(𝜖𝑑/8𝑘𝑛)(我會調的參數可以先隨便設) 的方格
- 縮放每一個小方格的邊長為8
- 把點round到方格點上

2. 建立Quadtree
- (a,b)-random shift

3. 放置portals
- 每一個square的邊上 放 m(我會調的參數可以先隨便設)個等距的portals

## DP

$f(P,T,S)=\{t,C\}$

$t=\text{the number of tours in S}$
$C=\text{path\tour sequence}$

$f(P,T,S) = \begin{cases}
𝑏𝑎𝑠𝑒(𝑆) & \text{if S is leaf square}, \\
min_t\{{f(P_{c1},T_{c1},S_{c1})+f(P_{c2},T_{c2},S_{c2}) \\+f(P_{c3},T_{c3},S_{c3})+f(P_{c4},T_{c4},S_{c4})\} } & \text{if S is internal square }, .
\end{cases}$

$S_{ci}$ is i-th children of S

$P =\{P_{c1\text{_outer}}~\cup~P_{c2\text{_outer}}~\cup~P_{c3\text{_outer}}~\cup~P_{c4\text{_outer}} \}$

$T=\{round(Path_1),round(Path_2),..., round(Path_{2p})\}$

$t = \sum_{i=1}^{4} f(P_{ci},T_{ci},S_{ci})[0]+\text{number of tour form by S's inner portals}$

$C = \sum_{i=1}^{4} f(P_{c1},T_{c1},S_{c1})[1]+ \text{tour sequence form by S's inner portals}$

$f(P_{c1},T_{c1},S_{c1})[0]~ \text{is t store in }f(P_{c1},T_{c1},S_{c1})$

$f(P_{c1},T_{c1},S_{c1})[1]~ \text{is C store in }f(P_{c1},T_{c1},S_{c1})$

## 還原tour&切tour

- 把portal-respecting tour的限制解開
- 切cost超過B的tour

## meeting

### Introduction 05/27(week1)

- introduction to the algorithm

### Implementation 06/02(week2)

- input graph
- UAV's speed
- the amonut of data for each IoT device
- dataset
- realworld dataset
- synthetic data generation

## Review

### Review 1

- Experiment :question: :memo:
- Range ( such as the 7x7 km^2 )
- It's beneficial for including OPT ( for small instance )
- Communication issue :question: :memo:
- Mention data tranmission(to nearby base station) before introducing tour cost ( may confuse reader )
- Should explicitly state we did not address the communication part, and all are based on perfect condition

- Some numerical values are presented without prior explanation :question:
- Grid's side length

- Unclear about drone can collect data from multiple sensors simultaneously or not. :question: :memo:

- Information regarding the communication range of the sensors is missing :question: :memo:

### Review 2

- Model not practical

- Reference can be written in a standard and complete way :question: :ok_hand:

### Review 3

- SIP
- The resulting recursive structure may lead to an unbalanced partition

- SMP
- it may not be suitable for large-scale IoT networks with a large number of devices.

- GPUDA algorithm may depend heavily on the graph structure

- The consideration of voids has been added in the experimental evaluation part, which may be a verification of the robustness of the algorithm, but it needs to be explained in the contribution. :question:

### Review 4

- Neglecting other variables and environmental factors like wind speed and climate conditions

- tour time, tour length, path length :question:
- Consistency ?

- Structure :question:
- May be better for placing Related work before GPUDA ?

- It would be good to add a more detailed explanation of the concept of MCCP by adding chapters such as “Backgrounds”. :question:

### Review 5

- Lack of technical innovation or novelty in the proposed solution

- Lack of prototype implementation or experimental evaluation

- No discussion or comparison with other possible directions to solve the IoT data collection problem