On Universal and Differentially Private Steiner Trees and TSPs

Given a collection of vertices in a network, the problem of finding the minimum cost sub-network connecting a set of client nodes to a dedicated hub-node is the Steiner tree problem. Consider the following two twists. In the first setting, the set of client nodes is unknown, and the algorithm needs to output a master tree which "works well" for all plausible set of clients. In the second setting, the set of clients is known, however, the algorithm's output must respect privacy constraints and not reveal any information about a node (of it being a client or a not). These two settings, defined similarly for the traveling salesman problem, lead to the universal and private versions of the problem, respectively. Clearly, these need the design of new classes of algorithms and the question that naturally arises is: how good/bad is the performance of these compared to the traditional algorithms?

After giving precise definitions of the problems in hand, we'll resolve the above question for the above two problems by giving lower bounds which match the known upper bounds (which also we'll sketch) up to constant factors. Our constructions are simple, and I'll attempt to convey them in this self contained talk (joint work with Anand Bhalgat and Sanjeev Khanna, both at University of Pennsylvania).