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.

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. Inclusion test: Specify demands, one-center feasible region, cost function and weights, then minimize the maximum demand cost and report both center and optimal radius. Exclusion test: Exclude sum-of-distance location, multiple-center location, maximizing remoteness, and smallest enclosing shapes under unrelated containment rules. Nearest boundary: The 1-median minimizes aggregate cost and can sacrifice an outlier; the 1-center minimizes the worst cost and is driven by extreme demands. Exit condition: It leaves the class when the objective is not a maximum over demand-to-one-center costs or the number of facilities exceeds one. Common misclassifications: 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. Nearest named distinctions: 1-median: Minimizes total or average distance. k-center: Places multiple centers. Maxmin location: Maximizes distance from demands. Minimum-diameter spanning tree: Optimizes path diameter in a network structure.

Manages Complexity

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

Abstract Reasoning

1. Define demand points and feasible locations.
2. Choose cost and any weights.
3. Express the maximum cost for a candidate center.
4. Minimize that radius by geometric, combinatorial, or convex methods.
5. 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.

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