Seminar on Combinatorics, Games and Optimisation

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:

Upcoming Speakers:

Thursday 24 January - Anran Li (LSE) CANCELLED 

Previous seminars in the series:

Michaelmas Term 2018

Thursday 13 December - Vera Traub (Hausdorff Centre for Mathematics)

Beating the integrality ratio for s-t-tours in graphs
Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this work, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497.

Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebő and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).

This is joint work with Jens Vygen.

Wednesday 12 December - Noam Nisan (Hebrew University of Jerusalem)

The Communication Complexity of Cake-Cutting
This talk concerns the well-studied model of "cake-cutting" for studying questions regarding notions of fair division of resources.  We focus on discrete versions rather than using infinite-precision real values, specifically, focusing on the communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-log total communication), and "hard".

Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class.  Our main open problem is to separate the "hard" from the "medium" classes.

Joint work with Simina Brânzei

Thursday 6 December - Andrés Cristi (Universidad de Chile)

A Near Optimal Mechanism for Energy Aware Scheduling
Consider a cloud server, where clients can submit jobs for processing. The quality of service that each agent receives is given by a private non-decreasing function of the completion time of her job. The server has to process the jobs and charge each agent while trying to optimize the social cost that is defined as the energy expenditure plus the sum of the values of the internal cost functions. The server operator would like to design a mechanism in order to optimize this objective, which ideally is computationally tractable, charges the users “fairly” and the induced game has an equilibrium. We present a mechanism that combines the aforementioned properties with a constant Price of Anarchy. An interesting feature of our mechanism is that it is indirect: each user needs only to declare an upper bound on the completion time of her job, and not the cost function.

This is joint work with Antonios Antoniadis.

Friday 30 November - Benny Sudakov (ETH)

Subgraph statistics
Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given a large graph $G$, what is the fraction of $k$-vertex subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or complete, and $\ell$ is zero or $\binom k 2$, this fraction can be exactly 1. On the other hand if $\ell$ is not one these extreme values, then by Ramsey's theorem, this fraction is strictly smaller than 1.

The systematic study of the above question was recently initiated by Alon, Hefetz, Krivelevich and Tyomkyn who proposed several natural conjectures. In this talk we discuss a theorem which proves one of their conjectures and implies an 0asymptotic version of another.  We also make some first steps towards analogous question for hypergraphs. Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities and hypercontractivity.

Joint work with M. Kwan and T. Tran

Wednesday 28 November - Guillem Perarnau Llobet (Birmingham) 

Efficient sampling of random colorings
A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree \Delta is rapidly mixing for k \ge \Delta+2. In 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper k-colorings for k > (11/6)\Delta, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the (11/6)\Delta barrier for general graphs by showing rapid mixing for k > (11/6 - \eta)\Delta for some positive constant \eta. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda’s 2007 survey paper on Glauber dynamics for colorings. (Joint work with Michelle Delcourt and Luke Postle)

Wednesday 21 November - Iannis Caragiannis (University of Patras) 

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 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