1-Center Problem¶

A minimax location problem that places one center to minimize the largest distance or service cost to any demand point.

Version: v1 · 2026-09-28 · History
Domain-specific #: 7806
Domain group: Formal Sciences
Origin domain: Operations Research
Subdomain: Facility Location → Operations Research
Aliases: One-center problem, Single-facility minimax location, Minmax location problem

Core Idea¶

The 1-center problem asks where one facility should be placed when the worst-served demand determines quality. For each feasible location, compute all demand costs and retain the maximum; the optimum minimizes that maximum.

Geometry, graph structure, discrete candidates, weights, and distance choice create distinct variants. The objective's bottleneck character separates it from median problems and makes extreme or active constraints central to optimality certificates.

How would you explain it like I'm…

Nobody Left Far Away

Say a town needs one ice-cream truck parking spot, and every kid has to walk to it. We want the kid who lives farthest away to have the shortest walk possible. Finding that spot is the 1-Center Problem.

Help the Farthest Person

The 1-center problem is about choosing where to put one thing, like a fire station, that many people need to reach. For each possible spot, you find the person who would have the worst trip. Then you choose the spot where that worst trip is as small as possible. This is different from making the average trip short: here only the worst-off person decides how good a spot is.

Minimax Single-Facility Location

The 1-center problem places a single facility so that the worst-served demand point is served as well as possible. For every candidate location you compute the cost (such as distance) to each demand point and keep only the largest; the best location is the one with the smallest such maximum, a 'minimax' goal. This separates it from the median problem, which minimizes the total or average cost and can leave a far-off customer badly served. Different versions arise depending on whether the facility can go anywhere in a plane or only on a road network or a list of candidate sites, whether demands carry weights, and how distance is measured. Because only the extreme cases matter, the few points that tie for 'worst' are what determine and prove the optimum.

Formally, choose a location x from a feasible set to minimize max_i w_i·d(x, v_i), where the v_i are demand points, the w_i optional weights, and d a chosen distance or cost. The objective is a bottleneck: quality is set entirely by the worst-served demand, in contrast to the 1-median problem, which minimizes the sum of weighted costs. Variants differ by space (continuous geometry, graphs with facilities on vertices or edges, or a discrete candidate list), by weighting, and by metric, and each yields its own algorithms. At the optimum, a small set of demands are 'active', achieving the maximum simultaneously, and these extreme points supply the certificate that no move can lower the worst cost. Reasoning about the problem therefore centers on active constraints rather than on aggregate cost.

Structural Signature¶

Sig role-phrases:

Demand set — Lists points or clients whose worst service cost matters. It is required input. Counterfactual: No demands leave the objective empty.
Feasible center set — Constrains where the single center may be placed. It is decision domain. Counterfactual: Changing continuous to discrete locations changes the problem.
Cost or metric — Maps each center-demand pair to service burden. It is comparison rule. Counterfactual: No declared cost makes minimax values incomparable.
Single center — Provides the one decision location. It is cardinality constraint. Counterfactual: Multiple centers define k-center.
Maximum operator — Selects the worst served demand at a candidate location. It is robust objective. Counterfactual: Replacing maximum by sum defines median-like objectives.
Minimizer and radius — Return an optimal location and its least possible worst cost. It is solution. Counterfactual: A feasible location without an optimality bound is only a candidate.

What It Is Not¶

It is not the 1-median problem.
It is not k-center with several facilities.
It is not maxmin obnoxious-facility location.
The Euclidean smallest circle is one special case, not the full definition.
Closest near-miss. The 1-median minimizes aggregate cost and can sacrifice an outlier; the 1-center minimizes the worst cost and is driven by extreme demands.

Scope of Application¶

Facility location. Bounds worst travel or response cost.
Computational geometry. Finds smallest enclosing circles and balls.
Networks. Places a center under graph distance.
String analysis. Uses Hamming distance in closest-string variants.

Clarity¶

State demand and feasible sets, continuous or discrete choice, distance or cost, weights, ties, approximation criterion, and whether the answer includes a center, radius, or certificate.

Manages Complexity¶

The formulation compresses many service constraints into one epigraph radius while retaining the active demands that certify the optimum.

Abstract Reasoning¶

Define demand points and feasible locations.
Choose cost and any weights.
Express the maximum cost for a candidate center.
Minimize that radius by geometric, combinatorial, or convex methods.
Verify optimality through active demands or lower bounds.

Knowledge Transfer¶

Minimax-center reasoning transfers across geometry, graphs, and strings only when distance and feasible-center semantics are preserved.

Examples¶

Canonical¶

For planar points under Euclidean distance, the center of the smallest enclosing circle minimizes the farthest point distance; boundary points certify the optimal radius.

Mapped back: demands → planar points; feasible → plane; metric → Euclidean; center → circle center; maximum → radius.

Applied / In Practice¶

Choosing a warehouse to minimize total delivery distance is a 1-median problem even if only one warehouse is opened.

Mapped back: centers → one; objective → sum; verdict → not 1-center.

Structural Tensions¶

T1 — Worst-Case Equity versus Average Efficiency. Protecting the farthest demand can increase total travel.

Diagnostic: Is the operational goal maximum guarantee or aggregate cost?

T2 — Continuous Freedom versus Discrete Feasibility. An unconstrained geometric center may outperform every permitted site.

Diagnostic: Is the center allowed anywhere or only at candidate locations?

Structural–Framed Character¶

1-Center Problem is strongly structural as a single-facility minimax optimization.

Structural Core vs. Domain Accent¶

The skeleton is demand, feasible center, cost, maximum, and minimization. Applications supply geometry, networks, weights, and service meaning.

This entry is a kind of Optimization.

Approved root. No reviewed parent entails this exact minimax location problem.
Related — facility location, minimax optimization, k-center, and 1-median. They provide the field, objective family, generalization, and contrasting aggregation.

Relationships to Other Abstractions¶

Current abstraction 1-Center Problem Domain-specific

Parents (1) — more general patterns this builds on

1-Center Problem is a kind of Optimization Prime

The 1-Center Problem is Optimization that minimizes the maximum demand-point distance or service cost from one chosen center.

Hierarchy path (1) — routes to 1 parentless root

1-Center Problem → Optimization

Neighborhood in Abstraction Space¶

1-Center Problem sits in a moderately populated region (46^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Combinatorial Optimization & Game Problems (12 abstractions)

Nearest neighbors

Matroid-Constrained Number Partitioning — 0.88
Shephard's Lemma — 0.87
Round-Robin Scheduling — 0.86
Central Place Theory — 0.86
Quadratic knapsack problem — 0.86

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

1-median. Tell: Minimizes total or average distance.
k-center. Tell: Places multiple centers.
Maxmin location. Tell: Maximizes distance from demands.
Minimum-diameter spanning tree. Tell: Optimizes path diameter in a network structure.

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/1-center_problem (revision 1300232212).
Preserved source candidate: http://theory.stanford.edu/~megiddo/pdf/weight1.pdf

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.