Integrality gap
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
A bound that may be off by a third
The shortest tour through a set of cities is hard to find, and a linear programme gives a lower bound for it in polynomial time: give every road a weight between nought and one, two at each city, at least two across every division of the map. On random cities the bound is almost always exact. On two triangles joined by three long paths it falls short by nearly a third, and whether a third is the worst it can ever do has been conjectured for decades and never proved.
Prices for things wanted only together
When every buyer wants one thing, there are always prices at which everyone is content with what they get. Let one buyer want two things together and there may be none — and whether there are is decided exactly by whether the market's best fractional allocation beats its best whole one.
Named alongside it
The objects these essays reach for when they reach for this one.
Linear programmingAssignmentCoreDualityMarket clearingMinimum cutPolytopeRelaxationTravelling salesman