| paper | d4-conf-ijcai-2019-0123 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Exactly solvable in deterministic polynomial time; therefore the requested \((1-1/e-\epsilon)\)-approximation is computable with success probability \(1\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Corollary 1
statement extracted from the paper’s text layer
Given types \(T\) with rational masses \(\mu_t\), seed types \(A\), baseline LTM predecessor probabilities \(p^0_{st}\), and explicit feasible integral link bundles \(\mathcal K_t\) with added probabilities \(\eta_s(K)\), choose fractions \(y_{tK}\) summing to \(1\) for each non-seed type, subject to the per-capita budget \(\sum_{t\notin A}\mu_t\sum_{K\in\mathcal K_t}y_{tK}|K|\le\beta\), to maximize activated mass. For each bundle, define activation by \(h_{tK}=\sum_{s\in A}(p^0_{st}+\eta_s(K))+\sum_{s\notin A}p^0_{st}\bar h_s\), with \(\bar h_s=\sum_K y_{sK}h_{sK}\) and seed activation equal to \(1\); use the least nonnegative solution. Is a \((1-1/e-\epsilon)\)-approximation computable in time polynomial in the number of types \(\tau\), the number of listed bundles \(\kappa\), input bit length \(L\), and \(1/\epsilon\), or does this model admit a stronger algorithm or a hardness classification?
A well-mixed typed LTM network with rational population masses, per-type distributions over integral seed-to-recipient link bundles, a per-capita budget, and activated mass as the objective.
It targets Corollary 1 and Theorem 1’s submodularity basis in a typed block regime; it leaves Theorem 2’s LSS reduction, heuristic speedups, experiments, and the cited prior ICM results alone.
My lead is a continuous version of LTM Influence Maximization with Augmentation. The anchor is Corollary 1, proved in this paper: for any \(\epsilon>0\), Algorithm 1 gives a \((1-1/e-\epsilon)\)-approximation for IMA under LTM. The underlying discrete problem has a weighted directed graph, a seed set \(A\), and a budget \(B\); it adds at most \(B\) edges from the eligible set \(\bar E\setminus E\), subject to the LTM incoming-weight constraint, to maximize the expected number of activated nodes. Theorem 1, also proved here, supplies the key property: this expected-spread objective is monotone and submodular in the added-edge set. It supports the anchor, but I would not count it as a separate mirror. The paper mentions an ICM hardness result from earlier work, but it is not a numbered result of this paper, so it is not my anchor.
Here is a regime where the population limit seems sensible. Imagine a large platform recommending connections from a set of content creators to potential recipients. Recipients fall into a modest number of cohorts—say, by topic, region, and engagement pattern—with the same LTM influence profile, recommendation cost, and link weights within each cohort. Seed status is part of a type: every member of a seed type is initially active. There are \(N\) users, \(N\gg\tau\) types, and the number of recommendations scales with population, \(B/N\to\beta\). A finite platform still sends each person whole links; the continuum records the fraction of each cohort assigned each bundle of links.
Call the resulting problem Type-Continuous LTM Augmentation. An instance has a finite type set \(T\), rational masses \(\mu_t\) summing to one, seed types \(A\subseteq T\), and baseline LTM predecessor probabilities \(p^0_{st}\): a type-\(t\) user selects a live predecessor of type \(s\) with probability \(p^0_{st}\), with \(\sum_s p^0_{st}\leq1\). For each non-seed type \(t\), the instance also specifies its feasible integral bundles \(\mathcal K_t\) of new links from seed types. A bundle \(K\) has cost \(|K|\) and adds predecessor probability \(\eta_s(K)\) from seed type \(s\); it is feasible only if \(\sum_s p^0_{st}+\sum_{s\in A}\eta_s(K)\leq1\). Thus the probability weights and feasible links are part of the type description.
The decision is a distribution \(y_{tK}\geq0\), where \(y_{tK}\) is the fraction of type-\(t\) mass assigned bundle \(K\), and \(\sum_{K\in\mathcal K_t}y_{tK}=1\). The per-capita budget is
\[
\sum_{t\notin A}\mu_t\sum_{K\in\mathcal K_t}y_{tK}|K|\leq\beta.
\]
For each post-recommendation type \((t,K)\), let \(h_{tK}\) be its activation probability, and let \(\bar h_s=\sum_{K\in\mathcal K_s}y_{sK}h_{sK}\) be the average activation probability of type \(s\). Seed types have activation probability \(1\); for non-seed types, the LTM live-edge model gives
\[
h_{tK}=\sum_{s\in A}\bigl(p^0_{st}+\eta_s(K)\bigr)
+\sum_{s\notin A}p^0_{st}\bar h_s,
\]
taking the least nonnegative solution when the equations have multiple solutions. The objective is to maximize the activated mass,
\[
\sum_{t\in A}\mu_t+\sum_{t\notin A}\mu_t\bar h_t.
\]
The requested output is a feasible \(y\) whose objective is at least \((1-1/e-\epsilon)\) times optimal, or a classification showing whether that guarantee is achievable in time polynomial in \(\tau\), the number of listed bundles \(\kappa=\sum_t|\mathcal K_t|\), the input bit length \(L\), and \(1/\epsilon\).
I expect this to be Class A for approximation, though the paper does not establish that conclusion for this model. Its LTM anchor identifies monotone diminishing returns as the source of the discrete guarantee; the continuous question is whether that structure survives when the decision is a distribution over integral bundles. With many exchangeable users, a type-level algorithm could work in \(\tau\) and \(\kappa\) rather than in \(N\). The main follow-up is to prove or refute that lift, then bound how well a finite population with \(n_t/N\approx\mu_t\) realizes the continuous solution.
This mirrors the paper’s LTM contribution specifically: a fixed seed population, a budget of new seed-to-recipient connections, and expected spread as the objective. It does not claim to mirror the paper’s ICM discussion or its running-time heuristics. The stochastic diffusion model is retained; the population is what becomes continuous.
My weakest point is that this is a typed, well-mixed network regime. The mirror compresses individual graph neighborhoods into predecessor probabilities between types, and Theorem 1’s submodularity over discrete edge sets does not automatically imply the needed property over bundle distributions. If influence depends on highly distinctive neighborhoods, the number of meaningful types may approach \(N\), defeating the high-multiplicity premise. But for platforms with large, stable cohorts and common transmission profiles, the model preserves the paper’s central optimization question closely enough that its authors could reasonably recognize it as an LTM augmentation problem.
Corollary 1 is a real computational anchor: it gives an approximation guarantee for a problem proved here. The strongest objection is that its decision variables are particular edges in a particular graph. Under LTM, the value of adding an edge depends on where its recipient sits in the network: which paths it opens, which reachable sets it overlaps, and how its activation can spread onward. Theorem 1 establishes diminishing returns for those edge sets. It does not establish that users can be pooled by cohort without changing the optimization problem.
For an exact high-multiplicity type, swapping two people of that type must leave the spread objective unchanged under every feasible augmentation. In a typical social graph, that requires capturing their network positions and neighborhoods, not merely their topic, region, or average influence profile. Those details are usually different for each user, so the number of exact types can approach the population size. Coarser types may be useful approximations, but then the model has discarded information the algorithm optimizes over.
The proposed type model makes compression possible by replacing the graph with block-level predecessor probabilities. That is a legitimate model in its own right, but its equations summarize how mass moves between cohorts; they do not preserve the particular reachability patterns in \(G(S)\). A more faithful continuous limit might retain a graphon or another network limit object. But for sparse, heterogeneous networks, preserving the paths and neighborhoods that determine spread requires a richer object and encoding than a short list of rational type masses. If that encoding effectively retains each user’s position, the hoped-for high-multiplicity compression is gone; if it averages positions away, the problem has changed. The fixed-graph approximation result does not itself resolve that modeling tradeoff.
This is a substantial objection to the mirror as a general account of the paper’s result, but it does not defeat the best scenario. In a large, genuinely exchangeable block network, cohorts could have shared transition profiles and a per-capita recommendation budget; assigning each person an integral bundle while recording cohort-level fractions is coherent. The proponent’s model is a plausible instance of that regime, and the fact that its solution might be simple would not make the question unworthy. So the negative case is strongest against treating Corollary 1 as naturally continuizable for ordinary graph instances. It is weak against the user’s universal standard: a convincing symmetric-network scenario may survive, and I cannot honestly rule out a worthwhile mirror there.
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.