Home > Department of Mathematics > Seminars > Seminar on Discrete Mathematics and Game Theory
How to contact us

Department of Mathematics
Columbia House
London School of Economics
Houghton Street
London WC2A 2AE, UK


Email: maths.info@lse.ac.uk|
Tel: +44(0)207 955 7732/7925


Click here| for information on how to get to LSE using public transport and maps of the campus

Seminar on Discrete Mathematics and Game Theory

Below you'll find the programme for the Seminar on Discrete Mathematics and Game Theory. The Seminar normally takes place on Thursdays from 2.00 pm - 3.00 pm in room TW2.3.01 (Tower Two, Clement's Inn - entrance through Tower One|), unless stated below. Please contact the seminar administrator on seminar@maths.lse.ac.uk|, for further information about any of these seminars.

Upcoming Speakers:

Thursday 6 November - Thomas Kesselheim| (Max Planck, Saarbruecken)
Primal Beats Dual on Online Packing LPs in the Random-Order Model

We study packing linear programs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources.

First, we consider the following special case of online weighted matching: The vertices on the right-hand side of a bipartite graph are given in advance and the vertices on the left-hand side arrive online in random order. Whenever a vertex arrives, its adjacent edges with the corresponding weights are revealed and the online algorithm has to decide which of these edges should be included in the matching. We present a new algorithmic approach achieving competitive ratio e = 2.72... This matches the lower bound for the classical secretary problem.

For general packing LPs, we present an online algorithm with competitive ratio $1-O(\sqrt(log d / B)), where d denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1 - \epsilon)-approximation if the capacity ratio satisfies B=\Omega(log d / \epsilon^2), which is known to be best-possible for any (randomized) online algorithms.

Joint work with Klaus Radke, Andreas Tönnis, and Berthold Vöcking, RWTH Aachen University.

Thursday 13 November - Dan Kral |(University of Warwick)
Title and abstract TBC

Tuesday 18 November -
Eilon Solan| (Tel Aviv University)
Room TW1.2.03, Tower One, St. Clement's Inn, LSE
Stopping games with termination rates

Multiplayer stopping game with termination rates are continuous-time stopping games in which when some players stop at the time interval $[t,t+dt)$, the game does not terminate with probability 1, but rather stops with some probability, which is of the order of $dt$ and may depend on time and on the set of players who stop at that time. We prove that every multiplayer stopping game with termination rates admits an $\ep$-equilibrium, for every $\ep > 0$.

Thursday 20 November - Ilias Diakonikolas| (Edinburgh)
Algorithmic Approaches to Statistical Estimation under Structural Constraints

The area of inference under structural (or shape) constraints -- that is, inference about a probability distribution under the constraint that its density function satisfies certain qualitative properties -- is a classical topic in statistics and machine learning.
Shape restricted inference has seen a recent surge of research activity, in part due to the ubiquity of structured distributions in the natural sciences. The hope is that, under such structural constraints,  the quality of the resulting estimators may dramatically improve, both in terms of sample size and in terms of computational efficiency.

In this talk, I will describe a framework that yields new, provably efficient estimators for several natural and well-studied classes of distributions. This approach relies on a single, unified algorithm that provides a fairly complete picture of the sample and computational complexities for fundamental inference tasks. The focus of the talk will be on density estimation (learning), but I may also discuss applications of these ideas to hypothesis testing.

Thursday 27 November - Costis Daskalakis| (MIT)
Title and abstract TBC

Thursday 4 December - speaker, title and abstract TBC

Thursday 11 December - Jop Briet| (NYU/CWI)
Title and abstract TBC

Previous seminars in this series:

2014|, 2013|, 2012|, 2011|, 2010|, 2009|, 2008|, 2007|, 2006|, 2005|, 2004 and before|