Sub-linear algorithms for graph problems
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/120411 |
| _version_ | 1826217161764372480 |
|---|---|
| author | Yodpinyanee, Anak |
| author2 | Ronitt Rubinfeld. |
| author_facet | Ronitt Rubinfeld. Yodpinyanee, Anak |
| author_sort | Yodpinyanee, Anak |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. |
| first_indexed | 2024-09-23T16:59:00Z |
| format | Thesis |
| id | mit-1721.1/120411 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:59:00Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1204112019-04-10T08:40:32Z Sub-linear algorithms for graph problems Yodpinyanee, Anak Ronitt Rubinfeld. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018. Cataloged from PDF version of thesis. Includes bibliographical references (pages 189-199). In the face of massive data sets, classical algorithmic models, where the algorithm reads the entire input, performs a full computation, then reports the entire output, are rendered infeasible. To handle these data sets, alternative algorithmic models are suggested to solve problems under the restricted, namely sub-linear, resources such as time, memory or randomness. This thesis aims at addressing these limitations on graph problems and combinatorial optimization problems through a number of different models. First, we consider the graph spanner problem in the local computation algorithm (LCA) model. A graph spanner is a subgraph of the input graph that preserves all pairwise distances up to a small multiplicative stretch. Given a query edge from the input graph, the LCA explores a sub-linear portion of the input graph, then decides whether to include this edge in its spanner or not - the answers to all edge queries constitute the output of the LCA. We provide the first LCA constructions for 3 and 5-spanners of general graphs with almost optimal trade-offs between spanner sizes and stretches, and for fixed-stretch spanners of low maximum-degree graphs. Next, we study the set cover problem in the oracle access model. The algorithm accesses a sub-linear portion of the input set system by probing for elements in a set, and for sets containing an element, then computes an approximate minimum set cover: a collection of an approximately-minimum number of sets whose union includes all elements. We provide probe-efficient algorithms for set cover, and complement our results with almost tight lower bound constructions. We further extend our study to the LP-relaxation variants and to the streaming setting, obtaining the first streaming results for the fractional set cover problem. Lastly, we design local-access generators for a collection of fundamental random graph models. We demonstrate how to generate graphs according to the desired probability distribution in an on-the-fly fashion. Our algorithms receive probes about arbitrary parts of the input graph, then construct just enough of the graph to answer these probes, using only polylogarithmic time, additional space and random bits per probe. We also provide the first implementation of random neighbor probes, which is a basic algorithmic building block with applications in various huge graph models. by Anak Yodpinyanee. Ph. D. 2019-02-14T15:49:10Z 2019-02-14T15:49:10Z 2018 2018 Thesis http://hdl.handle.net/1721.1/120411 1084286489 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 199 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Yodpinyanee, Anak Sub-linear algorithms for graph problems |
| title | Sub-linear algorithms for graph problems |
| title_full | Sub-linear algorithms for graph problems |
| title_fullStr | Sub-linear algorithms for graph problems |
| title_full_unstemmed | Sub-linear algorithms for graph problems |
| title_short | Sub-linear algorithms for graph problems |
| title_sort | sub linear algorithms for graph problems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/120411 |
| work_keys_str_mv | AT yodpinyaneeanak sublinearalgorithmsforgraphproblems |