The collection

Every essay — page 34

Page 34 of 34, 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.

An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The core of a market with two houses and two buyers. The core of an assignment game drawn in the plane of buyer A's payoff against buyer B's, a polygon with vertices (0, 1), (0, 0), (1, 0), (4, 3), (2, 3); the buyers' best corner is (4, 3).

The prices nobody can break away from

3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative.

Prices at every corner

Eight corners of a squashed cube, visited in order by the simplex method. Klee and Minty's program in 3 variables drawn as its own deformed cube and as a plain one. The simplex method with the largest-price rule visits all 8 corners, with objective values 0, 4, 6, 10, 15, 19, 21, 25; the optimum is one edge from the start.

The cube that takes every corner

The core of a group worth the square of its size: the outline of its six arrival orders. Splits of 9 among three players; core corners (1, 5, 3), (5, 1, 3), (1, 3, 5), (5, 3, 1), (3, 1, 5), (3, 5, 1); arrival-order splits (1, 3, 5), (1, 5, 3), (3, 1, 5), (5, 1, 3), (3, 5, 1), (5, 3, 1); average 3, 3, 3.

The corners are the orders of arrival

6 figures · new

The cheapest tree for a remote user between two near ones, and each user paying for its own link. A source and 3 users with link costs source–A 2, source–B 9, source–C 2, A–B 1, B–C 1, A–C 2; the cheapest tree costs 4 and Bird's rule charges 2, 1, 1.

Each user pays for its own last link

6 figures · new

Every majority pattern on 5 candidates, and the fewest voters that make it. 12 tournaments on 5 candidates: wins 22222 needs 3; wins 32221 needs 3; wins 32221 needs 3; wins 32221 needs 3; wins 33211 needs 3; wins 33211 needs 3; wins 42211 needs 3; wins 43111 needs 3; wins 33220 needs 3; wins 42220 needs 3; wins 33310 needs 3; wins 43210 needs 1.

How few voters any majority needs

5 figures · new

The fewest swaps to a winner

5 figures · new

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

5 figures · new

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

5 figures · new