| paper | d4-journals-jair-2017-0057 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: For every fixed \(p\ge2\), the problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(K\). No exact algorithm running in \(f(K)\operatorname{poly}(m,\tau,L)\) exists unless \(\mathrm{FPT}=\mathrm{W}[1]\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 3.1(1)
statement extracted from the paper’s text layer
Given \(m\) candidates, fixed \(p\), approval types \(A_1,\ldots,A_\tau\subseteq C\) with \(|A_i|\le p\), positive binary-rational masses \(\mu_i\) summing to \(1\), a committee limit \(K\), and a rational threshold \(\theta\), decide whether some \(W\subseteq C\), \(|W|\le K\), satisfies \(\sum_{i:A_i\cap W\ne\varnothing}\mu_i\ge\theta\). Classify this problem parameterized by \(K\), with input size measured in \(m,\tau\), and the mass bit length \(L\).
Each approval set \(A_i\) is a voter type with mass \(\mu_i\). Choose binary candidate variables \(x_c\), with \(\sum_{c\in C}x_c\le K\), to maximize \(\sum_{i=1}^{\tau}\mu_i\mathbf{1}[A_i\cap\{c:x_c=1\}\ne\varnothing]\); ask whether the maximum is at least \(\theta\).
The opponent’s unaddressed prior-art point is that rational-mass MaxCover is weighted MaxCover, and the cited Skowron work already gives a closely related bounded-frequency FPT approximation scheme; this limits novelty but does not invalidate the population mirror or its hardness anchor.
fatal: False
The mirror covers Theorem 3.1(1) and Theorem 4.1 in the upper-bounded approval setting. The cited weighted MaxCover literature already answers a closely related approximation question. The other results, including lower-bounded-frequency, MinNonCovered, and unrestricted MaxCover results, are not assessed by these anchors.
The strongest mirror is the approval version of Chamberlin–Courant winner determination in a large customer population. The paper itself motivates the rule with a company choosing a small number \(K\) of product models for a large customer base. In a plausible high-multiplicity regime, many customers share the same shortlist of models they would consider, and each shortlist contains at most \(p\) models. A type is such a shortlist \(A\subseteq C\); its mass \(\mu_A\) is the fraction of customers with that shortlist. The support has \(\tau\) distinct shortlists, potentially far fewer than the number of customers.
The company chooses a committee \(W\subseteq C\), \(|W|\le K\), to maximize the represented customer mass
\[
\mathrm{cov}_\mu(W)=\sum_{A:A\cap W\ne\varnothing}\mu_A.
\]
This is the paper’s MaxCover objective with the population made continuous. It is also an instance regime the authors should recognize: they explicitly describe product selection as an application of the approval-based rule. The model uses approval lists as the complete type description because the objective treats each represented customer equally.
My lead is Bounded-Approval Mass MaxCover. Its instance consists of candidates \(C\), a support of approval types \(A_1,\ldots,A_\tau\) with \(|A_i|\le p\), positive rational masses \(\mu_i\) summing to \(1\), a committee limit \(K\), and a rational threshold \(\theta\in[0,1]\). The question is whether there is a committee \(W\) of at most \(K\) candidates with \(\mathrm{cov}_\mu(W)\ge\theta\); a solution is such a committee.
The anchor is Theorem 3.1(1), whose hardness and membership apply for every fixed \(p\ge2\): MaxCover with element frequencies bounded above by \(p\) is W[1]-complete when parameterized by the number \(K\) of sets in the solution. The paper derives hardness from the cited W[1]-hardness of MaxVertexCover (Guo, Niedermeier, and Wernicke, 2007), and proves membership here. The continuous mirror should remain W[1]-complete for fixed \(p\) and parameter \(K\). For hardness, take a discrete instance with \(n_A\) voters of each approval type \(A\), set \(\mu_A=n_A/n\), and set \(\theta=q/n\) for its coverage threshold \(q\). This preserves yes and no answers and the frequency bound. For membership, a parameterized algorithm can guess the \(K\) candidates and compute the covered rational mass in polynomial time. The underlying combinatorics still concern choosing candidates, so I expect hardness to transfer.
A useful second anchor is Bounded-Approval Mass Approximate MaxCover, the optimization version asking for a committee \(W\) whose covered mass is at least \(\gamma\) times the optimum, for a fixed \(\gamma\in(0,1)\). A solution is the committee itself, with its achieved covered mass. Theorem 4.1, proved in this paper, says that for fixed \(p\), Algorithm 1 returns a \(\gamma\)-approximation for discrete MaxCover with frequencies at most \(p\), in time
\[
\operatorname{poly}(|I|)\binom{\left\lceil 2pK/(1-\gamma)+K\right\rceil}{K}.
\]
The continuous mirror question is whether this guarantee extends to rational type masses, with running time polynomial in \(m,\tau,L\) times the same parameter-dependent factor. I expect it to be tractable: the paper’s algorithm ranks candidate sets by cardinality, tries subsets among the largest, and its bounded-frequency argument appears to extend by replacing cardinalities with total mass. That weighted extension is a proposed mirror result, not a theorem stated in the paper.
The scope here is the paper’s bounded-frequency approval setting: exact winner determination and approximation for choosing a committee that represents as much population mass as possible. The paper’s result that upper-bounded-frequency MaxCover is W[1]-complete is the strongest anchor for the lead; the approximation theorem is complementary evidence that the continuous model has a natural algorithmic question as well.
The soft spot is that this mirror gives a clean high-multiplicity formulation without making the problem easier. The continuous input can represent the original discrete instances exactly, and the hardness is driven by candidate selection rather than by the number of individually listed voters. That is a credible Class B outcome for the programme, but it is not a case where continuization dissolves the paper’s hardness.
The strongest case against these anchors is that the proposed society is exactly a weighted MaxCover instance. For each approval type \(A_i\), make one universe element of weight \(\mu_i\), and for each candidate \(c\), let \(S_c=\{i:c\in A_i\}\). Then
\[
\mathrm{cov}_\mu(W)=\sum_{i\in\bigcup_{c\in W}S_c}\mu_i.
\]
Conversely, a weighted MaxCover instance gives approval types by recording which sets contain each element; elements with the same approval pattern can be merged. After normalizing the weights, this is precisely a rational distribution over types. So the customer scenario is plausible, and mass is meaningful, but it creates no new computational object.
That directly undercuts the approximation anchor. Skowron’s work on submodular maximization defines MaxWeightCover with weighted elements and proves an FPT approximation scheme for it when element frequencies are bounded, parameterized by \((K,p)\). It also gives a PTAS when each element is covered by at least a fixed fraction of the sets. Those are the weighted population versions of the paper’s upper- and lower-frequency questions. The paper’s specific bound in Theorem 4.1 can also be carried over by using total weight in place of cardinality. [Skowron, *FPT approximation schemes for maximizing submodular functions*](https://fpt.akt.tu-berlin.de/publications/skowron_fpt_approx_scheme.pdf).
The exact-complexity anchor adds little new structure either. The weighted mass decision problem is W[1]-hard because equal masses recover the paper’s unweighted instances; membership follows by guessing the \(K\) candidates and computing the covered rational mass. That gives the proposed W[1]-completeness classification directly. It is a valid statement about the weighted model, but its proof is a routine extension of the discrete result, not a new continuization insight.
The negative case is weak on the universal claim. This paper has a credible high-multiplicity setting, and the population interpretation is natural. If ChoCo values making an explicit dictionary from voting problems to weighted mass problems, this could still be a useful example. But neither named anchor appears to open a worthwhile *new* continuous computational question: the approximation landscape already includes weighted coverage, and the exact classification transfers immediately. I would reject this paper as a novel continuization project while acknowledging that the evidence does not prove no scenario could make it worthwhile.
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.