# Metric facility placement planner

Edition: 8 October 2026. Initial decision: **Conditional engineering**. The product interpretation and pricing are hypotheses; independent proof and buyer validation remain open.

## Research finding

The result claims deterministic polynomial-time k-median approximation with factor 1+2/e+epsilon for finite rational metrics and specified facility candidates. It opens at most k facilities; the polynomial may depend on epsilon.

## Problem and buyer

An operations team selecting a fixed number of depots or service points needs to reduce aggregate distance and understand how far a proposed plan can be from the best plan under a stated model.

## What the finding could enable

A planning tool could produce a candidate plan with a documented model-specific approximation guarantee and scenario comparisons. The theorem strengthens a solver backend; the planner, data cleaning and integrations were already possible.

## Technical and commercial limits

Capacity, fixed opening costs, time windows, directed travel times and fairness constraints are not covered automatically. A road-time matrix may violate symmetry or triangle inequalities. The theorem's approximation factor is not an instance-specific optimality certificate.

## Minimal architecture

Metric and candidate-site validator -> research approximation backend -> lower-bound baseline -> scenario viewer -> export. Reject unsupported constraints or route them to separately labeled solver modes.

## Existing alternatives and differentiation

Commercial optimization suites and tailored location-planning tools are established substitutes. A narrow vertical and trusted data pipeline are more credible differentiation than a generic map UI.

## Monetization hypothesis

Hypothesis: AUD 5,000-20,000 per site-planning engagement or an annual vertical subscription after repeat use is established. Contract ranges are prospective assumptions, not observed quotes.

## Validation experiment

Compare objective values, constraint fidelity and runtime with exact optima on small cases and established heuristics on larger instances. Measure sensitivity to inaccurate distances and epsilon choices.

## Conditions to reject or defer

Defer if the buyer's problem is capacitated or nonmetric, or if existing solvers provide stronger practical solutions within their time budget.

## Next concrete action

Review the algorithm's epsilon dependence and build a strict metric-instance validator before any location demo.

## Source evidence

Repository sources are pinned to revision `fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb`. Selected scope notes and manuscript statements have been reviewed to the extent described above; these links do not represent successful kernel checks.

### Family 125

Subject: The metric <i>k</i>-median approximation threshold and recovery.

- [Single-exponential recovery and bounded-price strictness for metric k-median](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026/paper.pdf)
- [The approximation threshold for metric k-median](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026/main.pdf)
- [Formal scope notes](https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/lean/docs/125.md)

## Current alternative sources

Primary documentation reviewed on 8 October 2026. Product availability demonstrates alternatives, not demand or willingness to pay for this proposal.

- [Gurobi commercial licensing](https://www.gurobi.com/product/pricing-and-licensing)