| paper | d4-conf-ecai-2012-0134 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Yes; deterministic polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a matroid activity instance \(M=(X,\mathcal F)\), nonnegative revenue weights \(w\), \(p\) visitor types of equal mass \(1/p\) identified with activity labels, and a positive integer \(k\), compute an integral base \(B\) whose revenue is at least \((k-1)/k\) of the maximum base revenue and whose served population mass is at least \(1/k\) of the maximum mass any base can serve. A type is served when \(B\) contains an activity with its label.
The society is a distribution over visitor types \(\ell\), each type having mass \(\mu_\ell\); choosing an integral feasible activity base \(B\) earns \(R(B)=\sum_{e\in B}w(e)\) and serves mass \(U_\mu(B)=\sum_{\ell\in L(B)}\mu_\ell\).
The cohort formulation preserves exactly the feasible plans and approximation ratios of the paper's weighted label-coverage model, so it contributes a population interpretation rather than a distinct algorithmic landscape.
fatal: False
The proposed mirror covers Theorem 3's equal-cohort tradeoff guarantee and Lemma 2(b)'s equal-cohort boundary, plus Theorem 2's lexicographic result for arbitrary rational cohort masses; it leaves Theorem 1 and the remaining Pareto and complexity results unclaimed.
The strongest mirror is a crowded version of the paper’s own travel-agency example. Suppose a municipality schedules activities for a very large visitor population. Each visitor belongs to a category type \(\ell\), with mass \(\mu_\ell\), and gets utility \(1\) if the itinerary includes an activity of that category and \(0\) otherwise. The types are complete for this problem: people of the same type have the same preferences and relevant parameters. If there are \(N\) visitors but only \(\tau\) types, with \(N\gg\tau\), the society is naturally represented by the binary-rational distribution \(\mu\), where \(\sum_\ell\mu_\ell=1\).
An activity plan is still an integral base \(B\) of the paper’s matroid: for example, a schedule assigning activities to available days. Let \(L(e)\) be an activity’s category and \(w(e)\) its revenue. The agency’s revenue is \(R(B)=\sum_{e\in B}w(e)\), while the fraction of the population served is \(U_\mu(B)=\sum_{\ell\in L(B)}\mu_\ell\). Thus the continuous object is the population; the schedule remains discrete. For the paper’s label-gain objective, setting \(g(\ell)=\mu_\ell\) makes \(g(B)=U_\mu(B)\).
My lead is Theorem 3 (proved in this paper). It says that, in the uniform case \(g(\ell)=1\), the polynomial-time algorithm 3-PHASES returns a base that is a \(((k-1)/k,1/k)\)-approximation for every positive integer \(k\) supplied as input. The ratios are measured against, respectively, the maximum revenue of any base and the maximum number of labels represented by any base. The continuous mirror is Uniform-Cohort Matroid Tradeoff: given a matroid activity instance, a society with \(p\) equally sized label types \(\mu_\ell=1/p\), and \(k\), find a base \(B\) with \(R(B)\ge (k-1)R^*/k\) and \(U_\mu(B)\ge U_\mu^*/k\). Because \(U_\mu(B)=|L(B)|/p\), the second ratio is exactly the paper’s label-count ratio. I expect this mirror to be tractable, in Class A; the theorem’s algorithm and proof carry over directly.
Lemma 2(b) (also proved here) gives a boundary for that tradeoff. In the uniform case, for every \(\alpha>0\) and \(\beta>1/2\), the paper exhibits an instance with no \((\alpha,\beta)\)-approximate base. Its two-label graphic-matroid example has ideal point \((2,2)\): requiring more than half of the maximum label count forces both labels, and every such spanning tree has zero weight. In the population mirror, the two types each have mass \(1/2\), so serving more than half of the maximum population requires serving both types; that forces zero agency revenue. The corresponding Uniform-Cohort Threshold Feasibility problem takes an instance and thresholds \(\alpha,\beta\), and asks whether a base meets both ratios. Lemma 2(b) proves that some instances are no-instances whenever \(\alpha>0\) and \(\beta>1/2\); it is a Pareto obstruction, not a hardness result. For general threshold feasibility, I would tentatively expect hardness to transfer because the choice of an integral base still carries the combinatorics. The paper says the exact complexity of its uniform case is open, though, so that prediction is conjectural.
A second, broader mirror comes from Theorem 2 (proved here). It says that, among the bases maximizing \(w\), a base that maximizes \(g\) can be computed in polynomial time. Its continuous version is Lexicographic Mass Coverage: given the matroid, revenues, and an arbitrary rational distribution \(\mu\), find a base maximizing \((R(B),U_\mu(B))\) lexicographically—first maximize agency revenue, then maximize the served population mass among revenue-optimal plans. I expect this to be tractable, also Class A; Theorem 2 applies with \(g(\ell)=\mu_\ell\). This covers unequal cohort sizes, though it gives a revenue-first Pareto point rather than a balanced tradeoff.
The mirror covers the paper’s matroid-constrained choice of activity plans, with an additive institutional objective and a label-coverage population objective. It does not extend the claim to arbitrary social-choice problems or to all of the paper’s tradeoff questions. Further questions include how the Pareto frontier changes with unequal type masses, how much revenue loss buys a specified population coverage, and the exact complexity of threshold feasibility in the uniform case.
My weakest point is that \(g\) already assigns arbitrary real gains to labels. A skeptical reader can say that normalizing those gains gives a type distribution, so this mirror mostly gives a population interpretation to a model that already has the right weighted-coverage mathematics. That weakens any claim of novelty. The case for the mirror is that the scenario is credible—the paper itself uses tourists, activity labels, and a travel agency—and the distinction between one collective diversity utility and many cohorts whose satisfaction aggregates to that same function is intelligible. The formulation also makes the high-multiplicity regime explicit: many visitors, few types, and no individual-level targeting. The paper’s Section 7 NP-completeness claim for \(\Pi\) is unnumbered, so I have not used it as an anchor under the stated rule.
The visitors in the proposed scenario make a credible high-multiplicity population. The strongest case against the mirror is that its population model is already exactly the paper’s \(g\)-objective in different notation.
For any nonzero rational gains, let \(G=\sum_\ell g(\ell)\) and set \(\mu_\ell=g(\ell)/G\). Then every base \(B\) satisfies
\[
U_\mu(B)=\sum_{\ell\in L(B)}\mu_\ell=\frac{g(B)}{G}.
\]
So the feasible plans, objective comparisons, and approximation ratios are identical. In particular, Theorem 2 already computes the proposed lexicographic population-coverage solution: maximizing \((w(B),g(B))\) is the same as maximizing \((R(B),U_\mu(B))\). Theorem 1 also gives its stated tradeoff guarantees for arbitrary gains on labeled-simple matroids. This is a model identity, not merely an outside result that happens to answer a newly posed question.
Theorem 3 and Lemma 2(b) map just as directly. With \(p\) equally sized cohorts, \(U_\mu(B)=|L(B)|/p\), so the population approximation ratio is exactly the label-count ratio in Theorem 3. In the two-label obstruction of Lemma 2(b), each cohort has mass \(1/2\); serving more than half the maximum population requires both labels and forces zero revenue, exactly as in the paper’s original instance. Replicating either cohort changes none of these calculations.
A stronger mirror might use unequal cohort sizes, ask for a balanced tradeoff, or ask whether a plan meets specified revenue and coverage thresholds. Unequal rational masses are already arbitrary \(g\)-values after normalization. The paper’s general tradeoff results therefore apply directly; its threshold problem \(\Pi\) is the same feasibility question, and the uniform case’s open complexity question remains the same open question under the population interpretation. Adding richer type-specific preferences could create new questions, but it would replace the paper’s label-coverage objective and cease to be a mirror of these anchors.
So the negative case rests on collision, not on denying that a large visitor population is sensible. The population interpretation is coherent, but for these results the paper’s gain vector already encodes the entire distribution. A formal population reading could be useful as a dictionary or application; I don’t see a separate computational question here that merits a continuous mirror. The honest weakness is that a broader model of visitor preferences might yield one, though it would need to be argued as a new problem rather than as a stronger version of these mirrors.
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.