TITLE: Disrepancy games
SPEAKER: Michael Krivelevich
WHEN: March 2, 4:30pm
WHERE: PPB 300
ABSTRACT:
A discrepancy game played on a hypergraph $H=(V,E)$ by two players, Balancer and Unbalancer. They select one element of the vertex set $V$ alternately, until all vertices are selected. Balancer wins if at the end of the game all edges $e$ in $E$ are roughly equally distributed between the two players.
We derive a criteria for Balancer’s win in a general discrepancy game. In particular, it follows from our result that if $H$ is $n$-uniform and has $m$ edges, then Balancer can achieve having between $n/2-c\sqrt{n\ln m}$ and $n/2+c\sqrt{n\ln m}$ of his vertices on every edge $e$ of $H$.
We also discuss applications in positional game theory.
A joint work with Noga Alon, Joel Spencer and Tibor Szab\’o.
Speaker: Srinath Sridhar
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Parameterized Algorithms for Steiner Tree Variants
Abstract:
Steiner tree problems naturally come up in diverse applications. It is sometimes necessary to find optimal solutions for such problems. Finding Steiner minimum trees on hypercubes is equivalent to finding the shortest evolutionary tree. In this talk, I will define two variants of the problem both of which are NP-complete. The problems can however be characterized by a parameter which is assumed to be small in practice. The first problem can be solved in time exponential in the parameter and polynomial in the size of the input. This shows that the problem is ‘fixed parameter tractable’ (FPT). The second problem can be solved in polynomial time if the parameter is a constant. I will go over prior work and provide an overview of the algorithms.
