Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
    informatyka analityczna  
UJ coat of arms
Theoretical Computer Science
at Jagiellonian
Combinatorial Optimization Seminar
Wednesday: 12:20 - 14:00, room 0106
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 na nowej stronie TCS.
table edited by: Bartłomiej Bosek
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.  
  • 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.  
  • 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.  
  • 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.  
  • 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.  
  • Dimitris Achlioptas, Fotis Iliopoulos, Random Walks that Find Perfect Objects and the Lovasz Local Lemma, FOCS 2014
  • 25.11.2014,
    Jakub Brzeski
    Markov Chains and Random Walks on Graphs
  • 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.  
  • 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.  
  • 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).  
  • R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66 (2013), no. 1, 87–92.
  • 14.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.  
  • 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.
      webmaster: email = a@b, a=www-tcs,