Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. ucz.

Information

Home page

List of talks

• Jan. 17, 2019, 12:15 p.m.
  Adrian Vladu (Boston University)
  Discrepancy and Optimization
  We consider the problem of minimizing the discrepancy of a set system. In 1985, Spencer proved that for m sets over a universe of n elements, one can always achieve a coloring with discrepancy O(sqrt(n …

  ---

• Nov. 29, 2018, 12:15 p.m.
  Krszysztof Fleszar (Univerisity of Warsaw)
  A PTAS for TSP with hyperplane neighborhoods
  A PTAS for TSP with hyperplane neighborhoods In TSP with neighborhoods, we are asked for a shortest tour visiting a given set of regions (i.e., neighborhoods). When the neighborhoods are lines in 2D, the problem …

  ---

• Oct. 25, 2018, 12:15 p.m.
  Stéphan Thomassé (ENS Lyon)
  EPTAS for Max Clique on Disks and Unit Balls
  We propose a polynomial-time algorithm which takes as input a finite set of points of R3 and computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the …

  ---

• Oct. 11, 2018, 12:15 p.m.
  Paweł Rzążewski (MIMI PW)
  Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization
  In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v\in V(G). The task is to find a homomorphism \phi:V(G)\to V(H) …

  ---

• July 19, 2018, 12:15 p.m.
  Jan van der Brand (KTH)
  Improved Algorithms for Dynamic Matrix Inverse
  The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems, such as maintaining the …

  ---

• June 11, 2018, 12:15 p.m.
  Krzysztof Kiljan, Wojciech Nadara, Michał Ziobro
  Three talks from Symposium on Experimental Algorithms (SEA'18)
  Krzysztof Kiljan, Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set   Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes …

  ---

• April 19, 2018, 12:15 p.m.
  Laszlo Kozma (TU Eindhoven)
  Trees and heaps: the many faces of basic data structures
  Binary search trees (BSTs) and heaps are the canonical comparison-based implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about …

  ---

• April 5, 2018, 12:15 p.m.
  Wiktor Zuba (MIMUW)
  Hamilitonian cycles of middle-levels subgraphs of hypercubes
  The n-dimension hypercube graph is the graph with vertices represented by sequences of n bits, with edges connecting those vertices, which representations differ at exactly one position. We can divide the graph into (n+1) levels, …

  ---

• March 15, 2018, 12:15 p.m.
  Marthe Bonamy (LaBRI, CNRS, Universite de Bordeaux)
  Distributed coloring in sparse graphs with fewer colors
  Distributed coloring in sparse graphs with fewer colors Abstract : We are concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, …

  ---

• March 8, 2018, 12:15 p.m.
  Magnus Wahlström (University of London)
  Fine-grained structure of NP-hard SAT problems
  Say that a problem SAT(\Gamma), for a constraint language \Gamma, admits an improved algorithm if it can be solved in O(c^n) time on n variables for some c<2, and that it is hard otherwise. Many …

  ---

• March 1, 2018, 12:15 p.m.
  Marc Heinrich (LIRIS )
  Online graph coloring with bichromatic exchanges
  Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires $\Omega(\log n)$ colors in the worst case. …

  ---

• Feb. 8, 2018, 12:15 p.m.
  Lucas Pastor
  Disproving the normal graph conjecture
  A graph G is said to be normal if there exists two coverings, C and S of its vertex set such that, every member of C induces a clique, every member of S induces a …

  ---

• Dec. 7, 2017, 12:15 p.m.
  Marcin Pilipczuk (Uniwrsytet Warszawski)
  The Erdős-Hajnal conjecture for caterpillars and their complements
  The celebrated Erdos-Hajnal conjecture states that for every proper hereditary graph class GG there exists a constant eps>0 such that every graph G in GG contains a clique or an independent set of size |V(G)|^eps. …

  ---

• Nov. 23, 2017, 12:15 p.m.
  Irene Muz
  Half-integral linkages in highly connected directed graphs
  We study the half-integral k-Directed Disjoint Paths Problem (1/2 kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where k=2, and the input graph is L-strongly connected, for …

  ---

• Nov. 9, 2017, 12:15 p.m.
  Bart M. P. Jansen (Eindhoven University of Technology)
  Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
  We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-Deletion problem is the following: given …

  ---