8th workshop of the Center of Modern Computer Science
8. seminář Centra moderní informatiky
The eighth workshop of the Center of Modern Computer Science will take place on Friday December 18, 2015 in the Mala Strana building.
Centrum moderní informatiky zve na osmý seminář. Přednášky juniorů centra se konají v průběhu programu v pátek 18. 12. 2015 v budově MFF UK na Malé Straně.
| The lectures are in the room S6, 2nd floor | |
| 14:30 | Josef Cibulka: Furedi-Hajnal Constants are Typically Subexponential |
| 15:00 | Andreas Emil Feldmann: An Exact Characterization of Tractable Demand Patterns for Directed Steiner Network Problems |
| 15:30 | Jiří Fink: Approximation algorithms for scheduling a group of heat pumps |
Abstracts
Josef Cibulka: Furedi-Hajnal Constants are Typically Subexponential
(Joint work with Jan Kyncl)
A binary matrix is a matrix with entries from the set {0,1}. We say that a binary matrix A contains a binary matrix S if S can be obtained from A by removal of some rows, some columns, and changing some 1-entries to 0-entries. If A does not contain S, we say that A avoids S. A k-permutation matrix P is a binary k times k matrix with exactly one 1-entry in every row and one 1-entry in every column.
The Furedi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant c_P such that for every natural number n, every n times n binary matrix A with at least c_P n 1-entries contains P.
Fox proved that c_P ≤ 2^(O(k)) for every k-permutation matrix P and that c_P ≥ 2^(Omega*(k^(1/2))) for asymptotically almost all k-permutation matrices. We show that c_P ≤ 2^(O*(k^(2/3)) for asymptotically almost all k-permutation matrices. (The Omega* and O* notation hides a polylogarithmic factor.)
The Stanley-Wilf conjecture says that the number of n-permutation matrices that avoid a fixed k-permutation matrix P is at most (s_P)^n for some constant s_P. The validity of this conjecture follows from the validity of the Furedi-Hajnal conjecture by Klazar's reduction. Extension of the Furedi-Hajnal conjecture to higher-dimensional matrices was found by Klazar and Marcus. We extend the Stanley-Wilf conjecture to higher-dimensional matrices.
Andreas Emil Feldmann: An Exact Characterization of Tractable Demand Patterns for Directed Steiner Network Problems
(This is joint work with Daniel Marx.)
We are interested in the fixed-parameter tractability (FPT) of the Directed Steiner Network (DSN) problem, where we are given a directed edge-weighted graph G with a specified set of terminal vertices R, and a "pattern graph" H, which is a directed (unweighted) graph with vertex set R. The aim is to find the cheapest subgraph N of G that implements all connectivity requirements given by H on the terminals. That is, there is a path in N from s to t if there is an edge st in H. This generalizes the Directed Steiner Tree (DST) problem, where H is always an out-star, and the Strongly Connected Steiner Subgraph (SCSS) problem, where H is always a strongly connected graph. For the parameter k=|R|, it is known that DST is FPT while SCSS is W[1]-hard and thus is unlikely to be FPT. We therefore ask for what classes C of pattern graphs the DSN problem restricted to C is FPT for parameter k. We show that the problem is FPT whenever the class C consists of caterpillar graphs with an additional constant number of edges, and it is W[1]-hard otherwise. Hence we obtain a complete characterization of the complexity of the problem in terms of its class of patterns.
Jiří Fink: Approximation algorithms for scheduling a group of heat pumps
In my talk, I will discuss planning problems for a group of heating systems which supply the hot water demand for domestic use in houses. These systems (e.g. gas or electric boilers, heat pumps or microCHPs) use an external energy source to heat up water and store this hot water for supplying the domestic demands. The latter allows to some extent a decoupling of the heat production from the heat demand. I will focus on the situation where each heating system has its own demand and buffer and the supply of the heating systems is coming from a common source. In practice, the common source may lead to a coupling of the planning for the group of heating systems. The bottleneck to supply the energy may be the capacity of the distribution system (e.g. the electricity networks or the gas network). As this has to be dimensioned for the maximal consumption, it is important to minimize the maximal peak. This planning problem is known to be NP-hard. I will present polynomial-time approximation algorithms for four variants of peak minimization problems and I will determine the worst-case approximation error.
