6th workshop of the Center of Modern Computer Science
6. seminář Centra moderní informatiky
The sixth workshop of the Center of Modern Computer Science will take place on Friday December 19, 2014 in the Mala Strana building.
Centrum moderní informatiky zve na šestý seminář. Přednášky juniorů centra se konají v průběhu programu v pátek 19. 12. 2014 v budově MFF UK na Malé Straně.
| Morning lectures are in the room S1, 4th floor | |
| 10:45 | Pavel Surynek: Solving cooperative path-finding optimally by reducing it to propositional satisfiability |
| 11:15 | Martin Tancer: Van Kampen - Flores type non-embeddability result for 2k-dimensional manifolds |
| 12:30 | Lunch at the faculty building |
| Afternoon lectures are in the room S5, 2nd floor | |
| 16:00 | Zdeněk Dvořák: Tree-width and separators |
Abstracts
Pavel Surynek: Solving Cooperative Path-Finding Optimally by Reducing it to Propositional Satisfiability
The talk will address makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task in CPF is to relocate a set of agents to given goal locations so that they do not collide with each other. A novel SAT encoding of CPF will be described. The novel encoding uses the concept of matching in bipartite graphs to separate spatial constraints of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evaluation shown that novel encoding can be solved faster than existing encodings for CPF and that the SAT based methods dominates over A* based methods in environments densely occupied by agents.
Martin Tancer: Van Kampen - Flores type non-embeddability result for 2k-dimensional manifolds
(Joint work with X. Goaoc, I. Mabillard, P. Patak, Z. Patakova, and U. Wagner)
The van Kampen - Flores theorem says that the k-dimensional skeleton of the (2k+2)-simplex does not embed into R^2k. We prove an analogous result for 2k-dimensional manifolds. We show that for every 2k-dimensional compact manifold M there is a value n such that the k-dimensional skeleton of the n-simplex does not embed into M. This result is also related to a conjecture of Kuhnel, who conjectured that if M is in addition (k-1)-connected, then n can be taken as the smallest integer satisfying \binom{n-k-1}{k+1} > b\binom{2k+1}{k+1} where b is the kth reduced Betti number of M (over Z_2). Our bound, n = 2b\binom{2k+2}{k}+2k+6 is weaker, but on the other hand, it holds for an arbitrary compact 2k-manifold.
Zdenek Dvorak: Tree-width and separators
(joint work with Sergei Norin)
It is well-known that a graph of tree-width at most k has a separator of order at most k+1 which splits the graph into parts of approximately the same size. Using a result on confluent flows, we show a rough converse to this claim: If every subgraph of G has such a balanced separator of order at most s, then G has tree-width at most 105s.
