This paper addresses the problem of traffic grooming in WDM rings in which all traffic emanates from a single node and all other nodes are destination nodes. This “one-to-many” scenario arises in metropolitan access networks in which one node serves as a “hub” connecting the ring to a larger network as well as in video-on-demand and other multimedia services where a single source node serves a collection of subscriber nodes. The ring comprises a given number of wavelengths of uniform capacity and a variable number of tunable Add-Drop Multiplexers (ADMs) at each node. Given a set of requests at the destination nodes, where each request comprises a bandwidth demand and a profit for fulfilling the request, our objective is to select a subset of the requests and pack (“groom”) them onto the wavelengths such that no wavelength’s capacity is exceeded and the total profit of the selected requests is maximized. Although this problem is NP-complete, we give polynomial time approximation algorithms with excellent theoretical performance validated with experimental results.

In the context of data on cities, we present an example of how to make statistics relevant and meaningful to non-expert users. While the cities of the world are emerging as key players in global processes, from climate change to migration, the body of data on the cities of the world is neither extensive nor well-organized. Towards the end of organizing, understanding, and presenting this data, we have created an online framework called CityRank. To make this data relevant to users, CityRank allows users to upload new data sets and create and share personalized rankings of cities based on the data included in CityRank’s data repository.

In optimization, there is a direct connection between approximation algorithms and inapproximability results: approximation algorithms give lower bounds on how well we can do while inapproximability results give upper bounds. We look for a deeper connection in the case of two techniques: semidefinite programming, which has proved very successful in devising approximation algorithms, and the Unique Games Conjecture, which has led to many inapproximability results. Although on the surface these techniques seem to be unrelated, a series of recent papers suggests otherwise. Is it possible that the Unique Games Conjecture exactly captures the power of semidefinite programming? We state a conjecture formalizing this connection and investigate this conjecture for a small set of problems.