Large volumes of available data have led to the emergence of new computational models for data analysis. One such model is captured by the notion of streaming algorithms: given a sequence of N items, the goal is to compute the value of a given function of the input items by a small number of passes and using a sublinear amount of space in N. Streaming algorithms have applications in many areas such as networking and large scale machine learning. Despite a huge amount of work on this area over the last two decades, there are multiple aspects of streaming algorithms that remained poorly understood, such as (a) streaming algorithms for combinatorial optimization problems and (b) incorporating modern machine learning techniques in the design of streaming algorithms.

In the first part of this thesis, we will describe (essentially) optimal streaming algorithms for set cover and maximum coverage, two classic problems in combinatorial optimization. Next, in the second part, we will show how to augment classic streaming algorithms of the frequency estimation and low-rank approximation problems with machine learning oracles in order to improve their space-accuracy tradeoffs. The new algorithms combine the benefits of machine learning with the formal guarantees available through algorithm design theory.

We consider node-weighted network design problems, in particular the survivable network design problem (SNDP) and its prize-collecting version (PC-SNDP). The input consists of a node-weighted undirected graph G = (V;E) and integral connectivity requirements r(st) for each pair of nodes st. The goal is to find a minimum node-weighted subgraph H of G such that, for each pair st, H contains r(st) disjoint paths between s and t. PC-SNDP is a generalization in which the input also includes a penalty π(st) for each pair, and the goal is to find a subgraph H to minimize the sum of the weight of H and the sum of the penalties for all pairs whose connectivity requirements are not fully satisfied by H. We consider three types of connectivity requirements, edge-connectivity (EC), element-connectivity (ELC) and vertex-connectivity (VC). Let k = max_st r(st) be the maximum requirement. There has been no non-trivial approximation for node-weighted PC-SNDP for k > 1 even in edge-connectivity setup. We describe multiroute-flow based relaxations for PC-EC-SNDP and PC-ELC-SNDP and obtain approximation algorithms for PC-SNDP and PC-ELC-SNDP through them. The approximation ratios we obtain for PC-EC-SNDP are similar to those that were previously known for EC-SNDP via combinatorial algorithms. Specifically, for PC-EC-SNDP (and PC-ELC-SNDP) we obtain an O(k log n)-approximation in general graphs and an O(k)-approximation in graphs that exclude a fixed minor. Moreover, based on the approximation algorithm of ELC-SNDP and the reduction method of [Chuzhoy and Khanna, Theory of Computing 2012] we obtain O(k⁴ log² n)-approximation for PC-VC-SNDP which improves to O(k⁴ log n) on instances from a minor-closed families of graphs.