The collection

Every essay — page 36

Page 36 of 36, continuing through the fields in the same order.

Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search

Applied

A rule for choosing, stated exactly, and what it forces on whoever adopts it.

Two triangles and three paths: the relaxation against the shortest tour. k = 3: 12 cities; subtour relaxation 12 with 6 half-edges; shortest tour 14; ratio 1.167.

A bound that may be off by a third

Christofides' algorithm: tree, pairing, tour. 12 cities: tree 2.4441, 6 odd cities paired for 1.5306, tour 3.6069, shortest 3.4606.

Tours within half again of the best

What the agenda leaves standing

Three splits that between them beat every other. The triangle of splits of one pound among three players, with the three half-and-half splits marked and every other lattice point coloured by which of the three dominates it: 134, 134, 134 beaten by exactly one, 91 by more.

Three splits that answer every other

No prices clear a market for a pair worth 3. The plane of prices for items A and B, with the triangle pA + pB ≤ 3 where buyer 1 wants the pair and the square pA, pB ≥ 2 where buyer 2 wants neither; they do not meet.

Prices for things wanted only together

Every envy-free way to split one rent among three rooms. A triangle of rent splits of 90 with the envy-free hexagon (corners 30, 30, 30; 46.7, 21.7, 21.7; 50, 25, 15; 45, 35, 10; 35, 40, 15; 28.3, 33.3, 28.3) and the maximin, equal and grid splits marked.

A rent nobody envies is not one rent

6 figures · new