Organizatorzy

dr hab. Marcin Pilipczuk, prof. UW

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

23 maja 2019 12:15
Piotr Skowron (University of Warsaw)
Fairness and Public Goods: the Case of Multiwinner Rules
An instance of a multiwinner election consists of a set of alternatives, a population of voters---each voter approves a subset of alternatives, and the desired committee size k; the goal is to select a committee …
21 lutego 2019 12:15
Laszlo Kozma (Freie Universität Berlin)
Selection from heaps, row-sorted matrices, and X+Y, using soft heaps
We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item from a heap-ordered tree, from a collection of sorted lists, and from X+Y. Our results match, and in some ways extend classical results …
24 stycznia 2019 12:15
Karolina Okrasa (Politechnika Warszawska)
Subexponential algorithms for locally constrained homomorphism problems in string graphs
We consider the complexity of finding weighted homomorphisms from string graphs with n vertices to a fixed graph H. We show that there exists an algorithm solving this problem in subexponential time, if H has no two vertices …
17 stycznia 2019 12:15
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 …
29 listopada 2018 12:15
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 …
25 października 2018 12:15
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 …
11 października 2018 12:15
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) …
19 lipca 2018 12:15
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 …
11 czerwca 2018 12:15
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 …
19 kwietnia 2018 12:15
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 …
5 kwietnia 2018 12:15
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, …
15 marca 2018 12:15
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, …
8 marca 2018 12:15
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 …
1 marca 2018 12:15
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. …
8 lutego 2018 12:15
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 …