Home > Department of Mathematics > Seminars > Lunchtime Seminar
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
Connect with LSE Maths: Twitter


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



Lunchtime Seminar

Below you'll find the program for the Lunchtime Seminar. The Seminar normally takes place on Fridays from 12.05 pm - 12.35 pm in room 32L.B.09 (32 Lincoln's Inn Fields, LSE).

Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator (Room COL 3.14), by sending an e-mail to: seminar@maths.lse.ac.uk

Upcoming Speakers:

Friday 27 November - Tom Lidbetter (LSE)
***Seminar will last one hour, from 12 noon***
Search games with submodular payoff functions

Suppose an element of a finite set X is chosen and a Searcher inspects the elements of the set one by one until he finds the chosen element.  For a given ordering x_1,...,x_n of X, the cost paid by the Searcher to find element x_i is f({x_1,...,x_i}), where f is a non-decreasing, submodular set function.  We consider the problem faced by the Searcher of choosing an ordering of X to minimise the expected cost of finding an element of X chosen according to some known probability distribution.  We give some examples of this problem, including the well-known problem in scheduling theory of minimising the sum of the weighted completion times of a set of jobs with precedence constraints.  The latter problem is NP-hard (and therefore so is ours), and we give a 2-approximation to the optimal search strategy, generalising the analogous result for scheduling.  The approximation makes use of what may be thought of as a version of "Smith's rule" for optimal scheduling.  We go on to consider a zero-sum game where a cost-maximising Hider chooses an element of X, the Searcher chooses an ordering of X and the payoff is the cost to the Searcher in finding the object.  We show that any optimal mixed (randomised) strategy of the Hider must lie in a well-known object called the base polyhedron of f.

This is joint work with Robbert Fokkink.

Friday 4 December
Speaker, title and abstract TBC

Friday 11 December
Speaker, title and abstract TBC


Previous seminars in this series: 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006