Why a greedy meeting scheduler is often the right first build

Six weeks out, the matching engine finally produces something. Nine hundred scored buyer and exhibitor pairs, ranked, with reason codes attached. Somebody in the room asks the obvious question: how do these become a diary?

The answer that gets proposed is almost always a solver. Someone has read about constraint programming, someone else wants an optimal schedule, and the estimate comes back at eight weeks. A greedy meeting scheduler is the thing you can have working by Thursday, and on a first edition it will get you most of the way there.

Here is the case for building it first, with the arithmetic, and with an honest account of what you give up.

What a greedy scheduler actually does

Sort every proposal by score, highest first. Walk the sorted list once. For each proposal, find the earliest time slot where the buyer is free, the exhibitor is free, and a table is available. Book it there. If no such slot exists, drop the proposal and move to the next one.

That is the whole algorithm. It has no backtracking, no lookahead and no notion of regret. A proposal scoring 0.94 gets placed before one scoring 0.93, and once placed it never moves, even if moving it would let three other meetings happen.

The reason this is respectable rather than lazy is that a version of it has a proven worst case. Avis surveyed heuristics for the weighted matching problem in Networks in 1983, and the sorted greedy algorithm has a performance ratio of one half: whatever graph you hand it, the matching it returns carries at least half the weight of the best possible matching. The running time is dominated by the sort, at order m log n for m proposals over n participants.

Preis improved the time bound at STACS in 1999 with a linear time algorithm that keeps the same one half guarantee, replacing the globally heaviest available edge with a locally heaviest one. Drake and Hougardy went further in ACM Transactions on Algorithms in 2005, with a linear time algorithm whose ratio can be pushed arbitrarily close to two thirds. The exact answer has been available since Edmonds published the first polynomial time algorithm for weighted matching in 1965. None of that is the reason to start greedy. The reason is that the sorted pass is about forty lines of code and every placement it makes can be explained to a concierge team in one sentence.

Walking 500 proposals through it

Take a hosted programme with 120 buyers, 250 exhibitors and 10 meeting slots across two days. Tables are not the binding constraint here, so assume 60 tables, which gives 600 places against 500 proposals.

Sort the 500 by score and walk them.

The first hundred proposals go in almost untouched. Diaries are empty, so the only way to fail is if the same buyer appears twice in the top hundred with a clash, and at this density that is rare. Say 100 placed, 0 dropped.

Proposals 101 to 300 hit a partly filled diary. Two hundred proposals, of which 168 find a free slot for both sides and 32 do not. Placement is falling because the popular exhibitors are filling up, and the buyers who sent the most requests are the ones whose diaries close first.

Proposals 301 to 500 hit a diary that is mostly booked at the top end. Two hundred proposals, 121 placed and 79 dropped.

Totals: 389 meetings placed from 500 proposals, 111 dropped, a placement rate of 77.8 per cent. Spread across 120 buyers that is 3.24 meetings each, and across 250 exhibitors, 1.56 each.

Now the value. Suppose the 500 proposals carry a total match score of 372.5, a mean of 0.745, and the 389 placed meetings carry 302.1. Greedy captured 81.1 per cent of the score that was proposed. That number is worth computing, and it is worth being precise about what it is not.

What does the half guarantee actually promise?

The 81.1 per cent above is the placed score over the proposed score. The theoretical guarantee is a different ratio entirely: placed score over the score of the best possible schedule. Those denominators are not the same, and confusing them is the most common error I see when somebody quotes an approximation bound in a planning document.

There is a second gap, which matters more in practice. The matching bound applies to a single matching, meaning one round of pairings where nobody appears twice. A meeting programme is ten of those stacked up, with a table capacity limit sitting across all of them and a participant able to appear in every slot. Each individual slot in your schedule is a matching. The whole schedule is not. So the one half figure is a guarantee about a simpler object than the one you are actually building, and you should treat it as a sanity floor for the shape of the algorithm instead of a promise about your show.

What the guarantee genuinely buys you is the knowledge that greedy cannot collapse. There is no proposal set on which sorting by score and placing first-fit returns almost nothing while a perfect schedule was available. The failure mode of a bad heuristic, where the output is arbitrarily far from the best answer, is ruled out. On real proposal sets, where scores are spread out and the graph is sparse, greedy usually lands well above its worst case.

Why not run an exact solver from the start?

Because the constraints are not stable yet, and an exact answer to the wrong problem is worth less than an approximate answer to the right one.

In the first edition of a meeting programme, the following will all change after somebody looks at the output: how long a slot is, whether lunch is a slot, whether a buyer can hold two meetings back to back, whether an exhibitor with two tables counts as one participant or two, and whether the sponsor who paid for priority gets their meetings placed before the sort or inside it. Each of those changes the model. A greedy pass absorbs them in an afternoon because the rule is local. A solver formulation absorbs them by being rewritten.

The second argument concerns trust. When a show director asks why a particular buyer got four meetings and not seven, the greedy answer is a walk through the sorted list showing where each of the other three proposals failed and which slot was already taken. That explanation is short and it is true. The equivalent explanation from an optimiser is that the objective function preferred a different global arrangement, which is also true and satisfies nobody.

I would build the solver second, after one edition of real data, and I would keep the greedy pass permanently as the baseline the solver has to beat. If the solver cannot beat greedy by a margin that shows up in meetings held, it has not earned its maintenance cost.

Where greedy gets embarrassing

Three failures show up reliably, and it is better to name them before somebody else does.

The first is order dependence at ties. If forty proposals all score 0.80, the order they arrive in decides who gets a table, and that order is usually the database's insertion order, which is usually registration order. Early registrants quietly win. Break ties deliberately, on something you are willing to defend, such as the participant with fewer meetings so far.

The second is the blocked pair. Two people whose only mutual free slot is slot 7, where a lower scoring proposal has already claimed one of them. Greedy will never find this, because it does not reconsider. A single repair pass over the dropped list, trying to swap one placed meeting to a different slot to admit a dropped one, recovers a meaningful share of these for very little code.

The third is concentration. Sorting by score sends proposals to the exhibitors who score well against everybody, and the first pass will happily give one exhibitor eleven meetings while a small stand gets none. The scheduler is doing exactly what it was told. The fix is a cap applied before the sort, and the diagnosis belongs with the ranking work rather than the placement work.

What to measure on the first run

Four counts, taken straight out of the scheduler rather than reconstructed later.

Placed. 389 in the example above. This is the only number anybody asks for and the least informative on its own.

Dropped for clash. Proposals where both parties existed but never had a free slot in common. If this is large, your problem is diary shape, and the availability work is where to look.

Dropped for capacity. Proposals that failed because every table in every mutually free slot was taken. If this is large, your problem is table allocation, which is a different fix with a different cost.

Empty slots per participant. With 120 buyers over 10 slots there are 1,200 buyer slots, and 389 meetings fill 389 of them, leaving 811 empty. Most of those are fine, because a buyer with four proposals was never going to hold ten meetings. The ones that are not fine are the gaps between booked meetings, and the idle time those gaps create is the complaint that actually reaches your inbox.

Where this stops

Greedy optimises the sum of match scores and nothing else. It has no view on fairness, no view on whether a buyer's day is a sensible shape, and no view on which meetings would have happened anyway.

That last one is the limit I would put in front of a board. A meeting between a buyer and an exhibitor who already trade, scoring 0.95 because every sub-score agrees, gets placed first. A meeting that would introduce two parties who have never met, scoring 0.71, gets placed after it and drops out when the diary fills. The schedule maximises score and may be minimising the thing the show is for. No amount of algorithmic sophistication fixes that, because the problem is in the objective rather than the search. If you want new relationships weighted higher, that belongs in the score before the scheduler ever sees it.

The other honest limit is that none of the guarantees survive contact with a participant who does not turn up, and a schedule is a plan rather than a record.

Start by running a sorted greedy pass over last edition's proposal file, using the availability you actually held, and print the four counts. If placement comes out above 75 per cent and the drops are mostly capacity, your matchmaking problem is a floor plan problem and no solver will help. If the drops are mostly clashes, the fix is upstream in what you know about people's days.