Below you'll find an overview of the past seminars in this series from 2016. The seminars are listed in reverse chronological order, most recent first.
Thursday 17 November - Timm Oertel (Cardiff)
Integrality gaps of integer knapsack problems
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a “typical” knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
This is joint work with Iskander Aliev and Martin Henk.
Wednesday 16 November - Peter Richtarik (Edinburgh)
Stochastic reformulations of linear systems and efficient randomized algorithms
We propose a new paradigm for solving linear systems. In our paradigm, the system is reformulated into a stochastic problem, and then solved with a randomized algorithm. Our reformulation can be equivalently seen as a stochastic optimization problem, stochastically preconditioned linear system, stochastic fixed point problem and as a probabilistic intersection problem. We propose and analyze basic and accelerated stochastic algorithms for solving the reformulated problem, with linear convergence rates.
Thursday 10 November - Daniel Dadush (CWI)
Making Banaszczyk's Bound Constructive for the Komlos Problem
We first consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)^{1/2}), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t^{1/2} log n) bound. The result also extends to the more general Komlos setting, where each vector has norm at most 1, and gives an algorithmic O(log^{1/2} n) bound.
Joint work with Nikhil Bansal and Shashwat Garg.
Wednesday 9 November - Sven Rady (HCM and University of Bonn)
Strongly Symmetric Equilibria in Bandit Games
This paper studies strongly symmetric equilibria (SSE) in continuous-time games of strategic experimentation with Poisson bandits. SSE payoffs can be studied via two functional equations similar to the HJB equation used for Markov equilibria. This is valuable for three reasons. First, these equations retain the tractability of Markov equilibrium, while allowing for punishments and rewards: the best and worst equilibrium payoff are explicitly solved for. Second, they capture behavior of the discrete-time game: as the period length goes to zero in the discretized game, the SSE payoff set converges to their solution. Third, they encompass a large payoff set: there is no perfect Bayesian equilibrium in the discrete-time game with frequent interactions with higher asymptotic efficiency.
Thursday 3 November - Felix Joos (Birmingham)
Packing and Covering Graphs
Menger's Theorem is one of the most satisfactory results in graph theory. It say that either there are k (vertex-)disjoint paths joining two specified vertex sets or there is a vertex set of size k-1 meeting all such paths. Observe that both statements exclude each other. This theorem is one prime example for the duality between packing and covering objects contained in graphs.
For many other objects (instead of paths between specified vertex sets) in graphs such a duality does not hold. One can consider a weaker form of this duality which is also known as the Erdos-Posa property of graphs. Results in this direction mainly deal with vertex-disjoint objects. We consider edge-disjoint objects (cycles of length l for some integer l) and show why it is much harder to investigate this question.
This is joint work with Henning Bruhn and Matthias Heinlein.
Wednesday 26 October - Michal Feldman (Tel Aviv)
Welfare Maximization via Posted Prices
Posted price mechanisms are simple, straightforward, and strategyproof. We study two scenarios of combinatorial markets where sequential posted price mechanisms achieve optimal or nearly optimal welfare. The first scenario is matching markets with full information, where optimal welfare is obtained. The second is markets with submodular (and XOS) valuations with Bayesian information, where half of the optimal welfare is obtained. We distinguish between static and dynamic pricing, and present various extensions of the above findings. Finally, we mention surprising relations between price of anarchy results and posted price mechanisms.
Based on joint works with Vincent Cohen-Addad, Alon Eden and Amos Fiat (2016), with Nick Gravin and Brendan Lucier (2015) and with Paul Duetting, Thomas Kesselheim and Brendan Lucier (2016).
Thursday 20 October - Bhargav Narayanan (Cambridge)
Symmetric Intersecting Families
A family of sets is said to be intersecting if any two sets in the family have nonempty intersection. Families of sets subject to various intersection conditions have been studied over the last fifty years and a common feature of many of the results in the area is that the extremal families are often quite asymmetric. Motivated by this, P{\'e}ter Frankl conjectured in 1981 that symmetric intersecting families must generally be very small; more precisely, Frankl conjectured that if a family of subsets of $\{1, 2, \dots, n\}$ with the property that any three sets in the family intersect has a transitive automorphism group, then the family must have size $o(2^n)$. In this talk, I shall prove this conjecture.
Joint work with David Ellis.
Wednesday 12 October - Heinrich Nax (ETH Zurich)
Payoff-based dynamics in transferable-utility matching markets
We consider simple, payoff-driven learning dynamics that we derive from laboratory evidence of how individuals adjust their behavior when interacting in low-information environments. We study the resulting convergence properties of such dynamics for transferable-utility matching markets (i.e. multi-player bargaining, assignment game, TU many-to-one matching). The dynamics are driven by individuals’ continued efforts to fulfill their aspirations and resulting aspiration adaptation. Agents have no knowledge of other agents’ strategies, payoffs, or of the structure of the game, and there is no central authority with such knowledge either. Our dynamics constitute a class of simple learning processes that converge to stable and optimal outcomes (the core). Based on stability properties, and not on any ex ante fairness considerations, a subset of the core with a natural equity interpretation may even be selected.
Thursday 6 October - Annika Heckel (Oxford)
The chromatic number of dense random graphs
We establish new upper and lower bounds for the chromatic number of the dense random graph G(n,p) where p is constant. These bounds are the first that match each other up to a term of size o(1) in the denominator, and in particular, they determine the average colour class size in an optimal colouring for the first time. Somewhat surprisingly, the behaviour of the chromatic number changes around p=1-1/e^2, with a different limiting effect being dominant below and above this value. In contrast to earlier results, the upper bound is obtained through the second moment method, and some aspects of the proof will be discussed. Furthermore, the same method can be used to show that a related graph parameter, the equitable chromatic number of the dense random graph G(n,m), is concentrated on just one value on a subsequence of the integers.
Wednesday 5 October - Panayiotis Kolios (Cyprus)
Resilient Drone-based Patrolling through Optimized Path Planning Strategies
Drones have become both affordable and highly capable platforms for watch-keeping and patrolling of particular Regions of Interest (ROI). However current practices assume manual control of flight paths for each drone that tamper scalability and result to operating inefficiencies. In accordance, this talk formulates optimized path planning strategies that would allow drones to autonomously operate both efficiently and effectively across ROIs. To address efficiency, the formulated problem considers all major flying aspects (including topography, weather, etc). To address effectiveness, the derived paths opt for resilience to unexpected events and faults that might occur. As shown, the resulting mathematical programming framework can address different objectives and accommodate and benefit from the availability of multiple drone platforms.
Thursday 29 September - Hal Kierstad (Arizona State)
Some history and applications of generalized coloring numbers
Abstract
WEDNESDAY 15 June - Marc Renault (Paris)
The bijective ratio of online algorithms
Bijective analysis is an intuitive technique for evaluating the performance of online algorithms that is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. Despite its success in providing a clear separation between algorithms for problems such as paging and list update, bijective analysis is not readily applicable to all online problems and algorithms since it stipulates a very strong relation between the compared algorithms that either may be difficult to establish or, worse, may not even exist.
In this work, we address these two deficiencies of bijective analysis. First, we generalize previous techniques that allow us to show optimality of certain greedy-like algorithms for a much wider class of online problems. Second, to account for situations in which an online algorithm is not bijectively optimal, we introduce the bijective ratio as a natural extension of exact bijective analysis. We demonstrate the applicability of the bijective ratio to one of the canonical online problems, namely the continuous k-server problem on metrics such as the line, the circle, and the star. Among our results, we show that the greedy algorithm attains bijective ratios O(k) consistently across these metrics; this is in stark contrast to competitive analysis, according to which it has an unbounded competitive ratio, even for the line.
This is a joint work with Spyros Angelopoulos and Pascal Schweitzer.
THURSDAY 9 June - Gergely Ambrus (University of British Columbia/Alfréd Rényi Institute of Mathematics)
Vector sum estimates in normed spaces
Consider a set V of n vectors in a d-dimensional real normed space whose norm is at most one. Assume that the vectors sum to 0. We consider several questions. First, what is the best possible bound S so that there always exists an ordering of the elements of V, according to which the initial partial sums have norms bounded by S? This question is due to Steinitz. Second, what is the best bound R so that for any given k<n, one choose a subset of V with cardinality k, so that the sum of the elements of this subset has norm at most R? Somewhat surprisingly, there exist such bounds depending only on d, but not on n. We are going to use linear algebraic methods for giving estimates, which are sharp in some cases.
This is a joint work with I. Barany and V. Grinberg.
THURSDAY 2 June - János Pach (EPFL)
Chromatic number vs. clique number
Given a set S of geometric objects, their disjointness graph is the graph on the vertex set S, in which two vertices are connected by an edge if and only if they are disjoint. It is shown, among other things, that the chromatic number of the disjointness graph of segments in d-dimensional space is bounded from above by the 4-th power of its clique number. Joint work with G. Tardos and G. Toth.
TUESDAY 31 May - Jon Lee (University of Michigan)
Relaxing efficiently and kindly
In the context of global optimization, "spatial branch and bound" is the workhorse general-purpose algorithm for so-called factorable formulations. I will present some results on making a key algorithmic aspect efficient, and a way to handle some limited type of non-differentiability. The first involves calculating some volume formulae for certain parametric families of low-dimensional polytopes, and surprisingly needs arguments about continuity and determining when various multivariate polynomials are nonnegative. The second starts with calculus and curve fitting, and in the end looks at when certain univariate polynomials are nonnegative.
FRIDAY 27 May - Dömötör Pálvölgyi (Eötvös University/University of Cambridge)
Polychromatic coloring and cover-decomposition problems in the plane
Is it true that given a finite point set on a sphere and a set of halfspheres, such that the set system that they induce on the point set is a Sperner family, we can select a subset of the points that meet every halfsphere in at least one but at most two points?
I don't know the answer to this question (waiting to be solved by YOU!), but I know that the above holds in the plane if instead of halfspheres we take (pseudo)halfplanes.
I will talk about consequences of similar results in polychromatic coloring and cover-decomposition, and also mention several other open problems.
MONDAY 9 May - Jochen Koenemann (University of Waterloo & University of Bonn)
Network Bargaining - Where Bargaining & Matching Theory Meet
Bargaining is a central topic of study in economics and in the social sciences. In the most basic setting, two agents A & B negotiate how to split a dollar. Assume the agents have monetary outside options a & b, respectively, that they receive, should negotiations fail; Nash's famous bargaining solution postulates that in an equilibrium, the agents each receive their outside options, and that the remainder is split evenly; i.e., the agents receive x_A and x_B such that x_A-a=x_B-b.
In this talk we will look at a natural generalization of Nash bargaining to agents interacting in social networks. We will present a natural equilibrium concept extending Nash's condition, and present Kleinberg & Tardos' recent characterization of graphs that admit equilibria. We will present connections between bargaining theory, cooperative games, and matching theory and use these to derive elegant algorithms for the computation of equilibria. We will also discuss several ways in which unstable instances of network bargaining can be stabilized.
WEDNESDAY 27 April - Neil Olver (VU Amsterdam)
On integrality gaps for Steiner problems
The Steiner tree, Steiner forest, and related problems are among the most classical in network design. I will discuss two results related to natural cut-based relaxations for such problems.
1) The integrality gap of the bidirected cut relaxation for the Steiner tree problem is suspected to be better than 2, but this has remained open for many years. I will discuss how better bounds can (constructively) be obtained for a certain class of instances, via a connection with a much stronger "hypergraphic" LP. (Joint work with A. Feldmann, J. Koenemann and L. Sanita.)
2) We show that the natural cut LP for the prize-collecting Steiner forest problem has an integrality gap strictly worse than 2. This is in contrast to the situation for prize-collecting Steiner tree as well as (non-prize collecting) Steiner forest. (Joint work with J. Koenemann, R. Ravi, G. Schaefer and C. Swamy.)