Georgia Institute of Technology
Hinted Data Structures with Applications to Optimization and Learning
Abstract
dc:description.abstractThis thesis investigates the interplay among data structures, graph algorithms, and machine learning, providing a fresh lens on conventional perspectives concerning worst-case scenarios and data structure performance. The thesis is divided into two main parts. The first part delves into the concept of Low Stretch Decomposition (LSD), a crucial component in graph algorithm design. The study applies LSDs to devise a nearly linear time algorithm to compute the terminal state of graph diffusions, specifically the 2-norm flow diffusion, and identify local clusters. It also pioneers the examination of LSD on dynamic graphs, leading to the creation of fully dynamic data structures for computing approximate cuts and distances. The second part of the thesis explores how data structures leverage 'hints' to enhance their efficiency. It demonstrates this by solving maximum flows and minimum-cost flow problems using dynamic LSD and an \ell1 Interior Point Method (IPM). The hints derived from the IPM updates expedite the data structure and result in an almost linear time algorithm for the problem. This section also delves into learning-augmented B-trees, which benefit from advice produced by machine learning models. Throughout the thesis, a comprehensive understanding of how optimization algorithms and machine learning models interact with data structures in non-worst-case and non-adaptive ways is pursued.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Chen, Li
- Advisor dc:contributor.advisor
-
- Peng, Richard
- Committee members dc:contributor.committeemember
-
- Vempala, Santosh
- Singh, Mohit
- Gupta, Swati
- van den Brand, Jan
Subjects
dc:subject × 4Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/72683