[Model] MinimumSumMulticenter

[isPANN]

Motivation

MIN-SUM MULTICENTER from Garey & Johnson, A2 ND51. A classical NP-complete facility location problem, also known as the p-median problem. Given a graph with vertex weights and edge lengths, the goal is to place K service centers so as to minimize the total weighted distance from all vertices to their nearest centers. Arises in optimal placement of warehouses, hospitals, schools, and other service facilities. Unlike the min-max variant (p-center), which minimizes the worst-case distance, the p-median minimizes average/total service cost.

Associated reduction rules:

• As target: R71 (DOMINATING SET -> MIN-SUM MULTICENTER)

Definition

Name: MinimumSumMulticenter
Canonical name: p-Median Problem; also: Min-Sum Multicenter, Uncapacitated Facility Location (variant)
Reference: Garey & Johnson, Computers and Intractability, A2 ND51

Mathematical definition:

INSTANCE: Graph G = (V,E), weight w(v) ∈ Z_0^+ for each v ∈ V, length l(e) ∈ Z_0^+ for each e ∈ E, positive integer K ≤ |V|, positive rational number B.
QUESTION: Is there a set P of K "points on G" such that if d(v) is the length of the shortest path from v to the closest point in P, then Sigma_{v in V} d(v)·w(v) ≤ B?

The optimization version asks: find K points on G minimizing the total weighted distance Sigma_{v in V} d(v)·w(v).

Variables

• Count: n = |V| binary variables (one per vertex). As noted by GJ, there is no loss of generality in restricting centers to vertices.
• Per-variable domain: binary {0, 1} — whether vertex v is selected as a center
• Meaning: variable x_v = 1 if vertex v is chosen as a center location. Exactly K variables must be set to 1. The configuration is valid if Sigma_{v in V} d(v)·w(v) ≤ B, where d(v) is the shortest weighted-path distance from v to the nearest selected center.
• dims() spec: vec![2; num_vertices] — n binary variables, one per vertex.

Schema (data type)

Type name: MinimumSumMulticenter
Variants: graph topology, weight type

Field	Type	Description
graph	SimpleGraph	The underlying graph G = (V, E)
vertex_weights	Vec<W>	Non-negative weight w(v) for each vertex v
edge_lengths	Vec<W>	Non-negative length l(e) for each edge e (used to compute shortest-path distances)
k	usize	Number of centers to place (K)
bound	W	Upper bound B on total weighted distance (for decision variant)

Size fields (getter methods for overhead expressions):

• num_vertices() → |V|
• num_edges() → |E|
• num_centers() → K

Notes:

• This is a satisfaction (decision) problem matching the GJ formulation: Metric = bool, implementing SatisfactionProblem.
• A configuration is satisfying if exactly K centers are selected and the total weighted distance Sigma_{v in V} d(v)·w(v) ≤ B.
• Per GJ comment: restricting P to a subset of V (vertex-restricted variant) does not lose generality for p-median.

declare_variants! guidance:

• Complexity string: "2^num_vertices" (brute-force enumeration of C(n, K) subsets; no specialized exact exponential algorithm improves on this for general p-median beyond ILP approaches).
• Note: This is the trivial enumeration bound. No faster specialized exact algorithm is known for general p-median.

Complexity

• Decision complexity: NP-complete (Kariv and Hakimi, 1979; transformation from DOMINATING SET). Remains NP-complete even with unit weights and unit edge lengths.
• Best known exact algorithm: O*(2^n) via brute-force enumeration of all C(n, K) vertex subsets with shortest-path distance computation. The p-median problem is typically solved in practice via integer linear programming with branch-and-bound. No specialized exact exponential algorithm is known that improves on the trivial bound for general p-median.
• Polynomial cases: Solvable in polynomial time for fixed K and for arbitrary K on trees (Kariv and Hakimi, 1979).
• Approximation: Constant-factor approximation by Charikar et al. (1999, 2002); best known ratio is (2+ε) by Cohen-Addad et al. (STOC 2022).
• References:
  • O. Kariv, S. L. Hakimi (1979). "An Algorithmic Approach to Network Location Problems. II: The p-Medians." SIAM J. Appl. Math., 37(3):539-560.
  • M. Charikar, S. Guha, E. Tardos, D. B. Shmoys (1999). "A Constant-Factor Approximation Algorithm for the k-Median Problem." Proc. 31st ACM STOC, pp. 1-10.

Specialization

• This is a special case of: General facility location / median location problems
• Known special cases:
  • Vertex p-median: centers restricted to vertices (no loss of generality per GJ)
  • Unweighted unit-length variant: w(v)=1, l(e)=1 (still NP-complete)
  • Tree graphs: polynomial-time solvable (Kariv and Hakimi, 1979)
  • Fixed K: polynomial-time solvable
• Related problems: MIN-MAX MULTICENTER (p-center, ND50) uses bottleneck objective instead of sum

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), weight w(v) ∈ Z_0^+ for each v ∈ V, length l(e) ∈ Z_0^+ for each e ∈ E, positive integer K ≤ |V|, positive rational number B.
QUESTION: Is there a set P of K "points on G" such that if d(v) is the length of the shortest path from v to the closest point in P, then Sigma_{v in V} d(v)·w(v) ≤ B?
Reference: [Kariv and Hakimi, 1976b]. Transformation from DOMINATING SET.
Comment: Also known as the "p-median" problem. It can be shown that there is no loss of generality in restricting P to being a subset of V. Remains NP-complete if w(v) = 1 for all v ∈ V and l(e) = 1 for all e ∈ E. Solvable in polynomial time for any fixed K and for arbitrary K if G is a tree.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all C(n, K) subsets of K vertices; for each subset, compute all-pairs shortest paths and evaluate Sigma_{v in V} d(v)·w(v). Check feasibility against B.
• It can be solved by reducing to integer programming. Binary variable x_v for each vertex (center selection) and assignment variables y_{v,u} for each vertex-center pair; minimize Sigma_{v,u} w(v)·d(v,u)·y_{v,u} subject to: each vertex assigned to exactly one center, assignment only to selected centers, exactly K centers.
• Other: Lagrangian relaxation with subgradient optimization; column generation / branch-and-price.

Example Instance

Graph G with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 8 edges, unit weights and lengths:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {0,6}, {2,5}
• K = 2, B = 6

All-pairs shortest distances (unit edge lengths), all w(v) = 1, l(e) = 1.

Optimal 2-median: Place centers at vertices {2, 5}.

• d(0) = dist(0, {2,5}) = min(dist(0,2), dist(0,5)) = min(2, 2) = 2
• d(1) = dist(1, {2,5}) = min(1, 2) = 1
• d(2) = 0 (center)
• d(3) = dist(3, {2,5}) = min(1, 2) = 1
• d(4) = dist(4, {2,5}) = min(2, 1) = 1
• d(5) = 0 (center)
• d(6) = dist(6, {2,5}) = min(dist(6,2), dist(6,5)) = min(2, 1) = 1

Total weighted distance = 2 + 1 + 0 + 1 + 1 + 0 + 1 = 6 ≤ 6 = B. Answer: YES.

For K = 2, B = 5: the minimum achievable total is 6 (verified by checking all C(7,2)=21 pairs). Answer: NO.

Prerequisite: Implementing this model requires MinimumDominatingSet to already exist in the codebase (for the planned reduction R71: DOMINATING SET -> MIN-SUM MULTICENTER). MinimumDominatingSet is already implemented.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; concrete planned reduction from DominatingSet
Non-trivial	✅ Pass	Distinct objective (minimize total weighted distance to nearest center) from all existing problems
Correctness	⚠️ Warn	References verified; complexity bound (O*(2^n)) is a generic ILP bound, not a specialized result
Well-written	⚠️ Warn	Minor issues: example has wrong intermediate calculation, schema missing B field for decision variant

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not exist in the codebase. It is GJ problem ND51 (p-median), a classical facility location problem with clear practical motivation (warehouse/hospital placement). The issue identifies a planned reduction from MinimumDominatingSet (R71), which would connect it to the existing reduction graph. The motivation section is substantive with concrete applications.

Result: Pass

Non-trivial

MinSumMulticenter has a genuinely distinct feasibility constraint and objective from all 26 existing problems. It combines shortest-path distance computation with subset selection (K centers) and a weighted sum objective. No existing problem captures this structure — it is not a variant of MinimumDominatingSet (which counts dominated vertices, not distances) or TravelingSalesman (which finds a tour, not facility locations).

Result: Pass

Correctness

References verified:

• Kariv and Hakimi (1979), "An Algorithmic Approach to Network Location Problems. II: The p-Medians," SIAM J. Appl. Math., 37(3):539-560 — confirmed at https://epubs.siam.org/doi/10.1137/0137041. The NP-completeness result and polynomial-time tree algorithm are correctly attributed.
• Charikar, Guha, Tardos, Shmoys (1999), "A Constant-Factor Approximation Algorithm for the k-Median Problem," STOC 1999, pp. 1-10 — confirmed at https://dl.acm.org/doi/10.1145/301250.301257.

Complexity bound: The issue states "O*(2^n)" as the best known exact algorithm, citing only generic ILP/branch-and-bound approaches. This is technically correct as an upper bound but uninformative — it is the trivial enumeration bound, not a specialized result. No faster exact exponential algorithm was found in the literature specifically for p-median. This is not wrong, just imprecise.

Result: Warn — the complexity bound is valid but could note that no specialized exact algorithm improves on brute force for general p-median.

Well-written

Template completeness: All required sections are present and substantive.

Issues found:

1. Example intermediate calculation error: For centers {2, 5}, the issue claims dist(6, 2) = 3. This is incorrect: with edges {5,6} and {2,5}, we have dist(6, 2) via 6→5→2 = 2, not 3. The final answer d(6) = 1 is still correct (since dist(6,5) = 1 dominates), but the intermediate value is wrong.

2. Messy example presentation: The example shows trial-and-error ("Wait -- that gives 6 > B=5. Let us try...") which reads like a draft, not a finished worked example. A clean example should present the final corrected instance directly.

3. Schema missing B field: The GJ definition is a decision problem with bound B, and the issue discusses both satisfaction and optimization formulations, but the schema table has no bound field for the decision variant. If implementing as a satisfaction problem (Metric = bool), the bound B must be stored somewhere.

4. Naming convention: The name MinSumMulticenter uses an abbreviated prefix. The project convention uses full Minimum/Maximum prefixes for optimization problems (e.g., MinimumVertexCover, MinimumDominatingSet). However, MaxCut and SpinGlass show abbreviated names are sometimes acceptable. This is a minor inconsistency.

5. Symbol consistency: The edge_lengths field stores per-edge lengths, but the distance computation uses shortest paths. The schema should clarify that edge_lengths stores raw edge weights, not distances. This is implicit but could be clearer.

Result: Warn — mostly well-written with minor fixable issues.

Recommendations

• Fix the example: present the corrected instance (B=6, K=2) cleanly without the trial-and-error narrative. Fix dist(6,2) = 2 (not 3).
• Decide on satisfaction vs optimization formulation and adjust schema accordingly. If satisfaction, add a bound field. If optimization, remove references to B.
• Consider the full prefix MinimumSumMulticenter for naming consistency, or explicitly note the abbreviated form.

[zazabap]

Changelog

Mechanical fix:

• Clarified edge_lengths field description to: "Non-negative length l(e) for each edge e (used to compute shortest-path distances)"

Substantive fix (Q1 — answer: A):

• Renamed MinSumMulticenter → MinimumSumMulticenter throughout the issue (title, struct name, type name, all references) to follow the project's explicit optimization prefix naming convention (e.g., MinimumVertexCover, MinimumDominatingSet, MinimumSetCovering).