Discrete Graduate Students Seminar

Introduction to Positional Games

Positional games are 2-player, finite, combinatorial games, in which players have perfect information, and there are no chance moves. There are several types of these games, each with distinct properties that affect how winning strategies are developed.

Since positional games are finite, it is theoretically possible to list all outcomes in order to find an optimal winning strategy. Unfortunately, this approach is impractical due to an iteratively exponential number of outcomes. Instead, probabilistic methods are used to build random algorithms for finding winning strategies. When possible, techniques, such as the method of conditional expectations, are used to derandomize these algorithms and construct deterministic winning strategies.

In this talk we will introduce the properties of positional games, examine their complexity, and illustrate the process of using probabilistic methods to develop winning strategies, with bounds on van der Waerden numbers as an example.

Steiner Tree Approximation via Iterative Randomized Rounding

Minimum Steiner tree problem is one of the fundamental NP-hard problems, it was first defined by Gauss in a letter he wrote to Schumacher: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In this talk, we will present and analyze a Linear Programming based iterative randomized rounding algorithm on Minimum Steiner tree problem designed by J. Byrka et al. (2013). This algorithm improves the approximation ratio for this problem from \(1+\ln (3/2)\approx 1.55\) to \(\ln(4)+ < 1.39\).

Event Topic

Discrete Applied Math Seminar