Answer: A PTAS exists: for every fixed \(\epsilon\in(0,1)\), a committee with \(D_\mu(W)\le(1+\epsilon)\mathrm{OPT}_\mu\) can be computed in time polynomial in \(m,\tau,L\), with \(k\) part of the input.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximate∀ϵ∈(0,1) we may compute a (1 + ϵ)-approximate solution to Mini- max Approval Voting in O Poly(n, m) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), a finite approval-type support \(\mathcal{A}\subseteq 2^C\) with positive binary-rational masses \(\mu_A\) summing to \(1\), and fixed \(\epsilon\in(0,1)\), compute a committee \(W\subseteq C\) with \(|W|=k\) such that \(D_\mu(W)\le(1+\epsilon)\min_{|U|=k}D_\mu(U)\), where \(D_\mu(W)=\max_{A\in\mathcal{A}}|W\triangle A|\).
Let \(C\) be a candidate set with \(m=|C|\), and let \(k\) be an integer with \(0\le k\le m\). Approval types may be arbitrary subsets of \(C\), including the empty set.
A society is given by its nonempty support: a list \(\mathcal A\subseteq 2^C\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_A\) satisfying \(\sum_{A\in\mathcal A}\mu_A=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
For a committee \(W\subseteq C\) with \(|W|=k\), define \(D_\mu(W)=\max_{A\in\mathcal A}|W\triangle A|\) and \(\mathrm{OPT}_\mu=\min_{U\subseteq C,\,|U|=k}D_\mu(U)\).
For every fixed \(\epsilon\in(0,1)\), can a committee \(W\) satisfying \(D_\mu(W)\le(1+\epsilon)\mathrm{OPT}_\mu\) be computed in time polynomial in \(m,\tau,L\), with dependence on \(k\) and \(\epsilon\) stated, or is achieving this guarantee NP-hard for some fixed \(\epsilon\)?
Known results: finite-voter Minimax Approval Voting admits a PTAS ([Byrka and Sornat](https://arxiv.org/abs/1407.7216)). The stated mass problem has exactly the same feasible committees and objective as the finite-voter instance containing one voter of each supported type; consequently, that PTAS already covers this formulation.
The problem admits a PTAS. For every fixed \(\epsilon\in(0,1)\), a committee satisfying the requested guarantee can be computed in time polynomial in \(m,\tau,L\), even when \(k\) is part of the input. The masses affect neither the optimization problem nor the approximation guarantee.
Enumerate the candidates as \(C=\{c_1,\ldots,c_m\}\). For each supported type \(A\in\mathcal A\), construct its incidence vector \(s_A\in\{0,1\}^m\), defined by \(s_A[j]=1\) exactly when \(c_j\in A\). Create a finite-voter instance with one voter for each of these \(\tau\) vectors and committee size \(k\).
A committee \(W\) corresponds bijectively to its incidence vector \(x_W\), with \(\sum_{j=1}^m x_W[j]=k\). Writing \(d_H\) for Hamming distance, each coordinate contributes to \(d_H(x_W,s_A)\) precisely when its candidate belongs to exactly one of \(W,A\). Consequently,
\(d_H(x_W,s_A)=|W\triangle A|\),
and hence
\(\max_{A\in\mathcal A}d_H(x_W,s_A)=D_\mu(W)\).
The feasible solutions and their objective values therefore coincide exactly. In particular, the finite-voter optimum equals \(\mathrm{OPT}_\mu\).
Constructing the incidence vectors takes \(O(m\tau+L)\) time. No replication proportional to a mass or its denominator is needed. The empty approval type is represented by the all-zero vector and satisfies the same identity.
Theorem 1 of Byrka and Sornat states that, for every fixed accuracy parameter \(\epsilon\in(0,1)\), Minimax Approval Voting on binary strings of length \(m\), with an exact cardinality constraint \(k\), admits a polynomial-time \((1+\epsilon)\)-approximation. Their rounding procedure can be derandomized. [Byrka–Sornat, Theorem 1 and Lemma 6](https://arxiv.org/pdf/1407.7216).
All hypotheses hold here: the constructed instance has finitely many binary votes, arbitrary approval sets are permitted, and \(0\le k\le m\). Apply that algorithm and return the committee corresponding to its output vector \(x\). The exact reduction gives
\(D_\mu(W)=\max_{A\in\mathcal A}d_H(x,s_A)\le(1+\epsilon)\mathrm{OPT}_\mu\).
This proves the requested guarantee.
In the cited algorithm, \(R=\lceil6/\epsilon\rceil\). It examines at most \(n^R\) voter subsets and \(k+1\) cardinality splits. Its auxiliary enumeration has at most
\((3n)^{108R\ln(2)/\epsilon^2}+m^{108R^2\ln(6)/\epsilon^2}\)
cases, with polynomial overhead. [Byrka–Sornat, Section 5](https://arxiv.org/pdf/1407.7216).
To accommodate its assumptions about the number of votes, we may pad our instance to \(n=\max\{\tau,k+1,R+1\}\) by duplicating any supported vote. Duplicating a vote preserves the maximum distance for every committee, so it preserves the optimum and every approximation guarantee.
Since \(k\le m\), we have \(n\le\tau+m+R+1\). Also, \(R=O(\epsilon^{-1})\), so the two displayed exponents are respectively \(O(\epsilon^{-3})\) and \(O(\epsilon^{-4})\). Thus a coarse running-time bound is
\(O(L)+f(\epsilon)(m+\tau+1)^{O(\epsilon^{-4})}\),
where \(f\) depends only on \(\epsilon\). In particular, \(k\) need not be fixed: its explicit enumeration contributes only \(k+1\) choices. This is a PTAS bound; it does not assert polynomial dependence on \(\epsilon^{-1}\).
If \(k=0\), return the unique feasible committee \(\varnothing\); if \(k=m\), return \(C\).
The multiplicative guarantee also handles a zero optimum. Indeed, \(\mathrm{OPT}_\mu=0\) holds exactly when every supported type equals one committee of size \(k\). Because supported types are distinct and the support is nonempty, this means \(\mathcal A=\{A\}\) with \(|A|=k\). Return \(A\) in that case. These checks take polynomial time and leave the PTAS applicable to all remaining instances.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned task correctly. The exact reduction preserves every feasible committee and its objective value. The cited PTAS applies, and the stated running time is polynomial for every fixed \(\epsilon\), with \(k\) allowed to vary with the input. No major or minor mathematical issues were found.
Enumerating \(C\) and representing each supported type by its incidence vector is valid for arbitrary subsets, including the empty set. The correspondence between committees and binary vectors is bijective, and the condition \(|W|=k\) corresponds exactly to \(\sum_{j=1}^{m}x_W[j]=k\).
No feasible solutions are lost or introduced.
The identity
\[
d_H(x_W,s_A)=|W\triangle A|
\]
is correct: both sides count precisely the candidates belonging to exactly one of \(W\) and \(A\). Taking the maximum over the same nonempty support therefore preserves the objective for every feasible committee, and consequently preserves the optimum.
The masses do not occur in this maximum. Ignoring their numerical values is justified by the stated definition of \(D_\mu\), regardless of their denominators.
Constructing \(\tau\) incidence vectors of length \(m\), while reading the input, fits the stated bound \(O(m\tau+L)\). The construction does not expand rational masses into repeated voters.
This addresses the relevant input-size distinction: the reduction depends on the support size, rather than the number of possible approval types or any denominator.
The paper defines MAV using binary votes, maximum Hamming distance, and exactly \(k\) selected candidates. Its Theorem 1 provides the claimed approximation for each fixed \(\epsilon\in(0,1)\). Lemma 6 explicitly states that its rounding can be derandomized. Thus the prover’s theorem statement and deterministic interpretation are supported. [Byrka–Sornat, definitions, Theorem 1, and Lemma 6](https://arxiv.org/pdf/1407.7216).
The constructed instance satisfies these hypotheses. The subsequent equality and approximation inequality correctly transfer the theorem’s guarantee to \(D_\mu\).
The paper assumes \(n>k\); its stable-subset argument also uses enough voters for an \(R\)-element subset and the accompanying sequence. Padding to \(n=\max\{\tau,k+1,R+1\}\) meets these requirements. Repeated votes are permitted: the paper itself uses duplication to ensure \(n>k\). [Byrka–Sornat, Sections 1.2 and 3](https://arxiv.org/pdf/1407.7216).
Duplicating a supported vote leaves every maximum distance unchanged. A vote to duplicate exists because the support is nonempty.
The cited enumeration bounds and \(R=\lceil6/\epsilon\rceil\) agree with Section 5. [Byrka–Sornat, Section 5](https://arxiv.org/pdf/1407.7216). Their orders are correctly calculated:
\[
\frac{108R\ln(2)}{\epsilon^2}=O(\epsilon^{-3}),
\qquad
\frac{108R^2\ln(6)}{\epsilon^2}=O(\epsilon^{-4}).
\]
The outer factor \(n^R\), the \(k+1\) splits, and polynomial overhead can be absorbed into the asserted coarse bound. Since \(k\le m\) and \(n\le\tau+m+R+1\), the resulting dependence
\[
O(L)+f(\epsilon)(m+\tau+1)^{O(\epsilon^{-4})}
\]
is consistent. The prover correctly distinguishes this from polynomial dependence on \(\epsilon^{-1}\).
For \(k=0\) and \(k=m\), the returned committee is the unique feasible solution and therefore optimal. This also covers \(m=0\).
The characterization of zero optimum is correct. A maximum of nonnegative Hamming distances is zero exactly when every supported type equals the selected committee. Distinctness and nonemptiness then force a singleton support whose type has size \(k\). Returning that type satisfies the multiplicative guarantee exactly.
None. No additional lemma, hypothesis, calculation, or clarification is needed to verify the claimed result.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.