Below you'll find the programme for the Seminar on Combinatorics, Games and Optimisation (a joining together of the former Seminar on Discrete Mathematics and Game Theory and the former Seminar on Operations Research).
This seminar series covers many of the research areas in the Department: discrete mathematics, algorithms, game theory and operational research.
Unless stated below, this Seminar normally takes place:
Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk.
Upcoming Speakers:
Wednesday 21 November - Iannis Caragiannis (University of Patras)
Venue: 32L.LG.14 from 15:30 - 17:00
Fairness in allocation problems
In this talk, we will present variations of the problem of allocating indivisible goods to agents with additive valuations for the goods. We will define basic fairness concepts such as proportionality and envy-freeness and will discuss their properties. Next, we will focus on allocations of maximum Nash welfare, and we will explain how they guarantee approximate notions of envy-freeness. Finally, we will define new fairness concepts that are related to the level of awareness of the agents for the allocation and to their social relations. We will present examples and many open problems. No advanced or special mathematical background is needed to follow the talk.
Thursday 22 November - Marcin Jurdzinski (Warwick)
Venue: CLM.7.03 from 14:00 - 15:30
Universal trees grow inside separating automata: Quasi-polynomial bounds for parity games
Several distinct techniques have been proposed to solve parity games in quasi-polynomial time since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures, and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games---a key component of which is constructing an automaton that separates languages of words encoding plays that are decisively won by either of the two players---thus establishing a single model that unifies the recent approaches to solving parity games efficiently.
Our main technical results are the nearly matching quasi-polynomial upper and lower bounds on the sizes of all separating automata. In particular, the lower bound forms a barrier that the existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games.We obtain our main results by introducing and studying universal ordered trees, a combinatorial object that may be of independent interest. Firstly, we establish the nearly matching quasi-polynomial upper and lower bounds on the size of smallest universal trees. Then we prove that the sizes of the smallest separating automata and of the smallest universal trees coincide---and hence both are quasi-polynomial---by showing how to turn universal as trees into separating automata, and that there is a universal tree hiding in the states of every separating automaton.
The talk is based on joint work with Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Ranko Lazić, and Paweł Parys.
Wednesday 28 November - Guillem Perarnau Llobet (Birmingham)
Venue: 32L.LG.14 from 15:30 - 17:00
Title and abstract TBC
Previous seminars in the series:
Michaelmas Term 2018
Thursday 15 November - Tibor Szabó (Freie Universität Berlin)
Optimality of the uniform random strategy
The concept of biased Maker-Breaker games, introduced by Chvátal and Erd\H os, is a central topic in the field of positional games, with deep connections to the theory of random structures. For any given hypergraph H the main questions is to determine the smallest bias q(H) that allows Breaker to force that Maker ends up with an independent set of H. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies a couple of natural ‘container-type’ regularity conditions about the degree of subsets of its vertices. This will enable us to derive a hypergraph generalization of the H-building games, studied for graphs by Bednarska and Luczak.
Furthermore, we investigate the biased version of generalizations of the van der Waerden games introduced by Beck. We refer to these generalizations as Rado games and determine their threshold bias up to constant factors by applying our general criteria. We find it quite remarkable that a purely game theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, when the generalizations to hypergraphs in the analogous setup of sparse random discrete structures are usually quite challenging.
Wednesday 14 November - Matthias Englert (Warwick)
Polylogarithmic Guarantees for Generalized Reordering Buffer Management
In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrive online, and have to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server.
Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance travelled by the servers.This problem was introduced by Chan et al. (TCS'12) and has been subsequently studied in an online setting by Azar et al. (STACS'14). The problem is a natural generalization of two very well-studied problems: the k-server problem for b=1 and the Reordering Buffer Management Problem (RBM) for k=1. We consider the GRBM problem on a uniform metric in the online version.
We show how to obtain a competitive ratio of O(log k(log k+loglog b)) for this problem. This is a significant improvement in the dependency on b compared to the previous best bound of O(sqrt(b) log k), and is asymptotically optimal for constant k.
Thursday 8 November - Maryam Sharifzadeh (Warwick)
Number of maximal sum-free subsets of integers and abelian groups.
A set $S$ is sum-free if it does not contain a triple $x,y,z$ such that $x+y=z$ (note $x,y$ may not necessarily be distinct). We say that $S\subseteq [n]$ is a maximal sum-free subset of $[n]$ if it is sum-free and it is not properly contained in another sum-free subset of $[n]$. Cameron and Erd\H{o}s asked whether the number of maximal sum-free subsets of $[n]$ is much smaller than the number of sum-free sets. They also gave a lower bound of $2^{\lfloor n/4 \rfloor }$ for the number of maximal sum-free sets. Together with J\'ozsef Balogh, Hong Liu, and Andrew Treglown, we give an exact solution to the problem: For each $1\leq i \leq 4$, there is a constant $C_i$ such that, given any $n\equiv i \mod 4$, $[n]$ contains $(C_i+o(1)) 2^{n/4}$ maximal sum-free sets. In this talk, I will outline the ideas and techniques used in the proof. I will also discuss some new results on the number of maximal sum-free sets in abelian groups, which are joint work with Hong Liu.
Wednesday 7 November - Brendan Murphy (Bristol)
Solymosi's conjecture for rich lines in general position
We give an explicit construction that disproves a conjecture of Solymosi on the number of lines in general position that contain a near maximal number of points of a Cartesian product set. We will explain how this problem is connected to the sum-product problem, and show why Solymosi's conjecture is plausible. The counter-example we give is motivated by related questions in group theory, and is rather different from the usual examples in arithmetic combinatorics.
Thursday 1 November - Kristof Berczi (Eotvos University)
Improving the integrality gap for multiway cut
In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák while the best known inapproximability factor is 1.2 due to Angelidakis, Makarychev and Manurangsi.
In this talk we show how to improve on the lower bound by constructing an integrality gap instance for the CKR relaxation. A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. One of the byproducts from our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák.
Joint work with Karthakeyan Chanrdasekaran, Tamás Király and Vivek Madan.
Wednesday 31 October - Ágnes Cseh (IE CERS HAS)
The complexity of cake cutting with unequal share
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share.
We investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
Joint work with Tamás Fleiner. The paper received the best paper award at SAGT 2018.
Thursday 25 October - Bruce Reed (McGill)
ω, Δ, and x
We consider three graph invariants and the relationship between them. The first is the size of the largest clique in a graph G, denoted ω(G). The second is the maximum degree of a vertex of G, denoted Δ(G). The third is the chromatic number of G, denoted x(G).Trivially, ω(G)≤ x(G). Greedy colouring shows x(G)≤ Δ(G)+1. So ω(G)≤ x(G)≤ Δ(G)+1. We discuss a conjecture which states that x lies in the lower half of this range. We also show that when x is sufficiently close to Δ it is determined by a small subgraph and can be computed in polynomial time.
Wednesday 24 October - Varun Kanade (University of Oxford)
Hierarchical clustering: Objectives & Algorithms
Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Hierarchical clustering has mostly been studied in procedural terms, i.e., a hierarchical cluster tree is obtained using certain bottom-up (agglomerative) or top-down (divisive) heuristics, rather than finding a hierarchical cluster tree as the solution obtained by optimizing some suitable objective. Dasgupta (2016) identified this as a reason why the theory of hierarchical clustering lagged behind that of flat clustering and proposed an objective function. In this talk, we will take an axiomatic approach to identifying suitable objective functions for hierarchical clustering. We will also describe a new random-graph model with a planted hierarchy. New and existing algorithms and their performance in theory and on some preliminary experiments will be discussed.
Based on joint work with Vincent Cohen-Addad, Claire Mathieu and Frederik Mallmann-Trenn.
Thursday 18 October - Leonidas Pitsoulis (Aristotle University of Thessaloniki)
Decomposition of signed-graphic matroids
In this seminar we will present a decomposition theory for the class of signed graphic matroids which are representable either in GF(2) or GF(4). The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not solely based on k-sums such as the decomposition of regular matroids, but also on an operation called star composition. A sketch of the resulting recognition algorithms as well as an excluded minor characterization of the building blocks of the aforementioned decomposition will also be presented.
2018, 2017, 2016
The Seminar on Combinatorics, Games and Optimisation started in 2016. It is a combination of two previous seminar series:
Seminar on Discrete Mathematics and Game Theory:
2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003
Seminar on Operations Research:
2016, 2015, 2014, 2013, 2012, 2011, 2010