|
|
ENQUIRE PROJECT DETAILS BY GENERAL PUBLIC |
| 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 : | School of Computing and Data Science | ||||||||||||||||||||
| Institution : | The University of Hong Kong | ||||||||||||||||||||
| E-mail Address : | hubert@cs.hku.hk | ||||||||||||||||||||
| Tel : | 28578461 | ||||||||||||||||||||
| Co - Investigator(s) : |
|
||||||||||||||||||||
| Panel : | Engineering | ||||||||||||||||||||
| Subject Area : | Computing Science & Information Technology | ||||||||||||||||||||
| Exercise Year : | 2016 / 17 | ||||||||||||||||||||
| Fund Approved : | 672,366 | ||||||||||||||||||||
| Project Status : | Completed | ||||||||||||||||||||
| Completion Date : | 31-3-2020 | ||||||||||||||||||||
| Project Objectives : |
|
||||||||||||||||||||
| Abstract as per original application (English/Chinese): |
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） 完全動態化的問題設定。比如，輸入可以要求演算法動態維護插入或者刪除一個子集後的解。這類問題的研究目標是有效地更新解，並避免重新計算。 |
||||||||||||||||||||
| Realisation of objectives: | Objective 1 To realize the first objective, we have considered the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find the shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We have given a randomized polynomial-time approximation scheme (PTAS) when the regions are fat weakly disjoint. We combined the techniques in the well-known Arora framework, together with the recent PTAS for TSP [STOC 2012: Bartal, Gottlieb, and Krauthgamer 2012] to achieve a PTAS for TSPN. In particular, the following approaches have laid down the technical foundation for this project: (1) Heuristic to detect sparse instances. In the STOC 2012 paper, a minimum spanning tree heuristic is used to estimate the portion of an optimal tour within some ball. We have adapted this for TSPN, in which the challenge is that it is not known if an optimal tour would use points inside the ball to visit regions that intersect the ball. (2) Partially cut regions in the recursion. After a sparse ball is identified by the heuristic, the PTAS framework for TSP uses dynamic programming to solve the instance restricted to the sparse ball and recurse on the remaining instance. For TSPN, it is an important issue to decide whether each region partially intersecting the sparse ball should be solved in the sparse instance or considered in the remaining instance. We have shown that both issues can be resolved by conservatively making the ball in question responsible for all intersecting regions, and we have developed a sophisticated charging argument to bound the cost of combining tours in the recursion. The result is that we have improved the running time’s dependence on the doubling dimension, which has appeared in TALG 2018. The above techniques have allowed us to design a PTAS for the prize collecting traveling salesman problem as well. The cost is the length of the tour plus the penalty due to uncovered points. We have augmented the standard the dynamic program which employs divide-and-conquer strategies and sparse instance decompositions, and the result has been published in ESA 2018. Objective 2 To realize the objective of applying our techniques to connectivity problems, we have achieved a randomized PTAS for the Steiner forest problem in doubling metrics. Before our work, a PTAS was given only for the Euclidean plane in [FOCS 2008: Borradaile, Klein, Mathieu]. We have extended the techniques developed in Objective 1 to connectivity problems in the following ways: (1) We have proved a technical lemma showing that Steiner points have to be ``near"" the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. (2) We have developed a novel algorithmic technique known as ``adaptive cells"" to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed “uniform cells” in the FOCS 2008 paper, whose techniques cannot be readily applied to doubling metrics. Our results have appeared in FOCS 2016 and SICOMP 2018. The approaches that we used for the prize collecting TSP in Objective 1 have also inspired solutions for the connectivity counterpart. Indeed, we have developed a unified framework for designing PTAS’s that can be applied to both TSP and Steiner tree variants of the prize collecting problem in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for TSP, while it needs to be a tree for Steiner tree. However, since it is unknown which part of the optimal cost is due to edge lengths and which part is due to penalties of uncovered terminals, we have developed new techniques to apply previous divide-and-conquer strategies and sparse instance decompositions. Specifically, we have revisited the sparsity structural lemma in the literature for TSP-like problems. Intuitively, it says that if a solution is sparse, then there exists a structurally light approximate solution. We have given this lemma a more formal treatment and the result has appeared in TALG 2020. Objective 3 In order to employ our techniques to the fully dynamic settings in Objective 3, we first design algorithms for finding dense regions in the input evolving graph. Tatti and Gionis [WWW 2015] presented a novel graph decomposition (known as the locally-dense decomposition) that is similar to the well-known k-core decomposition, with the additional property that its components are arranged in order of their densities. We have devised an efficient algorithm which is able to compute exact locally-dense decompositions based on the classic Frank-Wolfe algorithm, which is similar to gradient descent and can be efficiently implemented. Efficiency is important as the input graph can be rapidly evolving. We have provided a rigorous study of our algorithms and their convergence rates. Our results have appeared in WWW 2017. Since our PTASs are based on identifying instances with critical densities, we have studied the problem of maintaining densest subsets in fully dynamic graphs. The goal of the problem is to find a subset of nodes that induces a graph with maximum average degree. We have considered hypergraphs, which generalizes the problem to a wider class of networks in which edges might have different cardinalities and contain more than 2 nodes. We have developed both exact algorithms and a near-linear time r-approximation algorithm for the problem, where r is the maximum cardinality of an edge in the hypergraph. In the dynamic setting, an adversary can insert or delete an edge from the hypergraph in each round and the goal is to maintain efficiently an approximation of the densest subgraph. Our dynamic approximation algorithms have amortized polylogarithmic update times. Extensive experiments have been performed on large real datasets to validate the effectiveness and efficiency of our algorithms. The results have appeared in CIKM 2017. We have further investigated fully dynamic approximation algorithms in the context of clustering, which provides a fundamental tool for decomposing a metric space. In particular, the net decomposition technique for doubling metrics can be achieved by a k-center algorithm. We have designed an approximation algorithm for the k-center clustering problem with small amortized cost under the fully dynamic adversarial model. Our results have appeared in WWW 2018. Finally, we have also designed algorithms to maintain approximate core values in dynamic hypergraphs. The results are published in TKDD 2020. | ||||||||||||||||||||
| Summary of objectives addressed: |
|
||||||||||||||||||||
| Research Outcome | |||||||||||||||||||||
| Major findings and research outcome: | For Objective 1, we have designed a PTAS for the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. Based on the well-known Arora divide-and-conquer framework, we have developed a sophisticated charging argument to analyse the cost of recursion. We have improved the running time’s dependence on the doubling dimension and the results have appeared in TALG 2018. The techniques have also allowed us to design a PTAS for the prize collecting traveling salesman problem as well. In particular, we have extended the divide-and-conquer strategy by sparse instance decompositions, and the result has been published in ESA 2018. For Objective 2, we have achieved a randomized PTAS for the Steiner forest problem in doubling metrics. In particular, we have defined a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. Moreover, we have developed a novel algorithmic technique known as ``adaptive cells"" to overcome the difficulty of keeping track of multiple components in a solution. Our results have appeared in FOCS 2016 and SICOMP 2018. Furthermore, we have developed a unified framework for designing PTAS’s that can be applied to both TSP and Steiner tree variants of the prize collecting problem in doubling metrics. The key technique is a sparsity structural lemma that states that if a solution is sparse, then there exists a structurally light approximate solution. The result has appeared in TALG 2020. For Objective 3, we have designed algorithms for finding dense regions in an input graph. Specifically, we have devised an efficient algorithm which is able to compute exact locally-dense decompositions based on the classic Frank-Wolfe algorithm, which is similar to gradient descent and can be efficiently implemented. The results have appeared in WWW 2017. We have also studied the problem of maintaining densest subsets in fully dynamic hypergraphs. We have designed both exact and approximate algorithms with amortized polylogarithmic update times. Extensive experiments have been performed to validate the effectiveness and efficiency of our algorithms. The results have appeared in CIKM 2017. Finally, under the fully dynamic settings, we have achieved an approximate algorithm for the k-center problem in WWW 2018 and an algorithm to maintain approximate core values in TKDD 2020, where the update time is poly-logarithmic. | ||||||||||||||||||||
| Potential for further development of the research and the proposed course of action: |
In this project, we have developed algorithms for various variants of TSP and connectivity problems in doubling metrics. One important insight is that these algorithms identify sparse regions in the input instance. Future research directions can investigate other notions of sparsity or density, which can facilitate decompositions with desirable properties that are pertinent to more general problems. In the fully dynamic settings, the input to the problem changes as time progresses and the algorithms developed in this project have fast poly-logarithmic time, but use polynomial amount of memory. Further research can consider the streaming setting in which the algorithm only has (sub-) linear memory. A major focus of this project is on metric spaces which capture a binary relationship between nodes in the input. Towards the end of the project, we have considered hypergraphs that can capture higher-order relationships between different entities. We have started to consider hypergraph decompositions which will offer a useful tool to design divide-and-conquer and recursive algorithms for future research. An interesting challenge is to achieve practical algorithms whose performances scale desirably as the sizes of the hyperedges increase. | ||||||||||||||||||||
| Layman's Summary of Completion Report: | In this project, we have developed mathematical tools utilizing recent technical breakthroughs regarding metric space dimension, and designed algorithms for several variants of the traveling salesman problem (TSP) and connectivity problems, which have influence on the wider computer science community in general. A highlight of our results is a unified framework that captures the prize collecting variants of both TSP and the Steiner tree problem. We have also considered the more realistic fully dynamic settings in which the input changes as time progresses. We have shown that for several decomposition and clustering problems, it is possible to update the solution quickly without recomputing from scratch. We have designed dynamic data structures that can achieve theoretical tradeoffs between the approximation ratio and the update time, which have been verified by experiments on real-world data. We believe that this project has developed new techniques in combinatorial optimization and approximation algorithm design, which will have significant impacts on both theoretical and application-driven research. | ||||||||||||||||||||
| Research Output | |||||||||||||||||||||
| Peer-reviewed journal publication(s) arising directly from this research project : (* denotes the corresponding author) |
|
||||||||||||||||||||
| Recognized international conference(s) in which paper(s) related to this research project was/were delivered : |
|
||||||||||||||||||||
| Other impact (e.g. award of patents or prizes, collaboration with other research institutions, technology transfer, etc.): |
|||||||||||||||||||||
| SCREEN ID: SCRRM00542 |