Project Details
Funding Scheme : General Research Fund
Project Number : 17217716
Project Title(English) : Group Traveling Salesman Problems and Network Connectivity Problems on Fully Dynamic Metric Spaces with Bounded Growth 
Project Title(Chinese) : 完全動態有限增速度量空間下的組旅行商問題與網路連通性問題 
Principal Investigator(English) : Dr Chan, Hubert Tsz Hong 
Principal Investigator(Chinese) :  
Department : Department of Computer Science
Institution : The University of Hong Kong
Co - Investigator(s) :
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2016 / 17
Fund Approved : 672,366
Project Status : On-going
Completion Date : 30-9-2019
Abstract as per original application
This project will investigate new variants of several classical optimization problems that are central to theoretical computer science. In the famous traveling salesman problem (TSP), the points in the metric space represent the cities to be visited, and the goal is to find a shortest tour that visits all required cities and returns to the starting point. In the steiner tree problem, the terminal set is a subset of points that represent cities to be connected, and the goal is to build roads with minimum cost to connect all required cities, possibly using extra cities as intermediate hubs. It is known that for general metric spaces, these problems are NP-hard to approximate with a ratio better than some constant strictly larger than 1. Researchers have shown that for low-dimensional Euclidean metrics, these problems have polynomial time approximation schemes (PTAS’s) that have approximation ratios arbitrarily close to 1. Instead of using the geometric properties of the Euclidean dimension for algorithm design, there has been a long line of research that exploits the combinatorial properties of the underlying metric space via the doubling dimension. A STOC 2012 breakthrough paper achieves a PTAS for the TSP on doubling metrics. We will consider more challenging variants of these problems. For the group version of a problem, the input consists of a collection of subsets of a metric space. In the group TSP, the goal is to find a shortest tour that visits at least one point from each subset. This project has preliminary results in an upcoming SODA 2016 paper, which achieves a PTAS for the group TSP on doubling metrics. This provides new insights and powerful techniques to tackle the following problems that have applications in logistics and dynamic network design. (1) Variants of the group TSP. In the group prize collecting TSP, each unvisited subset incurs a certain penalty, and the goal is to minimize the length of the tour plus the penalties due to unvisited subsets. (2) Group connectivity problems. In the group steiner forest problem, the input consists of a collection of pairs of subsets, and the goal is to return a forest with minimum cost such that each pair of subsets are connected. (3) Fully dynamic setting. For instance, the input is updated by inserting a new subset or deleting an existing subset. The goal is to update the solution efficiently instead of recomputing from scratch.
此專案將探究幾個理論電腦科學研究中核心經典問題的新變種。在著名的旅行商問題中,度量空間中的點可看作一些需要被訪問的城市,而問題的目標是找到一條最短的、訪問所有城市至少一次並回到出發點的路。在斯坦納樹問題中,終端點集合是一個需要被連接的城市的集合,而我們的目標是在允許使用其他不在終端點集的中間點的情況下,修建最小長度的路來連通所有的城市。現在已知上述問題在一般度量空間下即使達到某個比1大的常數近似比都是NP完全的。已有研究表明,這些問題在低維歐氏空間中可以在多項式時間內被近似到任意接近於1的相對誤差,亦即存在多項式時間近似方案。不同於利用歐氏空間的幾何性質來設計演算法,很多研究者利用加倍維度來研究度量空間中的組合性質。在2012年,一篇突破性的STOC會議論文給出了一個旅行商問題在加倍空間下的多項式時間近似方案。我們將考慮這些問題更具挑戰性的變種。 在一個組版本的優化問題中,輸入將含有若干度量空間點集的子集。在組旅行商問題中,目標變為尋找一條最短的經過每個子集中至少一個點的回路。我們在該專案的一個前期成果中得到了對於組旅行商問題的多項式時間近似方案,並發表在SODA 2016會議上。該成果為下述在運輸領域以及動態網路設計領域中有重要應用的問題,給出了深刻的洞悉並且提供了有效的技術。 (1) 組旅行商問題的變種。在組獎金收集旅行商問題中,每個未被訪問的子集會產生一定的懲罰。該問題的目標是最小化路徑長度與懲罰的加和。 (2) 組連通性問題。在組斯坦納森林問題中,輸入將包含若干度量空間點集的子集對。該問題的目標變為尋找一個最小代價的連通所有子集對的森林。 (3) 完全動態化的問題設定。比如,輸入可以要求演算法動態維護插入或者刪除一個子集後的解。這類問題的研究目標是有效地更新解,並避免重新計算。
Research Outcome
Layman's Summary of
Completion Report:
Not yet submitted