Description

The relation $1+1=2$ has been the subject of some attention over the years. The additivity property of the counting numbers can be expressed by saying that the sequence of real numbers $a_n$ satisfies $a_{n+m} = a_n + a_m$ for all $n, m$. This property is very powerful, but also very special: it holds only for sequences $a_n = c n$ ($c$ constant). In various mathematical situations, one cannot expect something as strong as additivity to hold. But it turns out that approximate additivity, where we allow a small error on the right-hand side of the equality, or even subadditivity, where we replace the equality by an inequality, can carry over a surprising amount of the structure that one associates with additivity.

A sequence $a_n$ is subadditive if $a_{n+m} \leq a_n + a_m$ for all $n,m$. A result that can be proved using first-year analysis (Fekete's Lemma) says that such a sequence satisfies $\lim_{n \to \infty} (a_n / n) = \beta$ exists (possibly $-\infty$). If we can rule out $\beta = -\infty$, then we have preserved the fact that the sequence grows linearly, which was one of the key properties of additivity!

Subadditivity, or approximate subadditivity is quite a common property of probabilistic optimization problems, where one can get a feasible solution to a large-scale problem by splitting it into smaller sub-problems and pasting together optimal solutions for the smaller problems.

For example, consider the bin-packing problem, which is to find the smallest number of unit-capacity bins needed to accommodate $n$ random-weight items. If $b_n$ is the expected number of bins needs for the optimal assignment, then we can argue that $b_{n+m} \leq b_n + b_m$, since for $n+m$ items we can deal with the first $n$ and last $m$ items separately, at expected cost $b_n + b_m$, to get a (typically non-optimal) solution to the full assignment. The optimal solution is at least as good as this, hence the bound $b_{n+m} \leq b_n + b_m$. Fekete's lemma lets us quite easily conclude that $\lim_{n \to \infty} (b_n /n) = \beta_{\rm bin}$ exists. The exact value of $\beta_{\rm bin}$ depends on the distribution of the item weights, and is in general not so easy to compute. It is fairly obvious that $\beta_{\rm bin} \geq \mu$ where $\mu$ is the expected weight of an item; some conditions are known as to when $\beta_{\rm bin} = \mu$ (Rhee, 1988).

There are many other problems from probability theory, optimization, and statistical mechanics that have natural subadditive structure. As well as bin-packing, there is self-avoiding walk, long increasing subsequences of a random permutation, and the random travelling salesman problem, for example, which concerns the length of the shortest path that visits a large number of randomly distributed cities, where some of the main problems still resist mathematical analysis.

This project will investigate simple applications of subadditivity in various contexts, and then turn to its role in some probability, counting, or optimization problems, such as bin packing and self-avoiding walk. Other tools that often go hand-in-hand with subadditive are concentration and martingales, so those topics may well also play an important role.

There will scope for simulation.

   

Left: An increasing subsequence exhibited on The Frost Report, 1966. Right: Lonnie Donegan demonstrates bin packing, 1960.

Recommended prior knowledge

At least one of Markov Chains II or Probability II is necessary to understand the foundations of the project.

Students taking the Stochastic Processes III course may find it helpful.

Optimal bin-packing can be solved via linear programming or dynamic programming, so following the Operations Research III course might provide some useful ideas.

Certain directions for this project may benefit from programming skills, such as using R, python, MATLAB.

Resources

For some background on what may be involved, you should:

• look at some of the recommended literature or other literature you find to see which look most helpful;
• search for "subadditivity" or other keywords on the web.

Reading list. Two good books that motivate possible directions for the project, and go into many deeper areas are:

• J. Michael Steele, Probability Theory and Combinatorial Optimization. SIAM, 1997. Available online via the library.
• D. Romik, The Surprising Mathematics of Longest Increasing Subsequences. CUP, 2015. Available online via the library.

A nice short paper on bin-packing is:

• W.T. Rhee, Convergence of optimal stochastic bin packing. Operations Research Letters, 4 (1985) 121–123. Available online via the library.

Further ideas on bin-packing and related algorithms (not making much use of subadditivity, but that could be a project aim!) can be found in the book:

• E.G. Coffman, Jr. and G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley, 1991.