Seminar Algorithms

Organizers

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

Information

Home page

Research fields

• Algorithmics

List of talks

• Nov. 8, 2024, 2:15 p.m.
  Anita Dürr (Max Planck Institute for Informatics)
  Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
  We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time ˜O(n + t√pmax), where n is the number of items, t is the knapsack capacity, and pmax is the maximum item profit. …

  ---

• Oct. 25, 2024, 2:15 p.m.
  Maël Dumas
  On graphs coverable by k shortest paths
  We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single exponential function of k. As …

  ---

• Oct. 18, 2024, 2:15 p.m.
  Konrad Majewski
  Parameterized Dynamic Data Structure for Split Completion
  We design a randomized data structure that, for a fully dynamic graph G updated by edge insertions and deletions and integers k, d fixed upon initialization, maintains the answer to the Split Completion problem: whether …

  ---

• April 29, 2021, 12:15 p.m.
  Jana Cslovjecsek (EPFL)
  Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
  We consider n-fold integer programming problems and their generalizations. These are integer linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent sub-problems after deleting a small number …

  ---

• April 15, 2021, 12:15 p.m.
  Tomáš Masařík (Simon Fraser University)
  Flexible List Colorings in Graphs with Special Degeneracy Conditions
  For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is …

  ---

• April 1, 2021, 12:15 p.m.
  Michał Pilipczuk
  Reducing randomness in Isolation Lemma on decomposable graphs
  The classic Isolation Lemma of Mulmuley et al. states that if F is a non-empty family of subsets of a universe U of size n, and we draw a weight function f : U -> …

  ---

• March 18, 2021, 12:15 p.m.
  Anna Zych-Pawlewicz
  Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
  We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case …

  ---

• March 4, 2021, 12:15 p.m.
  Łukasz Bożyk
  Vertex deletion into bipartite permutation graphs
  A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines, one on each. A bipartite permutation graph is a permutation graph which is bipartite. We study …

  ---

• Jan. 21, 2021, 12:15 p.m.
  Karol Węgrzycki (MPI Saarbrucken)
  Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
  We present an O^*(2^{0.5 n}) time and O^*(2^{0.249999n}) space randomized algorithm for Subset Sum. This is the first improvement over the long-standing O^*(2^{n/2}) time and O^*(2^{n /4}) space algorithm due to Schroeppel and Shamir. This …

  ---

• Jan. 7, 2021, 12:15 p.m.
  Michał Włodarczyk (Eindhoven University of Technology)
  Parameterized Inapproximability for Steiner Orientation by Gap Amplification
  In the k\textnormal{-}\textsc{Steiner Orientation} problem, we are given a mixed graph, that is, with both directed and undirected edges, and a set of k terminal pairs. The goal is to find an orientation of the …

  ---

• Dec. 17, 2020, 12:15 p.m.
  Juliusz Straszyński
  Efficient Computation of 2-Covers of a String
  Quasiperiodicity is a generalization of periodicity that has been researched for almost 30 years. The notion of cover is the classic variant of quasiperiodicity. A cover of a text T is a string whose occurrences …

  ---

• Dec. 3, 2020, 12:15 p.m.
  Adam Karczmarz (UW)
  A Deterministic Parallel APSP Algorithm and its Applications
  In this talk we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has $\tilde{O}(nm+(n/d)3)$ work and $\tilde{O}(d)$ depth for any depth parameter $d\in [1,n]$. To the best of our …

  ---

• Nov. 19, 2020, 12:15 p.m.
  Céline M. F. Swennenhuis (Eindhoven University of Technology)
  A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
  In the Bin Packing problem one is given n items with different weights and m bins with a given capacity; the goal is to distribute the items over the bins without exceeding the capacity. Björklund, …

  ---

• Nov. 5, 2020, 12:15 p.m.
  Wojciech Nadara
  Approximating pathwidth for graphs of small treewidth
  We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. Our approach builds on the following key insight: every graph …

  ---

• Oct. 22, 2020, 12:15 p.m.
  Marcin Pilipczuk
  Quasi-polynomial-time algorithm for Independent Set in P_t-free and C_{>t}-free graphs via shrinking the space of connecting subgraphs
  In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in P_t-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm …

  ---