Submodular Facility Location Can’t Be Approximated Too Well (at least with only value queries)

Submodular Facility Location Can’t Be Approximated Too Well (at least with only value queries)

Introduction: the log-log barrier for submodular facility costs

Submodular facility location (often shortened to SFL) is the kind of problem that shows up whenever you want to serve clients using “bundling-friendly” economies of scale. Think: serving a cluster of customers together should be cheaper than serving them one-by-one, but the savings have diminishing returns—exactly what submodularity captures.

This new blog-friendly punchline comes from fresh research by Adam N. Elmachtoub, Bento Natura, and Meike Neuwohner, based on their paper “Settling the Approximability of Submodular Facility Location”. Their main result is a lower bound saying that the best-known approximation guarantee is basically the best you can hope for—up to constant factors—in a standard algorithmic access model (the value-oracle model) for submodular functions.

Earlier, Abbasi et al. (ICALP 2024) improved the approximation factor to roughly
O(log log |C|) · O(log log |C|) (more precisely: O(log log |𝒞|) · O(log log |𝒞|) as stated in the abstract) by designing an LP-rounding approach. The new work shows you cannot beat that asymptotic order—again, in the value-oracle model and even with unlimited computation time—without using substantially more “information” about the submodular function than polynomially many value queries.

Why This Matters: approximation limits that actually shape what algorithms you can build

Here’s the real-world relevance: many optimization systems rely on structured cost models—and submodular functions are one of the most popular structures because they encode “diminishing returns” naturally. In practice, you might be using a black-box simulator or pricing function for facility opening costs, and you can query it on sets (“What does it cost to serve this bundle?”) but you don’t know its internal formula.

So the key question isn’t just “can we approximate well?” It’s: how much can we learn from limited interaction? This paper answers that hard question for SFL in the most common interaction model: value-oracle access. If your system can only query the cost function on sets (like “pricing for a chosen client subset”), then this research says there’s an unavoidable approximation barrier around the log log regime.

A concrete scenario you can map today

Imagine a company placing “service hubs” for customers, where:
- connecting a customer to a hub costs distance/time,
- opening/using a hub has a cost that depends on which customers it serves,
- and that opening cost has diminishing returns because operational efficiencies saturate.

In many deployments, that hub operating cost might be computed by an external tool, rules engine, or learned component—meaning your algorithm can query it on subsets, but it’s not giving you derivatives, gradients, or a fully explicit representation. The lower bound here implies: if you stick to polynomially many subset-cost queries, then you shouldn’t expect a fundamentally better approximation factor than the known O(log log |𝒞| · log log |𝒞|)-type bound (up to constants).

How it builds on—and tightens—previous AI/optimization threads

There’s been a long line of “oracle model” lower bounds across submodular optimization and approximation. What’s new is the matching tightness: Abbasi et al. got the improved upper bound; Elmachtoub–Natura–Neuwohner now show you can’t asymptotically do better using only value queries. That means future work that claims better approximation guarantees likely needs to change something fundamental:
- the oracle model (more access than values),
- the function class (more structure than general submodular / even matroid rank),
- or the problem formulation (different LP relaxations/constraints or additional information).

Main result in plain language: the best-known approximation is “oracle-tight”

At a high level, the paper proves two main barriers:

1. Query-based hardness: in the value-oracle model, no polynomial-query algorithm can achieve approximation ratio better than
   o(log log |𝒞|) · o(log log |𝒞|) (asymptotically smaller than the known best order).

2. LP relaxation tightness: the natural configuration LP used in the best-known algorithm has an integrality gap of
   Θ(log log |𝒞|) · Θ(log log |C|) (matching the scale of the approximation upper bound, again up to constants).

These are not just “hard instances exist”—the paper builds them carefully so that an algorithm making few oracle calls can’t tell which hidden structure is present.

Below are the key ideas, unpacked without drowning you in notation.

Section 1: Submodular facility location with shared economies of scale

The starting point is metric facility location, where each client connects to some facility, paying connection costs based on distance.

In submodular facility location, each facility doesn’t have a fixed opening fee. Instead, the cost depends on the set of clients served by that facility. Formally, each facility f serving a subset S ⊆ 𝒞 pays a cost g(S), where g : 2^𝒞 → ℝ≥0 is:

• monotone: serving more clients doesn’t reduce facility cost,
• submodular: marginal increases show diminishing returns.

The “homogeneous” version studied in this line of work (and used here) assumes every facility shares the same submodular function g. This is crucial: it makes the problem about how well you can allocate clients when facility costs share one economies-of-scale model.

Why submodularity is the right modeling abstraction

A simple analogy: suppose a facility represents a logistics network. Adding the first few clients might require heavy coordination and setup, but after that, adding more clients can reuse routes, staff, or warehouses. Submodularity is the abstract “diminishing marginal cost” property for exactly that behavior.

The value-oracle model: limited cost information

The paper works in the value-oracle model: the algorithm can ask for g(C) for chosen subsets C ⊆ 𝒞. It gets answers, but it never sees the full structure of g.

That matters because lower bounds here are stronger: even with unlimited compute time, if you can’t query enough to learn hidden information, you can’t overcome the approximation barrier.

Section 2: Why symmetry hiding breaks “few queries can still learn everything”

The core technique is a clever twist on symmetry-based lower bounds (in the spirit of Vondrák’s symmetry-gap approach).

The intuition: “there are cheap solutions, but you can’t find the right one”

The authors imagine a setting where:

• there exists a much cheaper assignment, but
• the cheaper solution requires knowing some hidden pattern about how client groups must be split,
• and any algorithm that makes only polynomially many oracle queries doesn’t get enough information to recover that pattern.

So the algorithm is forced to output something that looks like a whole-orbit assignment—where symmetric client clusters stay together—despite the fact that splitting them appropriately would have been cheaper.

Orbits: symmetry classes of clients

The paper sets up a permutation group Γ acting on clients. Clients in the same orbit are indistinguishable under the symmetry.

A “whole-orbit assignment” sends every orbit to a single facility, while a “splitting assignment” breaks orbit structure and (in the constructed instances) becomes dramatically cheaper.

How they hide the splitting structure with replication

Here’s the main trick that makes the lower bound robust against limited querying:

• They replicate each client many times.
• The replicated copies are grouped into blocks, and each copy is connected to the facilities in a symmetric way.
• The key hidden information is: which copies correspond to which original client labels.

The facility cost function is then designed so that:
- if you guess correctly (i.e., you effectively learn the hidden partition), you can construct a cheap splitting assignment;
- if you can’t tell (most algorithms under polynomial queries), your queries “look the same” under a hidden oracle versus a public reference oracle.

That’s how the symmetry-gap turns into an information-theoretic lower bound for approximation.

Section 3: The submodular cost they use is even a matroid rank function

A particularly strong part of the result is that the hardness doesn’t rely on exotic submodular behavior. The authors prove the lower bound not just for arbitrary monotone submodular functions, but also for a very structured subclass:

matroid rank functions.

Matroid rank functions are among the most studied structured submodular functions. They capture “independence-like” combinatorial structure and appear naturally in many optimization settings.

So the message is: even when you restrict g to something as nice as a matroid rank function, the oracle-model approximation barrier remains.

Section 4: Two matching barriers—approximation hardness and LP integrality gap

This paper doesn’t only say “algorithms can’t do it.” It also shows the standard LP relaxation is inherently limited.

The configuration LP and why it matters

Abbasi et al. (ICALP 2024) built a rounding scheme based on the configuration LP. In facility location, the LP tries to represent fractional assignments by choosing “configurations” at each facility: which subset of clients a facility could serve.

If an LP has a large integrality gap, then even perfect rounding of the LP solution can’t yield a fully integral assignment without losing a factor.

What this paper proves about the gap

The authors show:

• ConfLP integrality gap is Θ(log log |𝒞|) · Θ(log log |C|) (same order as the known approximation).
• and the query lower bound aligns with the approximation upper bound order.

So the story becomes very tight:
- best-known algorithm matches the LP analysis,
- and the LP analysis can’t be improved asymptotically without changing the method (or the model).

Comparison: what’s known vs what this paper settles

(That table is aligned with the abstract-level statements in the paper, plus the concrete “matching” claims about approximation and integrality gap.)

Section 5: How the constructed instances create an exponential-feeling “cover” gap

The construction is combinatorial and graph-based. A key component is a carefully designed bipartite graph with:

• large cover number (hard to “cover” left vertices via neighborhoods),
• expansion properties on small sets (neighborhoods behave predictably enough to control submodularity).

A useful intuition

Think of facilities as right-side vertices and clients as left-side vertices. Serving a set of clients via some facility depends on which neighborhoods are “covered” in the graph.

A cheap assignment corresponds to a way of choosing neighborhoods that effectively covers clients efficiently—but only if you can exploit the hidden structure. If you must treat whole symmetry blocks together, the “cover cost” balloons.

Why matroid rank functions show up

The cover-number expression isn’t submodular “as-is,” so the authors replace it with a matroid rank function that matches it closely on the relevant scale. They also cap the value to keep the function submodular and to ensure it stays within the behavior needed for the symmetry-gap argument.

This is the part that makes the result especially clean philosophically: the construction doesn’t just prove hardness for bizarre functions—it engineers structured submodular costs that still encode the hard combinatorics.

Key Takeaways

• The best known approximation factor for submodular facility location is asymptotically optimal in the value-oracle model. You can’t do better than the existing O(log log |𝒞|) · O(log log |C|)-type order (up to constants).
• The hardness result holds even for matroid rank facility cost functions, meaning it survives strong structural restrictions.
• The configuration LP used to get the best-known algorithm has an inherent integrality gap of Θ(log log |𝒞|) · Θ(log log |C|), so the LP-based approach is essentially tight.
• The technique turns a symmetry gap into an information-theoretic oracle lower bound by replicating clients and hiding a crucial partition using a public reference function vs a hidden function.
• Practical implication: if your facility-opening cost behaves submodularly and you can only query its value on subsets, then expecting asymptotically better approximation guarantees than the known log log-regime is unrealistic without changing the access model or exploiting additional structure beyond “submodular.”

If you want, I can also translate the symmetry-gap + replication trick into a more concrete “toy model” example (with tiny sets) so you can literally see why few oracle queries can’t reveal the hidden splitting.