In this dissertation we investigate approximation algorithms for problems defined on networks and streams of data. The unifying theme of all problems discussed is that finding an exact solution to them is impractical. Such impracticality may stem from a provable time complexity characterization in a general computation model, or it may be dictated by constraints on the resources available to the algorithm.

The first problem concerns finding shortest paths in a network with time-variant transit times. We show that under minimal assumptions on the transit time functions, the complexity of the structure of the shortest paths between two network nodes over a time interval may overwhelm a decision maker; thus, it is crucial we devise strategies that approximate such structural complexity.

Another problem on networks presented considers coloring a graph on n nodes with k colors in such a way that all colors are used roughly the same number of times and the number of edges connecting two nodes assigned to different colors is minimized. We prove that the problem is hard to approximate even when restricted to tree instances. Despite this result, we were able to devise efficient approximation algorithms for a relaxed version of the problem on general graphs.

The second part of the dissertation studies problems on streams of data. In this model, a large stream of data is to be processed online using minimal time and memory per data item. These constraints are dictated by the restricted computational resources of the hardware processing the data, and by real time requirements. We first present a simple abstract framework for online approximation of time-series that yields a unified set of algorithms for the data stream model and other variations. Then, we implement our algorithms to solve the problem of identifying network traffic bursts at various and especially fine-grain time scales. The simplicity of our algorithmic framework allows our approximated burst detectors to be implemented directly in the operating system kernel or in constrained hardware such as routers.