Relevant Degree Programs
Affiliations to Research Centres, Institutes & Clusters
Graduate Student Supervision
Master's Student Supervision
Theses completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest theses.
In this thesis, we study the Multidimensional Knapsack Problem (MKP) and two closely related special cases: the Unsplittable Flow Problem on Trees (UFPT), and the Unsplittable Flow Problem on Paths (UFPP). For these problems, when the natural integer programming formulation is relaxed to a linear program, the integrality gap is O(n). Previous work on UFPT and UFPP has established that the addition of rank constraints to the linear program can be effective in some cases at reducing the integrality gap. However, Friggstad and Gao proved that even with all rank constraints added, the integrality gap of UFPT is Ω(√(log n)). Faenza and Sanità showed that a formulation for these problems which approximates the integer hull arbitrarily well must either have exponentially many facets or be described as an extended formulation (i.e., described in a higher dimensional space). We are interested in polynomially sized formulations, so we focus our study on extended formulations. Our first contribution is a greedy algorithm which finds an optimal solution to the linear programming relaxation for the special case of UFPT where all requests share a common endpoint. We apply this to tighten the analysis of hard instances described in the literature. Following this, we describe two approximate extended formulations for MKP using disjunctive programming. The first is a formulation which improves upon the integrality gap of the linear relaxation using only a small number of extra variables and constraints. The second is a polyhedral (1 - ε)-approximate extended formulation for MKP for any 0
We investigate the problem of designing (preferably optimal) online contention resolution schemes (OCRSs). They are a powerful framework for optimization under various combinatorial constraints such as matroids, matchings, knapsacks and their intersections. OCRSs immediately imply prophet inequalities in Bayesian online selection problem. They also have other important applications such as stochastic probing and oblivious posted price mechanisms.We present several novel OCRSs which improve the current state-of-the-art algorithms. We design an optimal 0.5-selectable OCRS over matroids with rank 2, and another optimal 0.5-selectable OCRS over transversal matroids. Previously the best result applicable to these types of matroids was a 0.25-selectable OCRS. Furthermore, we design a 1/(k+1)-selectable OCRS over matchings in k-partite hypergraphs.
In this thesis we investigate the core, or the set of stable solutions, of a cooperative game without side payments. This "multicommodity flow" game was initiallyintroduced by Papadimitriou to model incentives in internet routing. He posed thequestions of whether such stable solutions exist and if we can find them. Markakisand Saberi showed both how to solve this game in the setting with side payments,and that such stable solutions always exist with or without side payments. Yamadaand Karasawa provide an algorithm for generating one core solution in the specialcase when the underlying transit graph is a path (as well as special cases of trees).We provide a new algorithm for generating more core elements and a method to testcore membership efficiently in this same special case. We empirically characterizethis larger set of solutions. The data suggests that stability does not necessarilyimpede efficiency, and that there is little trade-off between efficiency and fairness.