Answer: Both objectives are exactly solvable in polynomial time in \(m,\tau,L\) with the stated oracle.
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor the general m number of facilities, the two optimization problems can be solved in O(n3m) time. Utilitarian Version With One Facility In this section, we study the one-facility game with the ob- jective of minimizing the total cost. We will first investigate upper and lower bounds for deterministic mechanisms and then turn our attention to randomized mechanisms.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\), sorted location types \(x_t\) with rational masses \(\mu_t\) summing to one, and a public entrance-fee oracle \(e\) supporting the minimizations required in Remark 1, compute exact facility locations minimizing either weighted total cost \(\sum_t \mu_t \min_j(|x_t - \ell_j| + e(\ell_j))\) or maximum positive-mass type cost.
A society is given by its support: \(\tau\geq1\) distinct sorted locations \(x_1<\cdots<x_\tau\in\mathbb{Q}\), each with a positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input specifies \(m=k\geq1\) homogeneous, uncapacitated facilities. Their locations \(\boldsymbol\ell\in\mathbb{R}^m\) may coincide or serve no mass.
A public fee function \(e:\mathbb{R}\to\mathbb{R}_{\geq0}\cup\{+\infty\}\) is finite somewhere. A type's cost is \(c_t(\boldsymbol\ell)=\min_{1\leq j\leq m}(|x_t-\ell_j|+e(\ell_j))\); equal-cost facilities are selected by smallest fee, then rightmost location.
The exact oracle evaluates \(e\) at rational locations and minimizes \(ae(z)+bz\) for binary integers \(a>0\), \(b\in\mathbb{Z}\), over closed intervals with rational or infinite endpoints. It reports infeasibility or unboundedness; otherwise it returns an attained minimum and a rational minimizer.
Finite evaluations and oracle outputs are binary rationals of length polynomial in \(L\) plus the query length, where \(L\) is the total binary input length. Count oracle calls at unit cost and all other computation at bit cost; state running times in \(m,\tau,L\).
Compute facility locations minimizing, separately, \(\sum_{t=1}^{\tau}\mu_t c_t(\boldsymbol\ell)\) and \(\max_{1\leq t\leq\tau}c_t(\boldsymbol\ell)\).
For each objective, is exact optimization polynomial-time solvable in \(m,\tau,L\) with this oracle, or is it NP-hard in this oracle model?
For a finite list of \(n\) agents, both objectives admit an \(O(n^3m)\) algorithm under exact, constant-cost fee-minimization access ([verified full version](https://arxiv.org/html/2204.11282v2)). No result settling the exact rational-mass formulation above was identified.
Both objectives are exactly solvable in polynomial time in \(m,\tau,L\) with the stated oracle. Binary rational masses can be handled directly by clearing denominators in oracle queries; no expansion into individual agents is needed.
The proof extends the consecutive-block approach in the cited [full version, Section 3.2](https://arxiv.org/html/2204.11282v2). We prove the structural property, attainment, correctness, and bit complexity explicitly.
For a facility profile, discard locations with infinite fee and merge coincident locations. If no finite-fee facility remains, both objectives are infinite. Such profiles cannot be optimal: placing every facility at any location where the fee is finite gives finite costs.
For two remaining locations \(u<v\), define their cost difference by
\[ D(x)=|x-u|+e(u)-|x-v|-e(v). \]
Equivalently, using the requested inline delimiters,
\(D(x)=|x-u|-|x-v|+e(u)-e(v)\).
The distance difference is \(u-v\) when \(x\leq u\), is \(2x-u-v\) when \(u\leq x\leq v\), and is \(v-u\) when \(x\geq v\). Thus \(D\) is nondecreasing.
Suppose types at \(x<y\) select \(v\) and \(u\), respectively. Their optimality implies \(D(x)\geq0\) and \(D(y)\leq0\). Monotonicity gives
\(0\leq D(x)\leq D(y)\leq0\).
Consequently, both facilities have equal minimum cost at both types. But the tie-breaking preference between these two facilities depends only on their fees and locations. It cannot favor \(v\) at one type and \(u\) at the other. This is a contradiction.
Therefore, the selected location is nondecreasing with the type’s location. Each used location serves a consecutive block of support indices. There are at most \(M:=\min\{m,\tau\}\) nonempty blocks.
This argument does not depend on the masses.
For \(1\leq i\leq j\leq\tau\), define
\(S_{ij}:=\min_{z\in\mathbb R}\sum_{t=i}^{j}\mu_t\bigl(|x_t-z|+e(z)\bigr)\).
We show how to compute its value and an attaining rational location using \(j-i+2\) oracle calls.
Write \(\mu_t=p_t/d_t\), where \(p_t,d_t\) are positive binary integers. Set
\(Q:=\prod_{t=1}^{\tau}d_t,\qquad w_t:=Q\mu_t\in\mathbb Z_{>0}\).
The bit length of \(Q\) is \(O(L)\), because the input contains all the denominator encodings. Each \(w_t\) also has bit length \(O(L)\).
Partition the real line into the following closed intervals:
For \(h\in\{i-1,\ldots,j\}\), let
\(A_{ij}:=\sum_{t=i}^{j}w_t>0\),
\(B_{ijh}:=\sum_{t=i}^{h}w_t-\sum_{t=h+1}^{j}w_t\),
\(C_{ijh}:=\sum_{t=h+1}^{j}w_tx_t-\sum_{t=i}^{h}w_tx_t\),
with empty sums equal to zero.
For every \(z\in I_h\), the absolute values expand to give
\(Q\sum_{t=i}^{j}\mu_t\bigl(|x_t-z|+e(z)\bigr)=A_{ij}e(z)+B_{ijh}z+C_{ijh}\).
Thus one legal oracle query, with integer coefficients \(a=A_{ij}\) and \(b=B_{ijh}\), computes the minimum of the variable part on \(I_h\). If its returned minimum is \(v_{ijh}\), the corresponding block value is
\((v_{ijh}+C_{ijh})/Q\).
Discard infeasible intervals and take the smallest returned block value.
On \(I_h\), the displayed identity and nonnegativity of the original costs imply
\(A_{ij}e(z)+B_{ijh}z\geq-C_{ijh}\).
Hence no feasible query is unbounded below. At least one interval is feasible, because the intervals cover \(\mathbb R\) and the fee is finite somewhere.
The oracle promise therefore gives an attained minimum and rational minimizer for every feasible interval. Taking the best interval computes \(S_{ij}\) and an attaining rational location, which we denote by \(s_{ij}\).
All block values and locations can consequently be computed with \(O(\tau^3)\) oracle calls.
For a block \(\{i,\ldots,j\}\), define
\(E_{ij}:=\min_{z\in\mathbb R}\max_{i\leq t\leq j}\bigl(|x_t-z|+e(z)\bigr)\).
The masses do not enter this objective.
For every \(z\), the largest distance among the block’s locations is attained at an endpoint. Indeed, if \(z\leq x_i\), it is attained at \(x_j\); if \(z\geq x_j\), it is attained at \(x_i\); and otherwise every block location lies between the two endpoints. Therefore,
\(\max_{i\leq t\leq j}|x_t-z|=\max\{|x_i-z|,|x_j-z|\}\).
Let \(h_{ij}:=(x_i+x_j)/2\). The block objective equals \(e(z)+x_j-z\) for \(z\leq h_{ij}\), and equals \(e(z)+z-x_i\) for \(z\geq h_{ij}\). Consequently,
\(E_{ij}=\min\left\{x_j+\min_{z\leq h_{ij}}(e(z)-z),\; -x_i+\min_{z\geq h_{ij}}(e(z)+z)\right\}\).
These are two legal oracle queries, with coefficients \((a,b)=(1,-1)\) and \((1,1)\), respectively.
On the left interval, \(e(z)-z\geq-h_{ij}\). On the right interval, \(e(z)+z\geq h_{ij}\). Thus neither feasible query is unbounded below. At least one is feasible, and the oracle promise supplies attained rational minima.
We obtain \(E_{ij}\) and an attaining rational location \(r_{ij}\) using two calls per block, hence \(O(\tau^2)\) calls overall.
We first optimize the independently assigned costs of consecutive blocks. Section 5 proves that this gives the original objectives, where types freely select facilities.
For \(q\geq1\) and \(j\geq q\), let \(U(q,j)\) be the minimum sum of weighted block costs over partitions of \(\{1,\ldots,j\}\) into exactly \(q\) nonempty consecutive blocks. Define \(V(q,j)\) analogously using the maximum of the block maximum costs.
Initialize
\(U(0,0)=V(0,0)=0\),
and set states with \(q=0<j\), or \(j<q\), to \(+\infty\).
The recurrences are
\(U(q,j)=\min_{q\leq i\leq j}\bigl(U(q-1,i-1)+S_{ij}\bigr)\),
\(V(q,j)=\min_{q\leq i\leq j}\max\bigl\{V(q-1,i-1),E_{ij}\bigr\}\).
To justify them, the last block of any such partition has a unique first index \(i\). The preceding indices form exactly \(q-1\) nonempty consecutive blocks. The sum objective combines their cost with \(S_{ij}\) by addition, and the maximum objective combines their cost with \(E_{ij}\) by taking the maximum. Conversely, every candidate in either recurrence defines a valid partition.
Compute the states for \(1\leq q\leq M\), and take
\(P_U:=\min_{1\leq q\leq M}U(q,\tau)\),
\(P_V:=\min_{1\leq q\leq M}V(q,\tau)\).
Both tables require \(O(M\tau^2)\) arithmetic operations and comparisons. Storing an attaining predecessor allows reconstruction of an optimal partition.
Two inequalities establish correctness without assuming that the reconstructed blocks remain the actual service blocks.
Consider any finite-cost profile. Section 1 partitions its types into at most \(M\) nonempty consecutive service blocks.
For a block \(\{i,\ldots,j\}\) served at \(z\), its weighted cost is at least \(S_{ij}\), by the definition of \(S_{ij}\). Summing over the service blocks gives
\(\sum_{t=1}^{\tau}\mu_tc_t(\boldsymbol\ell)\geq P_U\).
Likewise, the maximum cost on that block is at least \(E_{ij}\). Taking the maximum over service blocks gives
\(\max_{1\leq t\leq\tau}c_t(\boldsymbol\ell)\geq P_V\).
Profiles with infinite objective satisfy these lower bounds as well.
Take a partition attaining \(P_U\), and install one facility at \(s_{ij}\) for each of its blocks. Every type can use its designated block facility, so its actual minimum cost is at most its designated cost. Hence the actual weighted objective is at most \(P_U\). The preceding universal lower bound makes it exactly \(P_U\).
For the maximum objective, take a partition attaining \(P_V\), and install the corresponding facilities at \(r_{ij}\). Every designated block cost is at most \(P_V\), so every type’s actual minimum cost is at most \(P_V\). Again the universal lower bound gives equality.
If either construction uses fewer than \(m\) facilities, duplicate any installed location until there are exactly \(m\). Duplicating a location leaves every minimum cost unchanged.
Thus both algorithms return globally optimal rational facility locations. The argument also proves that both global optima are attained.
Every oracle query has length \(O(L)\):
The constants \(C_{ijh}\) have \(O(L)\) bits as well. To see this, let \(R\) be the product of the denominators of the input locations. Then \(R\) has \(O(L)\) bits, and all the constants can be represented over denominator \(R\). Prefix sums of \(w_t\) and \(w_tx_t\) permit their computation with constantly many rational operations per query.
By the oracle-output promise, there is a fixed polynomial bound \(H=\operatorname{poly}(L)\) on the lengths of returned numbers, reconstructed block values, and block locations.
A finite weighted dynamic-programming value is a sum of at most \(\tau\) block values. Representing such a sum over the product of their denominators takes \(O(\tau H+\log\tau)\) bits. A maximum-objective value is one of the block values and needs only \(O(H)\) bits. Since \(\tau\leq L\), all arithmetic and comparisons take polynomial bit time in \(L\).
With oracle calls charged at unit cost, the resulting bounds are:
| Objective | Oracle calls | Total running time |
|---|---:|---:|
| Weighted sum | \(O(\tau^3)\) | \(O\bigl((\tau^3+M\tau^2+m)\operatorname{poly}(L)\bigr)\) |
| Maximum cost | \(O(\tau^2)\) | \(O\bigl((\tau^2+M\tau^2+m)\operatorname{poly}(L)\bigr)\) |
Here \(M=\min\{m,\tau\}\), and the term involving \(m\) accounts for explicitly outputting all facility locations. The unspecified polynomial reflects the polynomial oracle-output-length bound in the premises.
The integers used in the weighted queries may have large numerical values, but their binary encodings have polynomial length. Their numerical magnitude causes no iteration or replication.
⟨structured verdict parsed — rendered above⟩
The prover resolves both objectives under the stated oracle promises. The argument is correct and self-contained; I found no major or minor mathematical issues.
For distinct finite-fee locations \(u<v\), the stated piecewise formula for \(D(x)\) is correct, including its signs. It makes \(D\) nondecreasing.
If \(x<y\) selected \(v\) and \(u\), respectively, optimality would imply \(D(x)\geq0\) and \(D(y)\leq0\). Thus both differences must be zero. Both facilities would then be cost minimizers at both types, and the fixed preference by fee and then location cannot select them in opposite orders. Other facilities do not invalidate this contradiction: selecting a facility requires it to prevail over every tied alternative.
Consequently, selected locations are nondecreasing and each used location serves a consecutive block. Removing infinite-fee facilities and merging coincident locations is legitimate for every finite-cost profile. The bound of \(M=\min\{m,\tau\}\) nonempty blocks follows.
Clearing denominators gives positive integer weights \(w_t=Q\mu_t\). On each stated interval, the identity
\(Q\sum_{t=i}^{j}\mu_t(|x_t-z|+e(z))=A_{ij}e(z)+B_{ijh}z+C_{ijh}\)
has the correct coefficients and constant term. It remains valid at shared endpoints.
Every query is legal because \(A_{ij}>0\) and \(B_{ijh}\) is an integer. There are exactly \(j-i+2\) intervals. The lower bound by \(-C_{ijh}\) rules out unboundedness below on every feasible interval. Coverage of the real line and finiteness of the fee somewhere guarantee a feasible interval.
The stated oracle promise therefore supplies attained rational minimizers. Selecting the smallest interval minimum correctly computes the global block minimum. No expansion into individual agents is used.
The farthest support location in a block is an endpoint. The midpoint \(h_{ij}\) correctly separates the two expressions \(e(z)+x_j-z\) and \(e(z)+z-x_i\).
Both integer-coefficient queries are legal. Their stated lower bounds follow from fee nonnegativity and the respective interval restrictions. At least one query is feasible, and the oracle guarantees attainment. This also covers singleton blocks, where \(h_{ii}=x_i\).
The recurrence ranges enforce exactly \(q\) nonempty consecutive blocks. Removing the last block leaves precisely the predecessor state stated in the proof; conversely, each finite predecessor and last block form a valid partition.
The initialization \(V(0,0)=0\) is appropriate because all block costs are nonnegative. Minimizing over \(1\leq q\leq M\) correctly permits fewer used facilities than the supplied number. The claimed \(O(M\tau^2)\) table computation and predecessor reconstruction are valid.
Every finite-cost profile induces an admissible partition, and its service-block costs dominate the corresponding independently optimized block costs. This establishes the universal lower bounds.
Conversely, installing the minimizers for an optimal partition makes each type’s actual minimum cost no greater than its designated cost. Combining this upper bound with the universal lower bound proves equality for each objective.
This argument correctly avoids requiring reconstructed blocks to remain the actual service blocks or reconstructed locations to be ordered. Duplicating a location preserves all minimum costs and supplies exactly \(m\) facilities.
Products of input denominators have \(O(L)\) bits. Moreover, \(\sum_t w_t=Q\), so the integer query coefficients have the asserted bit bounds. Using the product of location denominators also gives polynomial-length representations of the constants and prefix sums.
Query lengths are \(O(L)\), so the oracle-output promise bounds returned values and locations by a fixed polynomial in \(L\). Weighted dynamic-programming values sum at most \(\tau\) block values; the stated denominator-product bound ensures polynomial bit length. Maximum-objective values require no such accumulation.
The resulting oracle-call counts and total running times are valid, including the explicit output cost for \(m\) locations.
Both objectives are addressed, with attaining rational facility profiles. The edge cases \(\tau=1\), \(m=1\), and \(m>\tau\) are covered. No continuity or additional attainment assumption is silently imposed: attainment comes from the supplied oracle promise. The cited prior work is motivational; no external theorem is needed for the proof.
No repair or additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.