Efficient Algorithms for Large Scale Network Problems
出版項
2020
說明
1 online resource (206 pages)
文字
text
無媒介
computer
成冊
online resource
附註
Source: Dissertations Abstracts International, Volume: 81-11, Section: B
Advisor: Pettie, Seth
Thesis (Ph.D.)--University of Michigan, 2020
Includes bibliographical references
In recent years, the growing scale of data has renewed our understanding of what is an efficient algorithm and poses many essential challenges for the algorithm designers. This thesis aims to improve our understanding of many algorithmic problems in this context. These include problems in communication complexity, matching theory, and approximate query processing for database systems.We first study the fundamental and well-known question of SetIntersection in communication complexity. We give a result that incorporates the error probability as an independent parameter into the classical trade-off between round complexity and communication complexity. We show that any \uD835\uDC5F-round protocol that errs with error probability 2-E requires Ω(Ek1/\uD835\uDC5F) bits of communication. We also give several almost matching upper bounds.In matching theory, we first study several generalizations of the ordinary matching problem, namely the f-matching and f-edge cover problem. We also consider the problem of computing a minimum weight perfect matching in a metric space with moderate expansion. We give almost linear time approximation algorithms for all these problems.Finally, we study the sample-based join problem in approximate query processing. We present a result that improves our understanding of the effectiveness and limitations in using sampling to approximate join queries and provides a guideline for practitioners in building AQP systems from a theory perspective
Electronic reproduction. Ann Arbor, Mich. : ProQuest, 2020
