Grant: Discovery Grants Program - Individual

Combinatorial optimization problems arise in many areas of everyday life where one needs to distribute scarce resources in a utility-maximizing fashion. Practical instances of relevant problems tend to be NP-hard, and are therefore likely intractable. This proposal focuses on the design of approximation algorithms as one way of addressing the intractability. Such algorithms are efficient and produce solutions whose quality is provably close to that of optimal solutions. In this proposal we focus on the rich subclass of discrete optimization problems that, interpreted broadly, arise in a network context. The long term goal of the proposed research program is to develop versatile and efficient techniques for the design of (approximation-) algorithms for problems in this class.The work proposed here naturally continues my existing research program. Research questions proposed focus mostly on two vibrant areas: (1) Approximate Network Design, and (2) Games in Networks. A typical optimization problem in (1) asks for a minimum-cost sub-graph of a given weighted network that satisfies certain connectivity requirements. This general model captures many classical examples (e.g., from Karp's original list of 21 NP-hard problems), and yet, impressive progress has been made over the last 5-10 years (examples can be found in Byrka et al.'s work on the approximability of the Steiner tree [J. ACM, 2013], or that of Sebo and Vygen on approximating TSP in graphic metrics [Combinatorica, 2014]). Area (2) studies the impact of selfish and strategic behaviour in a network context. As before, the area contains many celebrated results, like Nash's famous work on bargaining [Econometrica, 1950], Shapley & Shubik's study of the cooperative matching game [Int. J. Game Theory, 1971], and the more recent algorithmic extension of the previous two results to the network context due to Kleinberg & Tardos [STOC, 2008]. For each of these areas, I will outline short- and medium-term research goals that are appropriate for graduate students and whose resolution will allow me to make progress towards the proposed long-term goal of my agenda.While much of this proposal focuses on theoretical aspects of CO, the techniques described have significant practical impact. Some of the problems discussed here arose in direct collaboration with industrial partners. Thus, obtaining efficient implementations of theoretical results is a priority of my research.