| paper | d4-conf-ijcai-2018-0086 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm{P}\), with running time \(\bigl(T(\tau+1)(k+T\tau)+L\bigr)^{O(1)}\) bit operations. · discrete side: parameterized · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(T\), \(k\), fixed starting locations \(y^0\in\mathbb{Q}^k\), total mass \(N>0\), and a rational distribution \(\mu\) over \(\tau\) types \(\theta=(w_\theta,x^\theta_1,\ldots,x^\theta_T)\), choose facility locations \(y^1,\ldots,y^T\in\mathbb{R}^k\) minimizing \(\sum_{t=1}^T\left(N\sum_{\theta=1}^{\tau}\mu_\theta w_\theta\min_{j\in[k]}|x^\theta_t-y^t_j|+\sum_{j=1}^k|y^t_j-y^{t-1}_j|\right)\).
An offline reallocation problem for \(k\) facilities on a line serving a nonatomic population of total mass \(N\), distributed over \(\tau\) types with shared weight and complete location trajectory; the decision variables are the facility locations at each stage, and the objective is mass-weighted service cost plus facility movement cost.
The continuous objective and feasible facility sequences are exactly those of a finite weighted instance after setting each supported type’s agent weight to \(N\mu_\theta w_\theta\), so the paper’s dynamic program already applies without new optimization structure.
fatal: False
The mirror covers the weighted offline multi-facility result, Theorem 2; it does not cover the single-facility results, the online competitive-ratio results, or the strategy-proof mechanism result.
My lead is a continuous weighted \(k\)-facility reallocation problem anchored in Theorem 2, proved in this paper. The theorem says that, for \(T\) stages, \(n\) explicitly listed agents with arbitrary weights, and \(k\) facilities on the line, an optimal offline reallocation can be computed in \(O(T^2(2\max\{Tn,k\})^{k+1})\) time. Thus it is polynomial for every fixed \(k\). The paper proves this result; it is not a citation to earlier work. This is the strongest anchor for a population mirror because it already allows weighted agents and preserves the multi-stage movement tradeoff.
Here is the mirror as a problem to hand to a prover. An instance gives \(T\), \(k\), starting facility locations \(y^0\in\mathbb Q^k\), a positive rational total population mass \(N\), and a distribution \(\mu\) over \(\tau\) types, with \(\sum_\theta\mu_\theta=1\). Each type \(\theta\) consists of a rational importance weight \(w_\theta\) and a complete location trajectory \((x^\theta_1,\ldots,x^\theta_T)\in\mathbb Q^T\). The mass \(N\mu_\theta\) consists of agents sharing that weight and entire trajectory. Choose facility locations \(y^1,\ldots,y^T\in\mathbb Q^k\) to minimize
\[
\sum_{t=1}^T\left(
N\sum_{\theta=1}^{\tau}\mu_\theta w_\theta
\min_{j\in[k]}|x^\theta_t-y^t_j|
+\sum_{j=1}^k|y^t_j-y^{t-1}_j|
\right).
\]
A solution is an optimal sequence of facility locations. When \(N=n\) and \(\mu_\theta\) is the fraction of the \(n\) agents in type \(\theta\), this is exactly the paper’s objective for that discrete population. Fractional masses extend it to nonintegral cohort sizes.
A natural regime is a large electorate whose political opinions lie on the paper’s one-dimensional spectrum. The \(k\) facilities are party members’ positions; voter cost is distance to the nearest member, and movement cost captures the cost of changing their positions. Types are voter weight and opinion trajectory over the election stages. Millions of voters may then be represented by a much smaller \(\tau\) of recurring trajectories. This is a credible high-multiplicity scenario when voter blocs share the same modeled path and weight. It also matches the paper’s underlying question: it retains the same line, stages, nearest-facility service cost, facility movement cost, and offline choice across stages. The population distribution is the object being continuized.
I expect this mirror to be tractable for fixed \(k\). Theorem 2’s proof uses the fact that an optimal solution can be found among facility positions drawn from the starting locations and the agents’ locations across stages, then applies dynamic programming. With \(\tau\) supported trajectories, there are only \(O(T\tau+k)\) such candidate coordinates. Aggregating the weighted cost by type gives the same kind of dynamic program, with a running-time bound of the theorem’s form after replacing \(n\) by \(\tau\): \(O(T^2(2\max\{T\tau,k\})^{k+1})\) arithmetic operations, plus polynomial bit complexity in the rational input length \(L\). This is polynomial in \(T,\tau,L\) for each fixed \(k\), though it does not establish a polynomial-time algorithm when \(k\) is part of the input. A further question is whether the dependence on \(k\) can be improved to an FPT bound, or shown necessary by a parameterized lower bound.
The scope here is the paper’s offline weighted multi-facility result, Theorem 2. I would not claim that this mirror covers the online competitive-ratio results or the strategy-proof mechanism: online decisions cannot use complete future trajectories, and a single agent’s deviation behaves differently in a nonatomic population. Nor does this anchor show that continuous populations dissolve a discrete hardness result. This paper provides no comparable numbered hardness result for the one-dimensional reallocation problem; its applicable anchor is an algorithmic theorem.
The weakest point is that sharing a full trajectory and weight across all stages can be a demanding assumption, and when nearly every agent has a distinct trajectory, \(\tau\) approaches \(N\) and the support compression buys little. Also, the discrete problem in Theorem 2 is already polynomial for fixed \(k\). So the case is strongest as a faithful continuous, support-based formulation of the authors’ weighted offline problem—not as a claim that continuization makes this particular problem tractable.
Theorem 2 is the proponent’s strongest anchor, and the population scenario is plausible. The problem is that its proposed continuum adds no new optimization model: its masses are already represented by the paper’s arbitrary agent weights.
For each type \(\theta\), set \(\bar w_\theta=N\mu_\theta w_\theta\). Then, for every facility sequence \(y\), the continuous objective is exactly the weighted objective of the paper’s instance with one agent per supported type:
\[ \sum_{t=1}^T\left( \sum_{\theta=1}^{\tau}\bar w_\theta \min_{j\in[k]}|x^\theta_t-y^t_j| +\sum_{j=1}^k|y^t_j-y^{t-1}_j| \right). \]
The feasible facility sequences are also identical. This is stronger than saying the continuous problem might have the same answer: it is the same optimization problem under a change of representation. Theorem 2 already permits the weights needed for that representation, and its dynamic program can use the \(\tau\) supported types as its agents. Rational masses add bit lengths to the coefficients; they do not add a new population-level decision.
A stronger mirror could drop the assumption that people share full trajectories. But the objective uses identity only through each stage’s location and weight; it does not couple an agent’s costs across stages. It therefore depends only on the weighted location distribution at each stage. Allowing separate cohorts at each stage changes the description, not the essential optimization: the paper’s candidate-location and dynamic-programming argument works with those stagewise supports too. People are never allocated or split by the algorithm, so fractional mass introduces no new decision structure.
Electorate blocs and recurring customer cohorts are sensible high-multiplicity regimes. They do not rescue this anchor: in either case, aggregate each cohort’s contribution into a weight and apply the paper’s result. A substantial new problem would need an identity-dependent cross-stage cost, a decision that reallocates people, or a succinct non-atomic input model. The first two change the paper’s objective; the last changes the input framework beyond a finite supported population.
The negative case is weakest if ChoCo counts a formal high-multiplicity encoding and its bit-complexity corollary as worthwhile in their own right. That could be a useful application. But for Theorem 2, the computational question and its solution are already contained in the paper’s weighted model, so this looks more like an immediate representation corollary than a distinct continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.