Approximation Algorithms for Faster Communication and Cheaper Net.pdf (847.43 kB)
Approximation Algorithms for Faster Communication and Cheaper Networks Using Linear Programming
thesis
posted on 2017-08-01, 00:00 authored by Jennifer IglesiasAs we are currently in the information age, people expect access to information to exist by default. In order to facilitate the communication of knowledge, efficient networks must be built. In particular, the networks must be built satisfying some constraints while minimizing cost or time. These constraints often make these problems NP-hard. In this thesis, we investigate two different sets of problems: communicating information quickly and building cheap networks. In the communication problems, the goal is to minimize the number of rounds of communication. In the network design problems the goal is to construct a network of minimum cost.
History
Date
2017-08-01Degree Type
- Dissertation
Department
- Mathematical Sciences
Degree Name
- Doctor of Philosophy (PhD)