EPFL Theory and Combinatorics Reading Group
Mailing list and calendar: There is a mailing list where the announcements of upcoming talks appear.To subscribe to this list, send an email (can be empty) to: theoryreadinggroupsubscribe@listes.epfl.ch .
There is also a calendar that you can subscribe to.
Upcoming Talks:
 No upcoming talks
Past Talks:

Friday, June 27, 2014:
Slobodan Mitrović,
Sketching Graph Cuts
Given an nvertex 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 (2epsilon) NPhardness for the "Concurrent Open Shop Problem", and (2epsilon) NPhardness 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 EdgeDisjointPaths
I will present the hardness of approximation result for the edgedisjointpaths 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 wellknown 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.18approximation 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 PrizeCollecting 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 CuttingPlanes?
(Based on the 2014 paper by Dey, Molinaro, and Wang How Good Are Sparse CuttingPlanes?)
Given a polyope P let P^k be its approximation obtained using all valid inequalities for P that have at most k nonzero coefficients ("ksparse cuts"). Let d(P;P^k) = max_{x in P^k} min_{yin P} x  y as a measure of the quality of ksparse 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 allpairs 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ć,
CutBased Hierarchical Decompositions of Graphs
(Based on paper Computing CutBased 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 edgedeletion question: given a graph G = (V, E), can we find a minimumcardinality stabilizer?
We show that this problem is vertexcover hard. We then prove that there is a minimumcardinality 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 Unionclosed Families of Sets
For a finite universe set U, a family of subsets F is unionclosed 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 FalgasRavry '11). These results and their proofs give us a better understanding of the structure of unionclosed families. 
Friday, March 7, 2014:
Abbas Bazzi,
Hastad 3bit 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 graphTSP(i.e. TSP on graph metrics) this approach results in a 1.461approximation algorithm, with respect to the HeldKarp 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 Constantfactor Approximation for Minimumcost knodeconnected Subgraphs
(Based on Approximating minimumcost knode connected subgraphs via independencefree graphs by Joseph Cheriyan, L�szl� A. V�gh, FOCS 2013.)
Given a knodeconnected graph with edge costs. The minimumcost knodeconnected subgraph problem asks for a spanning knodeconnected subgraph of minimum cost. I will present the 6approximation algorithm by Cheriyan and V�gh (for graphs with at least k^3(k1)+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 arbitrarycapacity edges, I will present an algorithm that computes a maximum st 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 st 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 unitcapacity edges, I will present an algorithm that computes a maximum st 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 st flows over f*, we obtain an integral flow f of value at least F  1. Finally, a maximum st 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 deadlineTSP and vehicle routing with timewindows by Bansal et al. (STOC'04). 
Monday, December 2, 2013:
Alfonso Cevallos,
A General Primaldual Approximation Technique for Constrained Forest Problems
I will present the famous and elegant primaldual 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 st path, min spanning tree, min Tjoin, Steiner tree and Steiner forest.

Friday, November 29, 2013:
Ashkan Norouzi,
Ashkan speaks on Set Cover via Exponential Clocks
Set cover problem is famous NPcomplete 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 3approximation Algorithm for the Orienteering Problem
In the Orienteering problem, given a graph with edge lengths and vertex profits, a sourcesink pair s,t, and a number D, we look for an st 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 kStroll problem. The latter is the dual problem: given an instance as before, we look for an st 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,
(11/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,
QuasiPolynomial Local Search for Restricted MaxMin Fair Allocation
(based on paper QuasiPolynomial Local Search for Restricted MaxMin Fair Allocation, by Lukas Polacek and Ola Svensson)
The restricted maxmin 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 quasipolynomial 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 constantfactor 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 axisaligned 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 trianglefree 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 Almostnearlylinear Time Algorithm for Approximate st 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 epsapproximate st maxflow 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 find a permutation that is "closest" to these k permutations. In this talk
we will consider the median problem under the Kendalltau distance which counts the number of
pairwise disagreements between permutations. It has been shown that the problem is NPhard for
k = 2m, m >= 2; while the case k = 2 is polynomialtime solvable. We will focus our attention on
the case k = 3 which remains open. We will discuss the relation between finding a median of three
permutations and finding 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 LPbased 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 halfintegral cases.
This talk will be selfcontained and no prior knowledge is necessary. 
Wednesday, July 24, 2013:
HyungChan An,
Centrality of Trees for Capacitated kCenter
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 kcenter problem: there is a simple tight 2approximation 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 kcenter 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 kcenter 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 nonzero 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 (maximumcardinality) bipartite matching problem. This will involve employing a primaldual approach that draws on the ideas underlying pathfollowing interiorpoint 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 (maximumcardinality) bipartite matching problem. This will involve employing a primaldual approach that draws on the ideas underlying pathfollowing interiorpoint 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 2Nash and kNash for k > 2. For market equilibria, all indications were that the dichotomy was separable vs nonseparable utilities and separable vs nonseparable production.
We obtain an improved dichotomy by defining a new class of utility functions, called Leontieffree 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 SingleSource 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:
SheraliAdams 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/enus/um/people/roysch/Papers/MCBNS13.pdf).

Thursday, June 20, 2013:
Abdallah Elguindy,
Pseudorandom Generators for Spacebounded Computation
Based on paper "Pseudorandom Generators for Spacebounded 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 Maxflows
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 Nearlylinear Time (II)
The presentation is based on paper "A Simple, Combinatorial Algorithm for Solving SDD Systems in NearlyLinear 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 Semidefinite 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 Nearlylinear 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 MaxCut on Low ThresholdRank 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,
Timespace Tradeoffs for st Connectivity
Based on paper "Faster Walks in Graphs: A tilde O(n^2) TimeSpace Tradeoff for Undirected st 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 Kenichi 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,
SemiDefinite Relaxations for Minimum Bandwidth and other VertexOrdering problems
Based on paper "SemiDefinite Relaxations for Minimum Bandwidth and other VertexOrdering 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, ShangHua Teng.

Tuesday, February 5, 2013:
Christos Kalaitzis,
The Use of Hierarchies in Allocation Problems
Semester project presentation by Christos.