EPFL Theory and Combinatorics Reading Group

Upcoming Talks:

• No upcoming talks

Past Talks:

• Friday, June 27, 2014: Slobodan Mitrović, Sketching Graph Cuts
  Given an n-vertex graph G = (V, E), and an eps in (0, 1), we show how to devise a sketch, i.e. a data structure, of size tilde{O}(n / eps) bits from which the capacity of any cut (S, V S) can be reported w.h.p. within approximation factor (1 + eps).
  
  The result I am going to present is from paper The Sketching Complexity of Graph Cuts, by Alexandr Andoni, Robert Krauthgamer, and David P. Woodruff.
• Friday, May 23, 2014: Abbas Bazzi, Optimal Inaproximability Results for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover
  The talk is based on a paper by S. Sachdeva and R. Saket entitled Optimal Inaproximability Results for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. I will be presenting a sketch of the proof for the Structural Hardness for Hypergraph Vertex Cover, and showing how to use this result to prove a (2-epsilon) NP-hardness for the "Concurrent Open Shop Problem", and (2-epsilon) NP-hardness for the "Assembly Line Problem".
• Friday, May 16, 2014: Chidambaram Annamalai, Subquadratic time algorithms for 3SUM
  The 3SUM problem is, without exaggeration, simply stated: Given a set S of n reals do there exist three numbers a,b,c in S such that a + b + c = 0? An O(n^2) algorithm for the problem is easy but no faster algorithms were known for a long time. So much so that the conjectured Omega(n^2) time bound has been used to prove many running time lower bounds in computational geometry. Recently Gronlund and Pettie (http://arxiv.org/abs/1404.0799) showed that the 3SUM in fact admits polylogarithmic speedups over the n^2 running time. Their techniques are quite similar to the ones used to break the n^3 barrier in the all pairs shortest paths problem in graphs. In this talk I will present the main result of Gronlund and Pettie and discuss possible ideas for improvements.
• Thursday, May 1, 2014: Carsten Moldenhauer, Hardness of Edge-Disjoint-Paths
  I will present the hardness of approximation result for the edge-disjoint-paths problem by Andrews, Chuzhoy, Khanna, Zhang (STOC and FOCS 2005). The result is obtained by first using a PCP characterization and then using a clever construction to yield a gap. I will state the PCP characterization and present the main motivations (sometimes omitting technical details) of the graph construction.
• Thursday, April 17, 2014: Christos Kalaitzis, Finding Minimum Latency Tours on Trees
  The Minimum Latency Problem is a variant of the well-known Traveling Salesman Problem. In this case, rather than finding a tour of minimum cost, we are interested in finding a tour which minimizes the average time we visit each city. The result I am going to present is a 3.18-approximation algorithm for the MLP problem on a special class of graphs, whose most natural subclass is that of trees. The presentation will be based on the paper Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls, by A. Archer and A. Blasiak.
• Friday, April 4, 2014: Ashkan Norouzi, Dependent Randomized Rounding for Matroid Polytopes and Applications
  I will present some high level ideas of paper Dependent Randomized Rounding for Matroid Polytopes and Applications by Chandra Chekuri, Jan Vondrak, and Rico Zenklusen.
• Thursday, April 3, 2014: Yuri Faenza, How Good Are Sparse Cutting-Planes?
  (Based on the 2014 paper by Dey, Molinaro, and Wang How Good Are Sparse Cutting-Planes?)
  Given a polyope P let P^k be its approximation obtained using all valid inequalities for P that have at most k non-zero coefficients ("k-sparse cuts"). Let d(P;P^k) = max_{x in P^k} min_{yin P} ||x - y|| as a measure of the quality of k-sparse cuts.
  I will present two result from the paper above. The first one is a general upper bound on d(P;P^k) which depend on the number of vertices in the polytope and exhibits three
  phases as k increases. Second, a lower bound on d(P;P^k) for random polytopes that shows that the upper bounds are quite tight.
• Monday, March 31, 2014: Farah Charab, Faster All Pairs Shortest Path Problem via Circuit Complexity
  (Based on Faster all-pairs shortest paths via circuit complexity by Ryan Williams.)
  The fastest algorithm for solving APSP on general graph runs in time n^3/log^{2}n. I will present a new method for computing APSP that runs faster than n^3/log^{k}n for every k. This new method uses tool from circuit complexity.
• Friday, March 28, 2014: Slobodan Mitrović, Cut-Based Hierarchical Decompositions of Graphs
  (Based on paper Computing Cut-Based Hierarchical Decompositions in Almost Linear Time by Harald Racke, Chintan Shah and Hanjo Taubig.)
  Hierarchical tree decompositions lie at the heart of oblivious routing strategies. I will present a fast construction algorithm for one such decomposition that approximates cuts of a given graph up to a factor of O(log^4 n).
• Wednesday, March 19, 2014: Adrian Bock, Finding Small Stabilizers for Unstable Graphs
  An undirected graph G = (V,E) is stable if its inessential vertices (those that are exposed by at least one maximum matching) form a stable set. We call a set of edges F ⊆ E to be a stabilizer if its removal from G yields a stable graph. In this talk we study the following natural edge-deletion question: given a graph G = (V, E), can we find a minimum-cardinality stabilizer?
  
  We show that this problem is vertex-cover hard. We then prove that there is a minimum-cardinality stabilizer that avoids some maximum matching of G. We employ this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.
• Monday, March 17, 2014: Chidambaram Annamalai, Topologically Sweeping an Arrangement
  Given an arrangement of lines on the plane I will present a quadratic time algorithm by Edelsbrunner and Guibas that sweeps over the set of O(n^2) intersection points in a "topological" order. This ordering turns out to be useful for several geometrical problems such as finding the minimum area triangle or the largest empty convex set in a set of points on the plane. Their method also generalizes to higher dimensions in a natural way.
• Wednesday, March 12, 2014: Alfonso Cevallos, Two Results on the Weight of Union-closed Families of Sets
  For a finite universe set U, a family of subsets F is union-closed if, for any two sets in F, its union is also in F. Frankl's conjecture states that for such a family F, there is always an element x in U that is contained in at least half of the sets in F. This is an elementary problem in combinatorics that has been open for more than 30 years. We study the related notion of weight of F:
  
  W(F) = sum_{A in F} |A| = sum_{x in U} |{A | x in A in F}|
  
  We present two tight lower bounds for the value of the weight (Reimer '03 and Falgas-Ravry '11). These results and their proofs give us a better understanding of the structure of union-closed families.
• Friday, March 7, 2014: Abbas Bazzi, Hastad 3-bit PCP Linearity Testing
  I will be talking about a part of Hastad's result, the way it is described in Subash Khot's thesis.
• Friday, February 28, 2014: Christos Kalaitzis, Approximating Graphic TSP by Matchings
  I will talk about the use of matchings in designing approximation algorithms for the metric TSP problem. Generally, matchings are used in order to add edges to a graph, with the purpose of making it Eulerian. The approach I will present addresses the issue of how to allow for the removal of certain edges, in order to have a decreased final cost. For graph-TSP(i.e. TSP on graph metrics) this approach results in a 1.461-approximation algorithm, with respect to the Held-Karp relaxation, and for certain classes of graphs it matches the conjectured ratio of 4/3.
  The results I will present appear in the paper Approximating Graphic TSP by Matchings, by Tobias M�mke and Ola Svensson.
• Friday, February 21, 2014: Ashkan Norouzi, Improved Approximation Algorithm for the Uncapacitated Facility Location Problem
  I will present (1+2/e)-approximation algorithm by Chudak and Shmoys.
• Thursday, February 20, 2014: Nguyen Viet Hang, A Constant-factor Approximation for Minimum-cost k-node-connected Subgraphs
  (Based on Approximating minimum-cost k-node connected subgraphs via independence-free graphs by Joseph Cheriyan, L�szl� A. V�gh, FOCS 2013.)
  
  Given a k-node-connected graph with edge costs. The minimum-cost k-node-connected subgraph problem asks for a spanning k-node-connected subgraph of minimum cost. I will present the 6-approximation algorithm by Cheriyan and V�gh (for graphs with at least k^3(k-1)+k nodes).
• Friday, January 31, 2014: Slobodan Mitrović, Beyond the Flow Decomposition Barrier
  (Based on Beyond the flow decomposition barrier by Andrew V. Goldberg, and Satish Rao.)
  Given a graph G on n vertices and m arbitrary-capacity edges, I will present an algorithm that computes a maximum s-t flow in G in time tilde{O}(min(n^{2/3}, m^{1/2}) m ln U), where U is the largest edge capacity.
• Friday, January 24, 2014: Slobodan Mitrović, Maximum s-t Flow in Time tilde{O}(m^(3/2)) via Interior Point Method
  (A semester project presentation.)
  Given a graph G on n vertices and m unit-capacity edges, I will present an algorithm that computes a maximum s-t flow, of value F, in G in time O(m^(3/2) ln m). The algorithm uses interior point method to obtain a fractional flow f* of value at least F - 1. By using fast rounding procedure for s-t flows over f*, we obtain an integral flow f of value at least F - 1. Finally, a maximum s-t flow is obtained by finding, if there is any, a single augmenting path in the residual network defined by f.
• Wednesday, December 4, 2013: Franka Tholen, Orienteering with Deadlines
  Given a graph with metric edge weights, a source node s and a deadline for every other vertex, the task is to find a path from s that visits as many vertices as possible before their deadline.
  We present the O(log n)-approximation from the paper Approximation algorithms for deadline-TSP and vehicle routing with time-windows by Bansal et al. (STOC'04).
• Monday, December 2, 2013: Alfonso Cevallos, A General Primal-dual Approximation Technique for Constrained Forest Problems
  I will present the famous and elegant primal-dual technique by Goemans and Williamson ('95). It gives a 2- (or better) approximation for a large set of problems where the solution is a forest on a graph, including shortest s-t path, min spanning tree, min T-join, Steiner tree and Steiner forest.
• Friday, November 29, 2013: Ashkan Norouzi, Ashkan speaks on Set Cover via Exponential Clocks
  Set cover problem is famous NP-complete problem and there exist many different approximation factor for it.
  In this presentation we are going to use "Competing Exponential Clocks" in this problem. By competing exponential clocks we mean competing independent exponential random variables. An exponential clock wins a competition if it has the smallest value among all participating exponential clocks.
• Tuesday, November 26, 2013: Christos Kalaitzis, A Constant Approximation Algorithm for the A Priori Traveling Salesman Problem
  Based on paper A constant approximation algorithm for the a priori traveling salesman problem by David Shmoys, and Kunal Talwar.
• Wednesday, November 13, 2013: Alfonso Cevallos, A 3-approximation Algorithm for the Orienteering Problem
  In the Orienteering problem, given a graph with edge lengths and vertex profits, a source-sink pair s,t, and a number D, we look for an s-t walk of distance at most D that maximizes the profit sum of the visited vertices. I will present the results by Blum et al. and Bansal et al., which derive this approximation algorithm from an approximation algorithm for the k-Stroll problem. The latter is the dual problem: given an instance as before, we look for an s-t walk of minimum distance that collects at least a certain amount of profit.
• Friday, November 8, 2013: Chidambaram Annamalai, Constant Factor Approximation Algorithm for the Santa Claus Problem
  From the work of Bansal & Sviridenko, Feige and Haeuptler et al. we know that there exists a constant factor approximation algorithm for the restricted max min fair allocation problem (Santa Claus). I will present this algorithm during the reading seminar.
• Thursday, October 31, 2013: Abbas Bazzi, (1-1/e + epsilon)-approximation for the Generalized Assignment Problem
  Based on paper Approximation algorithms for allocation problems: Improving the factor of (1 − 1/e) by Uriel Feige and Jan Vondrak.
• Thursday, October 17, 2013: Slobodan Mitrović, Graph Partitioning using Single Commodity Flows
  Based on paper Graph Partitioning using Single Commodity Flows by Rohit Khandekar, Satish Rao and Umesh Vazirani.
• Tuesday, September 24, 2013: Christos Kalaitzis, Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
  (based on paper Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation, by Lukas Polacek and Ola Svensson)
  The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. proved that a certain configuration LP can be used to estimate the optimal value within a factor ${1}/{(4+epsilon)}$, for any $epsilon>0$, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee.
  A natural question that arises from their work is if the difference between these guarantees is inherent or because of a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of Asadpour et al. and provide a novel analysis that lets us significantly improve the bound on its running time: from $2^{O(n)}$ to $n^{O(log n)}$. Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.
• Wednesday, August 14, 2013: Adrian Bock, O(1)-apx for the Schoolbus Problem
  I will present a recent result by Friggstad & Swamy that shows a constant-factor approximation algorithm for the Schoolbus problem in general graphs.
  Prior to this result, only logarithmic approximation algorithms were known.
• Monday, August 5, 2013: Filip Morić, Drawing Outerplanar Graphs
  We will talk about a recent paper by Noga Alon and Ohad N. Feldheim in which they prove that for any outerplanar graph G there is a one to one mapping of the vertices of G to the plane, so that the number of distinct distances between pairs of connected vertices is at most three. The proof combines geometric, combinatorial, algebraic and probabilistic arguments.
• Friday, August 2, 2013: Bartosz Walczak, Coloring Geometric Intersection Graphs
  I will discuss the problems of bounding the chromatic number of graphs arising from geometry as intersection graphs of geometric objects of various kinds, like axis-aligned rectangles, discs, segments, curves etc. Typical questions for a particular class of geometric intersection graphs are:
  * Is the chromatic number bounded by some function of the clique number?
  * If not, what is the asymptotics of the chromatic number with respect to the number of vertices, considering the clique number to be a fixed parameter?
  
  I will present several coloring algorithms and tricks which combined appropriately yield most known upper bounds. I will also present a construction of triangle-free geometric intersection graphs with chromatic number Theta(log log n) and discuss some evidence of its asymptotical optimality.
• Tuesday, July 30, 2013: Slobodan Mitrović, An Almost-nearly-linear Time Algorithm for Approximate s-t Max Flows
  (based on paper http://arxiv.org/abs/1304.2338, by Jonathan A. Kelner, Lorenzo Orecchia, Yin Tat Lee, and Aaron Sidford)
  I will present the main idea, from the paper, on getting an eps-approximate s-t max-flow in time O(m^{1 + o(1)} eps^{-2} log^c m), for some constant c. Also, I will briefly mention what is the main idea for constructing flow sparsifiers.
• Friday, July 26, 2013: Zlatko Joveski, Median of Three Permutations
  Given a set of permutations pi_1, pi_2, ..., pi_k, and a distance measure between permutations, the
  median problem is to find a permutation that is "closest" to these k permutations. In this talk
  we will consider the median problem under the Kendall-tau distance which counts the number of
  pairwise disagreements between permutations. It has been shown that the problem is NP-hard for
  k = 2m, m >= 2; while the case k = 2 is polynomial-time solvable. We will focus our attention on
  the case k = 3 which remains open. We will discuss the relation between finding a median of three
  permutations and finding the minimum feedback arc set of a tournament graph. In addition we
  will present some heuristic algorithms and discuss the possibility of obtaining an exact algorithm
  for the median problem on three permutations.
• Friday, July 26, 2013: Guru Prashanth, Some Notes on the TSP Path Problem
  The TSP problem is a fundamental problem in the field of algorithms, combinatorics and optimization. An equally interesting variant is the TSP path problem, which has been the subject of a lot of recent attention. In this talk, we will give an overview of the topic and present Gao's LP-based 3/2 approximation ratio for the graphic metric case. We will also show that this approach fails for the general metric case. Furthermore we will demonstrate that the "Best of Christofides' Algorithm" proposed by An et al, achieves a 3/2 approximation for half-integral cases.
  This talk will be self-contained and no prior knowledge is necessary.
• Wednesday, July 24, 2013: Hyung-Chan An, Centrality of Trees for Capacitated k-Center
  There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This is perhaps best illustrated by the classical k-center problem: there is a simple tight 2-approximation algorithm for the uncapacitated version whereas the first constant factor approximation algorithm for the general version with capacities were only recently obtained by using an intricate rounding algorithm that achieves an approximation guarantee in the hundreds.
  
  Our paper aims to bridge this discrepancy. For the capacitated k-center problem, we give a simple algorithm with a clean analysis that allows us to prove an approximation guarantee of 9. It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either 7, 8, or 9. The algorithm proceeds by first reducing to special tree instances, and then solves such instances optimally. Our concept of tree instances is quite versatile, and applies to natural variants of the capacitated k-center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are uniform.
  
  Based on joint work with Aditya Bhaskara & Ola Svensson, and an independent work of Chandra Chekuri, Shalmoli Gupta & Vivek Madan.
• Friday, July 19, 2013: Aleksander Mądry, (Electrical) Flows, Matchings, and the Central Path -- continued
  I will sketch how one can use electrical flow computations to solve (maximum-cardinality) bipartite matching problem. This will involve employing a primal-dual approach that draws on the ideas underlying path-following interior-point methods.
• Wednesday, July 17, 2013: Andres Ruiz Vargas, Empty Monochromatic Triangles
  Given a set X of n points in the plane (in general position) such that each point is either coloured red or blue. We say that a triplet {a,b,c} of points from X forms an empty triangle if there is no point in the interior of its convex hull. We say that it is monochromatic, if either all of its points are red, or alternatively, blue. At least how many empty monochromatic triangles can we find for any such point set X?
  
  We will show that we can always find at least $Omega(n^{4/3})$ empty monochromatic triangles, and that there are examples where there are at most $Omega n^2$ empty triangles.
• Tuesday, July 16, 2013: Aleksander Mądry, (Electrical) Flows, Matchings, and the Central Path
  I will sketch how one can use electrical flow computations to solve (maximum-cardinality) bipartite matching problem. This will involve employing a primal-dual approach that draws on the ideas underlying path-following interior-point methods.
• Thursday, July 11, 2013: Vijay Vazirani (Georgia Tech), Dichotomies in Equilibrium Computation: Markets Provide a Surprise
  Natural equilibrium computation problems tend to exhibit striking dichotomies, e.g., there is a qualitative difference between 2-Nash and k-Nash for k > 2. For market equilibria, all indications were that the dichotomy was separable vs non-separable utilities and separable vs non-separable production.
  
  We obtain an improved dichotomy by defining a new class of utility functions, called Leontief-free utilities, which play a complementary role to the classical Leontief utility functions -- whereas the latter are applicable when goods are complements, the former are applicable when goods are substitutes.
  
  We were led to this definition from the high vantage point provided by an algorithmic approach -- the powerful machinery of LCP formulations and Lemke's complementary pivot algorithm.
• Thursday, July 4, 2013: Chidambaram Annamalai, Single Source Unsplittable Graph Flows
  Based on paper On the Single-Source Unsplittable Flow Problem, by Yefim Dinitz, Naveen Garg, and Michel X. Goemans.
• Monday, July 1, 2013: Yuri Faenza (EPFL) and David Steurer (Cornell), Lectures on Extended Formulations
  Topics to be covered.
  
  Yuri:
  What is an EF
  slack matrices, factorization of slack matrices
  Yannakakis' theorem
  extended formulations from deterministic protocols, with an example
  extended formulations from randomized protocols, with an example
  
  David:
  Sherali-Adams Hierarchy is the best LP for CSPs (joint work with Siu on Chan, James Lee, and Prasad Raghavendra)
  simpler proof of the disjointness lower bound
• Thursday, June 27, 2013: Christos Kalaitzis, The Multiway Cut Problem via Exponential Clocks
  Based on "Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem", by N. Buchbinder, J. Naor, and R. Schwartz (http://research.microsoft.com/en-us/um/people/roysch/Papers/MC-BNS13.pdf).
• Thursday, June 20, 2013: Abdallah Elguindy, Pseudorandom Generators for Space-bounded Computation
  Based on paper "Pseudorandom Generators for Space-bounded Computation", by Noam Nisan (http://link.springer.com/article/10.1007/BF01305237).
• Wednesday, June 19, 2013: Friedrich Eisenbrand, Approximate Counting by Dynamic Programming
  Based on paper "Approximate Counting by Dynamic Programming" by Martin Dyer, STOC 2003, (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.8163).
• Tuesday, May 21, 2013: Slobodan Mitrović, Nearly Linear Time Max-flows
  Based on paper "Nearly Maximum Flows in Nearly Linear Time", by Jonah Sherman (http://arxiv.org/abs/1304.2077).
• Thursday, May 16, 2013: Aditya Bhaskara, Algorithms for Unique Games/Sparsest Cut Using Lasserre
  Based on paper "Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives", by Venkatesan Guruswami, Ali Kemal Sinop (http://arxiv.org/abs/1104.4746).
• Wednesday, May 8, 2013: Farah Charab, Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
  The presentation is based on paper "Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap" by Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan (http://arxiv.org/abs/1301.5584).
• Friday, May 3, 2013: Slobodan Mitrović, Solving Laplacian Linear Systems in Nearly-linear Time (II)
  The presentation is based on paper "A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time", by Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu (http://arxiv.org/abs/1301.6628).
• Thursday, May 2, 2013: Chidambaram Annamalai, Lasserre Hierarchy and the Decomposition Lemma
  Based on paper "Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack", by Anna R. Karlin, Claire Mathieu, and C. Thach Nguyen.
• Wednesday, April 10, 2013: Farah Charab, Graph Sketching
  The presentation is based on paper "Analyzing Graph Structure via Linear Measurements", by Kook Jin Ahn, Sudipto Guha, Andrew McGregor.
• Tuesday, March 26, 2013: Slobodan Mitrović, Solving Laplacian Linear Systems in Nearly-linear Time
  Based on paper "Approaching optimality for solving SDD systems", by Ioannis Koutis, Gary L. Miller, Richard Peng (http://arxiv.org/abs/1003.2958).
• Thursday, March 21, 2013: Christos Kalaitzis, Approximating Max-Cut on Low Threshold-Rank Graphs
  Based on "Rounding Semidefinite Programming Hierarchies via Global Correlation", by Boaz Barak, Prasad Raghavendra, David Steurer (http://arxiv.org/abs/1104.4680v1).
• Wednesday, March 20, 2013: Farah Charab, Time-space Tradeoffs for s-t Connectivity
  Based on paper "Faster Walks in Graphs: A tilde O(n^2) Time-Space Trade-off for Undirected s-t Connectivity", by Adrian Kosowski (http://arxiv.org/abs/1204.1136).
• Friday, March 15, 2013: Alfonso Cevallos, Characterization of Graphs where any Two Odd Cycles Intersect
  Based on paper "A Simpler Proof for The Two Disjoint Odd Cycles Theorem", by Ken-ichi Kawarabayashi and Kenta Ozeki.
• Wednesday, March 13, 2013: Slobodan Mitrović, Graph Sparsification
  Based on paper "Graph Sparsification by Effective Resistances", by Daniel A. Spielman, Nikhil Srivastava (http://arxiv.org/abs/0803.0929).
• Wednesday, March 6, 2013: Carsten Moldenhauer, Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems
  Based on paper "Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems", by Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala.
• Thursday, February 28, 2013: Slobodan Mitrović, Electrical flows and the Maximum Flow Problem
  The presentation is based on the first 3 sections of paper "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs", by Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng.
• Tuesday, February 5, 2013: Christos Kalaitzis, The Use of Hierarchies in Allocation Problems
  Semester project presentation by Christos.