Aegean Placement

Sixteen real Aegean ports, and the question of where to put a handful of supply depots among them. Asked two ways — and the difference between the two ways is the point.

Nothing here is computed on our side. The page loads a WebAssembly module, Go's runtime bridge and a packed coastline — three static files — and solves everything locally. There is no endpoint behind this page. Nothing on this page touches a chain.

One algorithm has a proof. The other does not.

Max-coverage — guaranteed

Serve as much population as possible within a radius of some depot. Coverage is monotone and submodular, so plain greedy is proven to return at least 63.2% of the true optimum — that is 1 − 1/e, and it is a worst case, known before the solver runs.

p-median — no guarantee

Minimize total weighted travel to the nearest depot. There is no approximation bound for the interchange heuristic that solves it. It is very good in practice and it is guaranteed nothing, and this page never calls its answer optimal.

Up to 4 depots the page also runs an exhaustive search and shows the true optimum beside the heuristic's answer, so you watch the bound hold rather than take our word for it. Past 4 the exhaustive search stops being cheap, and the page says the optimum was not computed rather than going quiet about it.

The map

Problem p-median no guarantee max-coverage proven bound

Depots 3 Seed

The seed decides where the search starts, not where it ends. p-median begins from eight random sets of depots and improves each by interchange, and on these sixteen ports it reaches the same answer from all of them — twenty-five seeds, one cost, and pass counts that vary widely, which is how you can tell the seed is reaching the search rather than being ignored. Over 120 generated instances the same heuristic matched an exhaustive optimum every time; that is a measurement of those instances and not a bound anyone can promise, which is the whole difference between this mode and the one beside it. Max-coverage takes a seed and cannot use it: greedy is deterministic, so the same inputs give the same depots by construction.

Loading the solver…

The answer

The ports

Every port below is a real place, and its weight is its population. Total demand across the 16 ports is 4632956.

The demand points, largest first. Rendered from the dataset on the server, so this table is here whether or not WebAssembly is.
Port	Country	Population	Lat	Lon
Izmir	Turkey	2587000	38.438	27.150
Thessaloniki	Greece	828000	40.698	22.883
Piraeus	Greece	466065	37.942	23.646
Heraklion	Greece	137154	35.325	25.130
Volos	Greece	110632	39.370	22.950
Canakkale	Turkey	87791	40.146	26.406
Chania	Greece	78728	35.512	24.016
Chalkida	Greece	71842	38.464	23.612
Kavala	Greece	59240	40.941	24.402
Rodos	Greece	56969	36.441	28.223
Alexandroupolis	Greece	52979	40.849	25.874
Mytilene	Greece	29328	39.110	26.555
Chios	Greece	26891	38.368	26.136
Kos	Greece	19244	36.894	27.289
Ermoupoli (Syros)	Greece	12260	37.450	24.933
Sitia	Greece	8833	35.200	26.099

Where the data comes from

Coastline and ports are Natural Earth 1:10m, public domain. The map is decimated with Ramer-Douglas-Peucker at 0.002°, the figure recorded by the run that built the artifact rather than one typed beside it.

Selecting the ports takes three rules, not one, and the page says so because a filter that has exceptions is not a computed filter.

Distance. A populated place inside the crop is a port if it sits within 7 km of a coastline vertex. That much is computed, and the measured distance for every row is carried in the dataset.
Named exceptions. The distance rule cannot catch a capital whose harbor is a separate municipality, so Athens is removed by name, with the reason recorded beside the row it would have produced. Bending the threshold instead would have dropped real ports with it.
Position overrides. Positions are Natural Earth's populated-place points except for Piraeus, where an explicit table supplies the ferry terminal instead — the town center is several kilometers from the quay, and a problem about sea distances must not measure from the town hall. Both positions are kept in the dataset.

Population is Natural Earth's POP_MAX, used as the demand weight and nothing else: it is not a claim about a port's throughput or a current census.

The crop stops at the Dardanelles. A box reaching far enough north for Kavala and Alexandroupolis also reaches over the strait and picks up Istanbul, which is not an Aegean port and has more people than the rest of the table combined — every depot would go there and the map would be one dot.

The solver is a separate public module: github.com/pigfox/aegean-solver. p-median interchange, lazy-greedy max-coverage and the distance model, with their own tests and 100% statement coverage. The bound is checked there against exhaustive search over 480 instances rather than cited.