Optymalizacja Kombinatoryczna

Czwartek 16:15-17:45, sala 0086

Jest to seminarium magisterskie, którego tematyka dotyczy optymalizacji kombinatorycznej. W szczególności interesują nas następujące tematy:

  1.   Zaawansowane algorytmy znajdujące skojarzenia w grafach (także dwudzielnych) w przypadkach nieważonych i ważonych krawędzi.

  2.   Problemy konstruowania on-line skojarzeń w grafach dwudzielnych, AdWords Problem - rozwiązania optymalne, randomizowane.

  3.   Algorytmiczne aspekty pokrycia uniłańcuchami produktów częściowych porządków.

Strona seminarium z aktualna listą prac do zreferowania znajduje się tutaj.

Strona seminarium na UsosWeb znajduje się tutaj.

27.04.2017 16:15
Jakub Szarawski
A greedy approach to the Turtle Tower problem
In the Turtle Tower problem we are given n turtles with a mass and capacity for each of them. We are looking for the highest tower possible, regarding that capacity of every turtle in the tower cannot be exeeded by the sum of the masses of turles it carry. Presented solution is faster than commonly known dynamic one.
04.05.2017 16:15
Grzegorz Bukowiec
Even factors of graphs
11.05.2017 16:15
Anna Kobak
Lambda number for the direct product of some family of graphs
18.05.2017 16:15
Katrzyna Janocha
Proper Orientations of Planar Bipartite Graphs

Poprzednie referaty

20.04.2017 16:15
Helena Borak, Zygmunt Łenyk
Necklaces, Convolutions, and X + Y, A new upper bound for the online square packing
Necklaces, Convolutions, and X + Y

The necklace alignment problem is to find the optimal rotation of the necklaces to best align the beads, when we have two necklaces given, each with n beads at arbitrary positions. Alignment is measured according to the ℓ_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = ∞ and how these problems can be reduced to convolution problems which can be solve in subquadratic time. Besides, we say how the necklace alignment problems, and their corresponding convolution problems, are also intrinsically connected to problems on X + Y matrices.

A new upper bound for the online square packing

In online square packing problem we try to minimise the height of squares on a plane with width 1. Squares come one by one, they can’t overlap and once set, it’s position can’t be changed. A new upper bound (ratio between algorithm result and optimal packing) is found by applying modified version of previously used First Fit Shelf algorithm.
06.04.2017 16:15
Andrzej Głuszyński, Jakub Nowak
Local Antimagic Vertex Coloring of a Graph, A short proof of Cayley's tree formula
Local Antimagic Vertex Coloring of a Graph

The edge labelling is called 'local antimagic', if for all vertices sum of labels for incident edges is different for every two adjacent vertices. Such sum induce a correct vertex colouring. The local antimagic chromatic number - X_la(G) - is the minimum number of colours used by any proper local antimagic labelling. In the paper authors present results on this parameter for trees, friendship, wheel and clique graphs.


A short proof of Cayley's tree formula

Cayley’s tree formula is a very elegant result in Graph Theory. The problem is to find the number of all possible trees on a given set of labeled vertices. For n = 2 and vertex set {v1, v2}, we have only one tree. For n = 3 and vertex set {v1, v2, v3}, we have 3 different trees. Similarly for n = 4, we have 16 trees. We give a short proof of Cayley’s tree formula for counting the number of different labeled trees on n vertices.

Alok Bhushan Shukla, A short proof of Cayley's tree formula.
23.03.2017 16:15
Aleksandra Mędrek, Marcin Muszalski
Planning for Fast Connectivity Updates
Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d > 1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens. We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d polylg n) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.
  1. Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007
16.03.2017 16:15
Patryk Urbański
Generating Linear Extensions Fast

One of the most important sets associated with a poset P is its set of linear extensions, E(P). In this paper, we present an algorithm to generate all of the linear extensions of a poset in constant amortized time; that is, in time O(e(P)), where e(P) = |E(P)|. The fastest previously known algorithm for generating the linear extensions of a poset runs in time O(n*e(P)), where n is the number of elements of the poset. Our algorithm is the first constant amortized time algorithm for generating a ``naturally defined'' class of combinatorial objects for which the corresponding counting problem is #P-complete. Furthermore, we show that linear extensions can be generated in constant amortized time where each extension differs from its predecessor by one or two adjacent transpositions. The algorithm is practical and can be modified to efficiently count linear extensions, and to compute P(x < y), for all pairs x,y, in time O(n^2 + e(P)).

Gara Pruesse, Frank Ruskey. Generating Linear Extensions Fast. SIAM J. Comput. Vol. 23, No. 2 (1994), pp. 373-386.

09.03.2017 16:15
Grzegorz Matecki
Boolean dimension of posets
A boolean dimension bdim(P) of a poset P=(X,<) is a smallest number k for which there is a set l1, l2, ..., lk of labelings X:->N and a boolean formula f(a1, ..., ak) such that the following is true: x < y in P iff f(a1, .., a_k) = 1 where ai =1 iff li(x) < li(x).
Generally, it is simple to observe that bdim(P) <= dim(P). Also, it is known that there is a constant c such that bdim(n) <= c log(n) for any poset P of size n.
The are few interesting open problems for boolean dimension:
1) Is boolean dimension of the boolean lattice of size n less that n?
2) Is there a constant c such that bdim(P) < c for any planar poset P?
 
09.03.2017 16:15
Mateusz Twaróg, Łukasz Majcher
Combinatorial library core
Presentation and discussion on core functionalities of the c++ combinatorial library. introduction to classes representing graphs, graph traversing algorithm templates and simple GUI.
26.01.2017 16:15
Wojciech Kruk, Maciej Woźniak
A few open problems
We mentioned the following open problems in graph theory and discrepancy theory:

1. Erdos discrepancy problem
2. Hoang - Reed conjecture
3. Seagull problem - a consequence of Hadwiger's conjecture
19.01.2017
Paweł Petecki
Akademia Górniczo-Hutnicza
Symmetry breaking polynomial
Let G be a graph, and let Γ= Aut G. A coloring c of G is symmetry-breaking if for every non-identity automorphism φ in Γ, there is some vertex v of G such that c(v)≠c(φ(v)). There has been a lot of work on the minimum number of colors in a symmetry-breaking coloring of G. We discuss here a different problem: counting the number of k-colorings that are symmetry breaking. The tool, as is frequently the case for problems such as this one, is Möbius inversion. To solve this problem we define symmetry breaking polynomial ψG. For positive integer k (number of colors), ψG(k) is the number of k-colorings that break all non-trivial symmetries of the graph G.
22.12.2016 16:15
Łukasz Majcher, Jan Szczepaniec
Convex p-partitions of bipartite graphs
A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p ≥ 1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
15.12.2016
Anna Kobak
Open problems in graph theory concerning minors.
We mentioned following open problems in graph theory:
  1. Hadwiger's Conjecture
  2. Seagull Conjecture
  3. Jorgensen's Conjecture
  4. Unfriendly partitions
  5. and a few more conjectures concerning minors.
08.12.2016
Zygmunt Łenyk
Rendezvous on the line.
This is one of a handful of rendezvous problems where two players must find one another in a certain structured domain. In line case, players are placed on the line with distance 2, without knowing neither on which side is their partner, nor the direction of the line. I'll concentrate on the symmetric case where players must follow a specific (but maybe mixed) strategy. The conjecture is that best expected time of meeting two players equals 4.25.
  1.  
  2.  
  3. www.openproblemgarden.org/op/rendezvous_on_a_line
  4. Improved bounds for the symmetric rendezvous value on the line. Qiaoming Han, Donglei Du, Juan Vera, Luis F. Zuluaga. SODA 2007
01.12.2016
Patryk Urbański
Coloring Ordinary Maps, Maps of Empires and Maps of the Moon
A short review of generalized map coloring problems:
  • Heawood's empire coloring problem in the plane - 6M colors are sufficient to color a map of empires each consisting of at most M connected regions.
  • Earth-Moon map coloring Mathematics Magazine Vol. 66, No. 4 (Oct., 1993), pp. 211-226problem - it is known that the chromatic number of thickness-2 graphs is between 9 and 12. It is an open problem to find the exact value.
Coloring Ordinary Maps, Maps of Emipres, and Maps of the Moon. Joan P. Hutchinson. Mathematics Magazine. Vol. 66, No. 4 (Oct., 1993), pp. 211-226.
24.11.2016
Wojciech Łopata
Several open problems from game theory, graph theory and combinatorics.

I'll briefly introduce the audience to two unrelated areas: book embedding and mechanism design, and walk through some open problems in those areas.
Wikipedia: Book embedding
Wikipedia: Mechanism design

17.11.2016
Paweł Kubiak
Succinct Data Structures
10.11.2016
Grzegorz Bukowiec
On more variants of the Majority Problem
03.11.2016
Gabriel Jakóbczak
Proper orientations of some types of graphs
Let G be a simple graph. We say that orientation of graph G is proper if for every pair of adjacent veritces u and v their indegrees are different. It was proved by Mieczysław Borowiecki, Jarosław Grytczuk and Monika Pilśniak that for every simple graph exists its proper orientation. Now we can define the proper orientation number of graph G as the minimum of the maximum indegree, taken over all proper orientations of G. We show that for some classes of bipartite graphs their proper orientation number is less than or equal to 6. We also show that this parameter is at most 4 for graphs which are trees and proof of that fact leads to a polynomial-time algorithm of finding proper orientation of such graphs.

Fiachra Knox, Sebastián González Hermosillo de la Maza, Bojan Mohar, and Cláudia Linhares Sales. 
Proper Orientations of Planar Bipartite Graphs. 
pages 2-6, sep 2016.
27.10.2016
Magdalena Gargas
The geometry of nesting problems: A tutorial
20.10.2016
Helena Borak
Exact algorithms for the two-dimensional strip packing problem with and without rotations
We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90 degree rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.
13.10.2016
Krzysztof Barański
Level-Oriented Two-Dimensional Packing Algorithms
The paper includes an overview of several algorithms, their complexities and approximation ratios solving two-dimensional strip packing problem:
1) First-Fit Decreasing Height (FFDH) - time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof]
2) Next-Fit Decreasing Height (NFDH) - time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof]
3) Best-Fit Decreasing Height (BFDH), Bottom-Left (BL), Steinberg's algorithm, Split-Fit (SF)
06.10.2016
Bartłomiej Bosek
A new variant of the game of cops and robber

The talk presents a joint work of Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak. We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v1,v2,…,vk} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector Du(B)=(d1,d2,…,dk) whose components di=dG(u,vi), i=1,2,…,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localize him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤|V(G)| holds obviously.

27.01.2016
Michał Dyrek
The Linear Arboricity of Graphs
A linear forest is a forest in which each connected component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests whose union is the set of all edges of G. The linear arboricity conjecture asserts that for every simple graph G with maximum degree D, la(G) <= [(D+1)/2].
 
Although this conjecture received a considerable amount of attention, it has been proven only for D <= 6, D = 8, D = 10 and the best known general upper bound for la(G) is la(G) <= [3D/5] for even D and la(G) <= [(3D + 2)/5] for odd A. Here we prove that for every e > 0 there is a D_0 so that for every G with maximum degree D > D_0, la(G) <= (1/2 + e) * D. To do this, we first prove the conjecture for every G with an even maximum degree D and with girth g > 50*D.
 
20.01.2016
Pola Kyzioł
Matching in regular and almost regular graphs

I present an O(n^2*log n)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2*log n) time if the difference between the maximum degree and the minimum degree is less than r.

R. Yuster, Maximum matching in regular and almost regular graphs

13.01.2016
Piotr Bejda
Perfect matchings in O(n log n) time in regular bipartite graphs

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bi-partite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m*sqrt(n)). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost and Schirra). In a recent line of work by Goel, Kapralov and Khanna the O(m) time algorithm was improved first to O'(min(m, n^2.5/d)) and then to O'(min(m,n^2/d)). It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step.
In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, an d is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for any deterministic algorithm. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log2 n) time, with O(m) pre-processing time; this gives a simple O(m + mn log2 n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix.

A. Goel and M. Kapralov and S. Khanna, Perfect matchings in O n log n time in regular bipartite graphs

16.12.2015
Krzysztof Kleiner
Online Dual Edge Coloring of Paths and Trees

Extending the results presented on the preceding seminar, we study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. For paths, we consider k=2, and for trees, we consider any k>=2. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit.

L. M. Favrholdt, J. W. Mikkelsen, Online Dual Edge Coloring of Paths and Trees

09.12.2015
Mateusz Twaróg
On-Line Edge-Coloring with a Fixed Number of Colors

We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and 1/2 , and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than 4/7 -competitive. If the graphs are all k-colorable, any fair algorithm is at least 1/2 -competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large.

M. Favrholdt, N. Nielsen, On-Line Edge-Coloring with a Fixed Number of Colors, Algorithimca 35 (2), 176-191, 2003

02.12.2015
Helena Borak
Linear Extensions of N-free Orders

We consider the number of linear extensions of an N-free order P. We give upper and lower bounds on this number in terms of parameters of the corresponding arc diagram. We propose a dynamic programming algorithm to calculate the number. The algorithm is polynomial if a new parameter called activity is bounded by a constant. The activity can be bounded in terms of parameters of the arc diagram.

Stefan Felsner , Thibault Manneville, Linear Extensions of N-free Orders, Order 32 (2), 147-155, 2015

18.11.2015
Leszek Jakub Kania
Improved Bounds for Online Preemptive Matching

When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight.  The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms.

L. Epstein, A. Levin, D. Segev, O. Weimann, Online Preemptive Matching, arXiv 2012

04.11.2015
Jakub Cieśla
Computing Tree-Depth Faster Than 2^n

A connected graph has tree-depth at most k if it is a subgraph of the clusure of a rooted tree whose height is at most k. The autors give an algorithm which for a given n-vertex graph G, in time O(1.9602^n) computes the tree-depth of G. The algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain G.

F. V. Fomin, A. C. Giannopoulou, M. Pilipczuk, Computing Tree-Depth Faster Than 2^n, Algorithmica 73 (1), 202-216, 2015

28.10.2015
Karol Banyś
Fast Algorithm for Partial Covers in Words

In this article autors introduce a new notion of α-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least α positions in w. They develop a data structure of O(n) size (where n=|w|) that can be constructed in O(nlogn) time which they apply to compute all shortest α-partial covers for a given α. They also employ it for an O(nlogn)-time algorithm computing a shortest α-partial cover for each α=1,2,…,n.

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski , Wojciech Rytter, Tomasz Waleń, Fast Algorithm for Partial Covers in Words, Algorithmica 73 (1), 217-233, 2015

21.10.2015
Paweł Kubiak
Lower bounds for dynamic algorithms

In my presentation I will discus some elementary dynamic problems (Single source reachability and Dynamic diameter) and then I will present interesting reduction from this problems to Orthogonal Vectors Problems. These reductions imply that if it would be possible to solve SSR in O(m^(1-ε)) or do 1.3 approximation of DD in O(m^(2-ε)) then SETH will be refuted.

Amir Abboud, Popular Conjectures and Dynamic Problems, 2015

14.10.2015
Katarzyna Janocha
Conditional hardness and equivalences for graph problems

Some graph problems (such as such as APSP, negative triangle, distance product or radius) do not have any known solutions better then the naive ones. We show subquadraic and subcubic reductions between them, proving that in case of finding a faster algorithm for any of the problems would be equivalent of reducing the complexity of each of them. We separate algorithms for sparse and dense graphs and focus on basic methods for both classes.

V. Williams, Conditional hardness and equivalences for graph problems

07.10.2015
Zygmunt Łenyk
Hardness for Easy Problems (overview)

Introduction into a young branch of algorithmics. We discuss why we are stuck during developing fast algorithms to some well-known problems. Problems in P and suitable reductions form equivalence classes of problems, inside which improving asymptotic time of any of them would automatically improve the rest. At the bottom of these classes lie problems such as: 3SUM, all-pairs-shortest-paths, orthogonal vectors. Their complexities are guarded by strong conjectures which, if proven wrong, would revoke widely believed conjectures such as SETH.  

Amir Abboud, Arturs Backurs, Piotr Indyk and Virginia V. Williams, Hardness for easy problems - An introduction, 2015

20.01.2015
Maciej Poleski
An online version of Rota's basis conjecture
Rota's basis conjecture states that in any square array of vectors whose rows are bases of a fixed vector space the vectors can be rearranged within their rows in such a way that afterwards not only the rows are bases, but also the columns. We discuss an online version of this conjecture, in which the permutation used for rearranging the vectors in a given row must be determined without knowledge of the vectors further down the array. The paper contains surprises both for those who believe this online basis conjecture at first glance, and for those who disbelieve it.  
References:
Guus P. Bollen, Jan Draisma, An online version of Rota's basis conjecture, Journal of Algebraic Combinatorics, October 2014
13.01.2015
Helena Borak
Variants of Hat Guessing Games
Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat they are wearing by looking at the colors of the hats worn by some of the other players. In this paper we consider several variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worst-case analysis of deterministic hat-guessing problems with a finite number of players.  
References:
S.Butler, M.T.Hajiaghayi, R.D.Kleinberg, T.Leighton, Hat Guessing Games
16.12.2014
Marcin Dziaduś
Five-list-coloring of planar graphs
Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that |L(u)|=|L(v)|=2, L(x) has at least three elements for every vertex x of C \ {u,v} and L(x) has at least five elements for every vertex x of G \ V(C). We prove a conjecture of Hutchinson that G has a proper coloring f such that f(x) belongs to L(x) for every vertex x of G.  
References:
Luke Postle, Robin Thomas, Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs, Journal of Combinatorial Theory, Series B
09.12.2014
Karol Banyś
Online Load Balancing and Correlated Randomness
This paper looks at online load balancing, in a setting where each job can only be served by a subset of the servers. The subsets are revealed only on arrival, and can be arbitrary. The cost of an allocation is the sum of cost for each server, which in turn is a convex increasing function of the number of jobs allocated to it. There are no departures.  
References:
S. Moharir, S. Sanghavi. Online Load Balancing and Correlated Randomness. 50th Annual Allerton Conference, 2012
U. Vazirani V. Vazirani A. Mehta, A. Saberi. Adwords and generalized on-line matching. Proceedings of FOCS, 2005
02.12.2014
Andrzej Dorobisz
Random Walks that Find Perfect Objects and the Lov´asz Local Lemma
We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lov´asz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints.  
References:
Dimitris Achlioptas, Fotis Iliopoulos, Random Walks that Find Perfect Objects and the Lovasz Local Lemma, FOCS 2014
25.11.2014
18.11.2014,Jakub Brzeski
Markov Chains and Random Walks on Graphs
 
References:
D. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph, 2014.
L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 353–397, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
04.11.2014
Jakub Cieśla
Finding All Maximally-Matchable Edges in a Bipartite Graph
We consider the problem of finding all maximally-matchable edges in a bipartite graph G = (V, E), i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time O(n + m) (where n = |V| and m = |E|). Hence, the time complexity of finding all maximally-matchable edges reduces to that of finding a single maximum matching.  
References:
T. Tassa, Finding all maximally-matchable edges in a bipartite graph, Theoret. Comput. Sci. 423 (2012), 50–58.
28.10.2014
Marcin Ziemiński
Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an (nd) lower bound for any deterministic algorithm.  
References:
A. Goel, M. Kapralov, S. Khanna, Perfect matchings in O(n log n) time in regular bipartite graphs, Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC'10), 39–46, ACM, New Yo
21.10.2014
Patryk Mikos
Maximum Matching in Regular and Almost Regular Graphs
An O(n^2*log(n))-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2 log n) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in O(√nm)-time for graphs with m edges, whenever m = ω(rn1.5 log n).  
References:
R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66 (2013), no. 1, 87–92.
14.10.2014
07.10.2014,Bartłomiej Bosek
Incremental algorithm on bipartite graphs
The talk presents the jont work of Bartłomiej Bosek, Darek Leniowski, Piotr Sankowski, and Anna Zych. We investigated the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation.  
References:
Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych. Online bipartite matching in offline time. In Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS14, pp. 384-393, 2014.