April 15 (Tue), 16:30-18:00, Room 115 (1F)
Degree-Bounded Spanning Trees
     We consider the minimum spanning tree problem under the additional restriction that all degrees of the spanning tree must be at most a given value k. We describe two approaches, one by speaker and one by Mohit Singh and Lap Chi Lau. These results show that one can efficiently find a spanning tree of maximum degree at most k+2, or even at most k+1 for the second approach, whose cost is at most the cost of the optimum spanning tree of maximum degree k. This is best possible, as the problem of just deciding whether a graph has a spanning tree of maximum degree k is NP-complete.
     The first approach uses a sequence of simple algebraic, polyhedral and combinatorial arguments, and relies on uncrossing, polyhedral characterizations, matroid intersection and graph orientation. The second approach also uses uncrossing and is a prime example of iterative relaxation, a new technique extending Jain's iterative rounding.

April 17 (Thu), 16:30-18:00, Room 115 (1F)
Single-Source Unsplittable Flows
     The unsplittable flow problem is a multicommodity flow problem in which each demand has to be routed on a single path from its origin to its destination. This problem generalizes the disjoint path problem. We focus our attention on the single-source case, in which all requests emanate from the same vertex. This special case is still NP-hard and has several interesting and important special cases.
     If the necessary cut condition is satisfied, we show how to compute an unsplittable flow such that the total flow through an edge exceeds its capacity by at most the maximum demand. For graphs in which all capacities are at least the maximum demand, this gives an unsplittable flow with congestion at most 2, and this result is best possible. Related results will also be discussed.
     This is joint work with Yefim Dinitz and Naveen Garg.

April 22 (Tue), 16:30-18:00, Room 115 (1F)
Cyclic Orderings of Matroids
     Given a matroid M, (a weighted version of) Edmonds' base covering (or forest partitioning) theorem says that the minimum number Γ(M,c) of bases (or forests) needed to cover c(e) times element e for every e is equal to the ceiling of the maximum of c(A)/r(A) over all sets A. This can be derived from matroid union or matroid intersection, and a cover can be obtained efficiently. van den Heuvel and Thomassé have extended this result and have proved that Γ(M,c) forests can be chosen and labelled cyclically so that every element e appears in c(e) consecutive forests. We will discuss this result, its existential proof, and conjectured variants and generalizations. In particular, finding this cyclic partition in an efficient way is open.

April 24 (Thu), 16:30-18:00, Room 115 (1F)
Deformable Polygon Representations and Near-Minimum Cuts
     Imagine a convex polygon with some of its diagonals drawn in the plane, and elements assigned to the cells defined by the diagonals. To each diagonal, we can associate the complementary sets of elements on each side, and this gives a symmetric family of sets. We provide a characterization in terms of excluded configurations of those symmetric families representable by polygons which can be arbitrarily deformed in a convex way. The proof will be sketched.
     As a corollary, this deformable polygon representation is shown to provide a representation of all cuts in a (weighted) undirected graph whose value is within a factor less than 6/5 of the edge-connectivity. This extends the classical cactus representation of Dinitz, Karzanov, and Lomonosov for all minimum cuts.
     This is joint work with Andras Benczur.

May 1 (Thu), 16:30-18:00, Room 115 (1F)
An Approximate König Theorem for Edge-Coloring Weighted Bipartite Graphs
     We study a generalization of edge coloring bipartite graphs in which every edge has a weight in [0,1] and the coloring of the edges must satisfy that the sum of the weights of the edges of any color incident to a vertex v must be at most 1. This problem arises in the study of non-blocking interconnection networks in the multi-rate setting. Some introductory background on interconnection networks will be given.
     We will derive an approximate König's theorem for edge-coloring weighted bipartite graphs. This provides an upper bound on the size of rearrangeable Clos networks, improving previous bounds of Du et al.
     Our analysis involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing.
     This is joint work with Jose Correa.

May 8 (Thu), 16:30-18:00, Room 115 (1F)
Approximately Learning Submodular Functions
     We consider the problem of learning a submodular function on a ground set of size n. The problem is stated as follows: Can we make a polynomial number of (value) queries to a submodular function, and then approximate the submodular function on any other set to within some factor? We partially answer this question by proving the following results. First, we show that one cannot find a learning algorithm that achieves a factor better than Ω((√n) log n), even if the queries are chosen adaptively, and even if the function is monotone. Moreover, we show that any such algorithm must perform Ω(n / log n) if the queries are chosen non-adaptively, even if f is monotone, and this result is tight. That is, there exists an algorithm using non-adaptive queries which can approximate a monotone submodular function to within a factor O(n / log n). For monotone functions, we prove that there exists a function using O(n^2) space which approximates a monotone submodular function to within a factor √n. This involves approximating a polyhedron with maximum volume ellipsoids.
     This is joint work with Nick Harvey, Bobby Kleinberg and Vahab Mirrokni.