d4-conf-sagt-2019-0012 (d4-conf-sagt-2019-0012)

Given \(B,\delta\in\mathbb{Q}_{>0}\) and a finite support \(T\) of interval types, with \(K_t=[a_t,b_t]\subseteq[0,B]\), \(b_t-a_t\leq\delta\), and rational masses \(\mu_t>0\) summing to \(1\), choose probability measures \(\nu_t\) supported on \(K_t\) to represent possible true locations within each type. Let \(\lambda=\sum_{t\in T}\mu_t\nu_t\). Compute an exact \(p^*\in[0,B]\) minimizing \(\sup_{(\nu_t)}[\int|x-p|\,d\lambda(x)-\min_{q\in[0,B]}\int|x-q|\,d\lambda(x)]\).

Given binary rationals \(B>0\) and \(0<\delta\leq B\), a society is given by its support: a nonempty list \(T\) of \(\tau\) interval types \(K_t=[a_t,b_t]\), with rational endpoints satisfying \(0\leq a_t\leq b_t\leq B\) and \(b_t-a_t\leq\delta\), and positive binary rational masses \(\mu_t\) summing to \(1\). The parameter \(\tau\) is the support size, not the number of possible types.
For each type, uncertainty permits any Borel probability measure \(\nu_t\) supported on \(K_t\), chosen independently across types; define \(\lambda=\sum_{t\in T}\mu_t\nu_t\).
For a facility location \(p\in[0,B]\), define \(R(p)=\sup_{(\nu_t)}\left[\int|x-p|\,d\lambda(x)-\min_{q\in[0,B]}\int|x-q|\,d\lambda(x)\right]\). The computational problem is to output any exact minimizer \(p^*\in\arg\min_{p\in[0,B]}R(p)\), using binary rational encoding.
Let \(L\) be the total input bit length, including endpoints, masses, \(B\), and \(\delta\). There is one facility and no separate candidate-count parameter \(m\); state running times in \(\tau\) and \(L\).

Is computing an exact minimizer of \(R\) solvable in polynomial time in \(\tau\) and \(L\), or is it NP-hard?

For the discrete version with \(n\) equally weighted agents, each having one unknown location in its reported interval, an exact minimax location for average distance can be computed in \(O(n\log n)\) arithmetic time. That result does not classify the distribution-over-types problem defined above.

Result

Computing an exact minimizer is polynomial-time solvable in \(\tau\) and \(L\). An algorithm uses \(O(\tau\log(\tau+1))\) arithmetic operations on \(O(L)\)-bit integers. A conservative bit-complexity bound is \(O(\tau\log(\tau+1)L^2)\).

The key is an exact reduction to two feasible societies: all mass at the left endpoints, and all mass at the right endpoints.

1. Exact reduction to endpoint societies

Define
\[ C_-(p)=\sum_t\mu_t|a_t-p|, \qquad C_+(p)=\sum_t\mu_t|b_t-p|, \]
and their optimal costs
\[ c_-=\min_{q\in[0,B]}C_-(q), \qquad c_+=\min_{q\in[0,B]}C_+(q). \]
Write \(f(p)=C_-(p)-c_-\) and \(g(p)=C_+(p)-c_+\).

Claim. For every \(p\in[0,B]\),
\[ R(p)=\max\{f(p),g(p)\}. \]

Proof. Fix a feasible \(\lambda\), and let \(C_\lambda(q)=\int|x-q|\,d\lambda(x)\). The inequality
\[ |C_\lambda(q)-C_\lambda(q')|\leq |q-q'| \]
shows continuity, so its minimum on \([0,B]\) is attained. Consequently, its regret at \(p\) is
\[ C_\lambda(p)-\min_q C_\lambda(q) =\max_q\int\bigl(|x-p|-|x-q|\bigr)\,d\lambda(x). \]

For fixed \(p,q\), put \(h_{p,q}(x)=|x-p|-|x-q|\).

If \(q\leq p\), this function equals \(p-q\) for \(x\leq q\), equals \(p+q-2x\) between \(q\) and \(p\), and equals \(q-p\) for \(x\geq p\). It is therefore nonincreasing. Since each \(\nu_t\) is supported on \([a_t,b_t]\),
\[ \int h_{p,q}(x)\,d\lambda(x) \leq\sum_t\mu_t h_{p,q}(a_t) =C_-(p)-C_-(q) \leq f(p). \]

If \(q\geq p\), the function equals \(p-q\) for \(x\leq p\), equals \(2x-p-q\) between \(p\) and \(q\), and equals \(q-p\) for \(x\geq q\). It is nondecreasing, giving
\[ \int h_{p,q}(x)\,d\lambda(x) \leq\sum_t\mu_t h_{p,q}(b_t) =C_+(p)-C_+(q) \leq g(p). \]

These two cases cover every comparison location \(q\). Taking the maximum over \(q\), and then the supremum over feasible measures, proves
\[ R(p)\leq\max\{f(p),g(p)\}. \]

Conversely, putting every type’s mass at its left endpoint is feasible and gives regret \(f(p)\). Putting every type’s mass at its right endpoint is feasible and gives regret \(g(p)\). Thus the reverse inequality holds. This proves the claim.

2. An equality point gives a global minimizer

Let \(\alpha\) and \(\beta\) be the lower weighted medians of the left and right endpoints:
\[ \alpha=\min\left\{a_t:\sum_{s:a_s\leq a_t}\mu_s\geq\frac12\right\}, \qquad \beta=\min\left\{b_t:\sum_{s:b_s\leq b_t}\mu_s\geq\frac12\right\}. \]

To verify the weighted-median property, on an open segment containing no left endpoint,
\[ C_-'(p)=2\sum_{t:a_t<p}\mu_t-1. \]
For \(p<\alpha\), the cumulative mass is less than \(\frac12\), so this slope is negative. For \(p>\alpha\), it is at least \(\frac12\), so the slope is nonnegative. Continuity and piecewise linearity therefore show that \(C_-\) is nonincreasing up to \(\alpha\), nondecreasing thereafter, and minimized at \(\alpha\). The same argument applies to \(C_+\) and \(\beta\). In particular,
\[ c_-=C_-(\alpha),\qquad c_+=C_+(\beta). \]

Moreover, \(\alpha\leq\beta\). Indeed, \(a_t\leq b_t\) implies
\[ \sum_{t:a_t\leq x}\mu_t\geq\sum_{t:b_t\leq x}\mu_t \]
for every \(x\). At \(x=\beta\), the right side is at least \(\frac12\), so the left weighted median is no larger than \(\beta\).

On \([\alpha,\beta]\), \(f\) is nondecreasing and \(g\) is nonincreasing. Define \(H=f-g\). It is continuous, and
\[ H(\alpha)=-g(\alpha)\leq0, \qquad H(\beta)=f(\beta)\geq0. \]
Hence there is a \(p^*\in[\alpha,\beta]\) with \(f(p^*)=g(p^*)\).

This point is a global minimizer. If \(p\leq p^*\), then \(p^*\leq\beta\) and the monotonicity of \(g\) gives
\[ R(p)\geq g(p)\geq g(p^*)=R(p^*). \]
If \(p\geq p^*\), then \(p^*\geq\alpha\) and the monotonicity of \(f\) gives
\[ R(p)\geq f(p)\geq f(p^*)=R(p^*). \]
These inequalities cover all \(p\in[0,B]\).

3. Finding the equality point exactly

Sort the left and right endpoints, compute their weighted medians, and evaluate \(c_-\), \(c_+\), and \(H(\alpha)\).

Merge the endpoint lists and retain the distinct coordinates in \([\alpha,\beta]\). Both \(\alpha\) and \(\beta\) occur in this list. Between consecutive coordinates \(z_i<z_{i+1}\), the slope of \(H\) is
\[ s_i= 2\left( \sum_{t:a_t\leq z_i}\mu_t - \sum_{t:b_t\leq z_i}\mu_t \right). \]
This follows by subtracting the slopes of the two absolute-distance costs. The inclusion
\[ \{t:b_t\leq z_i\}\subseteq\{t:a_t\leq z_i\} \]
also shows \(s_i\geq0\).

Maintain the two cumulative masses while scanning. Update values exactly by
\[ H(z_{i+1})=H(z_i)+s_i(z_{i+1}-z_i). \]

If a scanned coordinate satisfies \(H(z_i)=0\), output it. Otherwise, the endpoint signs guarantee consecutive coordinates with \(H(z_i)<0<H(z_{i+1})\). Here \(s_i>0\), and output
\[ p^*=z_i-\frac{H(z_i)}{s_i}. \]
Because \(H\) is affine on this segment, this is its exact zero. Section 2 proves optimality. The case \(\alpha=\beta\) immediately returns that common median.

Sorting takes \(O(\tau\log(\tau+1))\) arithmetic operations; all subsequent work takes \(O(\tau)\).

4. Binary encoding and bit complexity

We must additionally control intermediate and output sizes.

Let \(W\) be the product of the input mass denominators, and let \(X\) be the product of the endpoint denominators and the denominator of \(B\). Their bit lengths are \(O(L)\). Then
\[ w_t=W\mu_t,\qquad u_t=Xa_t,\qquad v_t=Xb_t \]
are integers, with \(\sum_t w_t=W\).

At every endpoint coordinate \(z_i=x_i/X\), the quantity \(h_i=WXH(z_i)\) is an integer, obtained from sums of weighted integer distances. Similarly,
\[ S_i=Ws_i= 2\left(\sum_{t:u_t\leq x_i}w_t-\sum_{t:v_t\leq x_i}w_t\right) \]
is an integer. The scan can therefore use
\[ h_{i+1}=h_i+S_i(x_{i+1}-x_i). \]
For a strict sign crossing, its output is the rational
\[ p^*=\frac{x_iS_i-h_i}{XS_i}. \]

All these integers have \(O(L)\) bits: coordinates lie between \(0\) and \(XB\), cumulative weights lie between \(0\) and \(W\), and weighted distance sums are at most \(WXB\). Thus the output numerator and denominator also have \(O(L)\) bits.

Using standard quadratic-time integer arithmetic gives the stated polynomial bound \(O(\tau\log(\tau+1)L^2)\). This argument works directly with the binary-encoded masses and does not expand them into equally weighted agents. It applies to every interval input satisfying the stated hypotheses.

⟨structured verdict parsed — rendered above⟩

The prover’s conclusion is correct: the write-up establishes a polynomial-time algorithm for computing an exact minimizer. No major or minor gaps were found.

1. Reduction to the two endpoint societies

The continuity argument is valid. Since every feasible measure is a probability measure, the pointwise reverse triangle inequality gives
\[ |C_\lambda(q)-C_\lambda(q')|\leq |q-q'|. \]
Thus \(C_\lambda\) is continuous on the compact interval \([0,B]\), and its minimum is attained. The displayed expression for regret as a maximum over comparison locations follows correctly.

Both piecewise formulas for \(h_{p,q}(x)\) are correct, including their boundary values:

• For \(q\leq p\), the function is nonincreasing, so its integral against each \(\nu_t\) is bounded above by its value at \(a_t\).
• For \(q\geq p\), it is nondecreasing, so the corresponding upper bound uses \(b_t\).

The resulting inequalities hold for every feasible choice of measures and every comparison location. Therefore taking the maximum over \(q\), followed by the supremum over measures, correctly gives
\[ R(p)\leq\max\{f(p),g(p)\}. \]
No interchange of optimization operations is needed.

For the reverse inequality, the choices \(\nu_t=\delta_{a_t}\) and \(\nu_t=\delta_{b_t}\) are feasible Borel probability measures. They realize regrets \(f(p)\) and \(g(p)\), respectively. Hence the claimed identity
\[ R(p)=\max\{f(p),g(p)\} \]
is fully established.

2. Weighted medians and global optimality

The lower weighted medians exist because the support is finite and nonempty, the masses are positive, and their sum is \(1\).

The derivative formula on segments without endpoints is correct. Below the lower weighted median, the cumulative mass is strictly less than \(1/2\); above it, the cumulative mass is at least \(1/2\). Continuity and piecewise linearity therefore justify the asserted monotonicity and the identities
\[ c_-=C_-(\alpha),\qquad c_+=C_+(\beta). \]
This reasoning also accommodates repeated endpoints and a cumulative mass exactly equal to \(1/2\), which can produce a flat interval of minimizers.

The argument for \(\alpha\leq\beta\) is valid: the coordinatewise inequalities \(a_t\leq b_t\) imply the stated cumulative-mass inequality for every \(x\).

On \([\alpha,\beta]\), the asserted monotonicity of \(f\) and \(g\) follows from their respective median properties. Their nonnegativity gives the endpoint signs for the continuous function \(H=f-g\). The existence of a zero follows from the intermediate value theorem.

The global-optimality argument is also valid. For every \(p\leq p^*\), both locations lie at or below \(\beta\), where \(g\) is nonincreasing. For every \(p\geq p^*\), both lie at or above \(\alpha\), where \(f\) is nondecreasing. Together with equality \(f(p^*)=g(p^*)\), these comparisons establish optimality over all of \([0,B]\).

3. Exact computation of an equality point

The merged list contains every breakpoint of \(H\) within \([\alpha,\beta]\), including both boundary coordinates. The slope formula is correct: between consecutive distinct coordinates, the cumulative endpoint masses are constant, and endpoints at the left boundary must be included.

The inclusion of index sets used to prove \(s_i\geq0\) is valid because \(a_t\leq b_t\) for each type.

The affine update
\[ H(z_{i+1})=H(z_i)+s_i(z_{i+1}-z_i) \]
is exact. If no scanned coordinate is a zero, the endpoint signs ensure a strict crossing between consecutive coordinates. Such a crossing forces \(s_i>0\), so the division in
\[ p^*=z_i-\frac{H(z_i)}{s_i} \]
is legitimate and returns a point inside that segment.

The case \(\alpha=\beta\) is handled correctly: the common coordinate minimizes both endpoint costs, so both regrets vanish there. Zero slopes, endpoint zeros, singleton intervals, and repeated coordinates cause no unhandled case.

4. Binary encoding and running time

The scaling construction is valid. Products of the input denominators have bit lengths bounded by their total encoded lengths, hence \(O(L)\). The scaled weights and coordinates are integers.

The claims that \(h_i=WXH(z_i)\) and \(S_i=Ws_i\) are integers follow directly from the scaled cost and slope formulas. The integer scan recurrence and the output formula
\[ p^*=\frac{x_iS_i-h_i}{XS_i} \]
are algebraically correct.

The stated magnitude bounds suffice to give \(O(L)\)-bit intermediate values. In particular, scaled distance sums are bounded by \(WXB\), slope numerators are bounded by \(2W\), and the output numerator and denominator consequently have \(O(L)\) bits.

Sorting, scaling, evaluating the initial costs, and scanning require the claimed number of arithmetic operations. Quadratic-time integer arithmetic therefore supports the conservative bound
\[ O\!\left(\tau\log(\tau+1)L^2\right). \]

The algorithm operates directly on rational masses and does not expand them into agents. Its proof applies to the full distribution-over-types model. The interval-length bound involving \(\delta\) is unnecessary for the argument, which is consistent with proving the result for every input satisfying the task’s hypotheses.

Assessment and feedback

The target is fully resolved. The endpoint reduction, minimizer characterization, exact algorithm, and bit-complexity analysis all stand as written. No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩