Answer: Polynomial-time solvable in \(m,\tau,k,L\), with running time \((\tau k+L)^{O(1)}\) using axis compression.
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateα-PAV can be computed in polynomial time for single-peaked approval preferences.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates on a common axis, a committee size \(k\), and \(\tau\) interval-approval types with positive rational masses \(\mu_t\) summing to \(1\), find a size-\(k\) committee \(W\) maximizing \(\sum_{t=1}^{\tau}\mu_t H_{|W\cap I_t|}\), where \(I_t\) is type \(t\)'s approved interval and \(H_q=\sum_{\ell=1}^{q}1/\ell\).
Let \(C=\{c_1,\ldots,c_m\}\), with \(m\geq 1\), have the supplied axis \(c_1\triangleleft\cdots\triangleleft c_m\), and let \(1\leq k\leq m\) be an integer. Each approval type is an interval \(I_t\subseteq C\); empty and full intervals are allowed.
A society is given by its support: the list of the \(\tau\) distinct types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Intervals are encoded by endpoints, with a separate empty-set marker; \(L\) is the total input bit length.
Find a committee \(W\subseteq C\) with \(|W|=k\) maximizing \(\sum_{t=1}^{\tau}\mu_t H_{|W\cap I_t|}\), where \(H_0=0\) and \(H_q=\sum_{\ell=1}^{q}\frac{1}{\ell}\) for \(1\leq q\leq k\). Any maximizing committee is acceptable.
Is this optimization problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,k,L\).
For an explicitly listed finite electorate with interval approvals, optimal PAV committees are computable in polynomial time; this also holds for nonnegative, non-increasing scoring vectors ([Peters, 2018](https://www.dominik-peters.de/publications/tum.pdf)). No result explicitly addressing the binary-rational support representation above was located in the search.
The problem is polynomial-time solvable in \(m,\tau,k,L\). Binary-rational masses can be used directly as objective coefficients; expanding the society into individual voters is unnecessary.
The relevant mechanism is the total-unimodularity formulation in [Peters (2018), Section 3](https://www.dominik-peters.de/publications/tum.pdf). Below is a complete proof for the support representation, including bit complexity. Compressing interchangeable candidates gives the stronger running-time bound \((\tau k+L)^{O(1)}\), with explicit committee output.
For every nonempty interval, write \(I_t=\{c_{a_t},\ldots,c_{b_t}\}\). Sort the distinct cut positions
\(1,m+1\), together with all \(a_t\) and \(b_t+1\).
Consecutive cuts partition the axis into nonempty blocks \(B_1,\ldots,B_s\), where \(s\leq 2\tau+1\). Let \(d_j=|B_j|\). Every interval is a union of consecutive blocks. In particular, all candidates within one block belong to precisely the same approval types.
Define \(A_{tj}=1\) if \(B_j\subseteq I_t\), and \(A_{tj}=0\) otherwise. Empty intervals give zero rows; full intervals give all-one rows.
A committee is therefore described, for purposes of its score, by integers \(y_j=|W\cap B_j|\) satisfying
\(0\leq y_j\leq d_j\) and \(\sum_{j=1}^{s}y_j=k\).
Conversely, every such integer vector can be realized by choosing \(y_j\) candidates from each block.
Introduce variables \(x_{t,\ell}\) for each type \(t\) and each \(\ell\in\{1,\ldots,k\}\). Consider the LP
\[ \begin{aligned} \text{maximize}\quad& \sum_{t=1}^{\tau}\sum_{\ell=1}^{k} \frac{\mu_t}{\ell}x_{t,\ell}\\ \text{subject to}\quad& \sum_{j=1}^{s}y_j=k,\\ & \sum_{\ell=1}^{k}x_{t,\ell} \leq \sum_{j=1}^{s}A_{tj}y_j \quad(t=1,\ldots,\tau),\\ & 0\leq y_j\leq d_j \quad(j=1,\ldots,s),\\ & 0\leq x_{t,\ell}\leq1 \quad(t=1,\ldots,\tau,\ \ell=1,\ldots,k). \end{aligned} \]
For a fixed integral vector \(y\), put \(q_t=\sum_j A_{tj}y_j\). This is an integer between \(0\) and \(k\). The best choice for type \(t\) is
\(x_{t,\ell}=1\) for \(\ell\leq q_t\), and zero otherwise, giving value \(\mu_tH_{q_t}\).
This remains optimal even among fractional choices of \(x\). Indeed, write \(q=q_t\). If \(q=0\), feasibility forces all its \(x\)-variables to zero. If \(q=k\), their upper bounds give the result. For \(1\leq q<k\), monotonicity of \(1/\ell\) gives
\[ \begin{aligned} \sum_{\ell=1}^{k}\frac{x_{t,\ell}}{\ell}-H_q &= -\sum_{\ell=1}^{q}\frac{1-x_{t,\ell}}{\ell} +\sum_{\ell=q+1}^{k}\frac{x_{t,\ell}}{\ell}\\ &\leq -\frac1q\sum_{\ell=1}^{q}(1-x_{t,\ell}) +\frac1q\sum_{\ell=q+1}^{k}x_{t,\ell}\\ &=\frac1q\left(\sum_{\ell=1}^{k}x_{t,\ell}-q\right) \leq0. \end{aligned} \]
Thus, for integral \(y\), optimizing the auxiliary variables gives exactly the required committee score.
A matrix is *totally unimodular* if every square submatrix has determinant in \(\{-1,0,1\}\).
First, any zero-one matrix whose ones are consecutive in each row is totally unimodular. Here is a direct proof. Take any square submatrix \(Q\). Its rows retain consecutive ones. Hence the columns of \(Q^{\mathsf T}\) have consecutive ones.
Let \(D\) have diagonal entries \(1\), subdiagonal entries \(-1\), and all other entries zero. Then \(\det D=1\). Each column of \(DQ^{\mathsf T}\) has at most one \(1\) and at most one \(-1\). Every square matrix with this property has determinant in \(\{-1,0,1\}\):
Consequently, \(\det Q=\det(DQ^{\mathsf T})\in\{-1,0,1\}\), proving the claim.
Now consider the LP constraints before adding variable bounds. Orient each type constraint as
\(\sum_j A_{tj}y_j-\sum_\ell x_{t,\ell}\geq0\).
The columns for \(y\) form \(A\) with an additional all-one cardinality row. Every row has consecutive ones, so this matrix is totally unimodular.
Each auxiliary column has just one nonzero entry, namely \(-1\) in its type row. Appending such columns preserves total unimodularity, by determinant expansion. Appending signed unit rows for variable bounds preserves it for the same reason. Finally, expressing the cardinality equality as two opposite inequalities also preserves total unimodularity: a square submatrix containing both opposite rows is singular; otherwise its determinant differs only by a row sign from an existing determinant.
Therefore the complete inequality matrix is totally unimodular. Its right-hand sides are integers: they consist of \(k,d_j,0,1\) and their negatives.
Every vertex of the feasible polytope is integral. To verify this, select a nonsingular square system of active constraints determining a vertex. Its determinant is \(1\) or \(-1\), so its inverse is integral by the adjugate formula. An integral right-hand side therefore gives integral coordinates.
The polytope is nonempty because \(\sum_jd_j=m\geq k\), and it is bounded by the variable bounds. Hence its linear objective attains a maximum at an integral vertex. Section 2 shows that the resulting committee maximizes precisely the requested objective.
The masses affect only the objective, so their denominators do not affect integrality.
There are \(N=s+\tau k\) variables and \(2N+\tau+2\) inequalities. A dense binary encoding of the LP has length
\[ S=O\!\left( N^2+kL+\tau k\log(k+1)+s\log(m+1) \right). \]
Here \(kL\) accounts for repeating each mass in its \(k\) objective coefficients. Multiplication of a denominator by \(\ell\) adds only \(O(\log(k+1))\) bits.
Exact rational linear programming runs in time polynomial in its encoding length. One can also extract an integral committee without assuming that a solver returns a vertex:
Every resulting set is a nonempty face of the original integral polytope. Its vertices are therefore integral, so every coordinate minimum fixed in this procedure is an integer. After these \(s\) additional LPs, all block counts are integral. By Section 2, the committee realizing them has score \(F\).
These LPs retain polynomial encoding length. Explicitly, if \(\mu_t=p_t/b_t\), every integral committee score has denominator dividing
\(D=(\prod_t b_t)k!\), whose bit length is \(O(L+k\log(k+1))\).
Since \(0\leq F\leq H_k\leq k\), the exact value \(F\) also has polynomial bit length.
Let \(P\) be a polynomial bound for an exact rational LP algorithm. Including preprocessing and output, the running time is
\[ O\!\left(L+\tau\log(\tau+1)\log(m+1)\right) +(s+1)P(S) +O\!\left(k\log(m+1)\right). \]
Because \(s\leq2\tau+1\), this is \((\tau k+L)^{O(1)}\), and in particular \((m+\tau k+L)^{O(1)}\). With the supplied axis explicitly listed, it is polynomial in total input length as well. If candidates are instead represented succinctly by their indices, the stated bound remains polynomial in the requested parameters; explicitly listing a committee necessarily takes at least \(k\) output steps.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. It establishes an exact algorithm polynomial in \(m,\tau,k,L\), with the stronger bound \((\tau k+L)^{O(1)}\). I found no major or minor mathematical gaps requiring repair.
The binary-rational masses are handled directly, without expanding the support into individual voters.
The compression is valid.
The correspondence between committees and feasible integral block counts is exact for the objective. The bounds \(0\leq y_j\leq d_j\) ensure realizability, and \(\sum_j y_j=k\) ensures the required committee size.
No assumption about distinct candidates having different approval patterns is needed.
For integral feasible \(y\), the quantity
\(q_t=\sum_j A_{tj}y_j\) is an integer satisfying \(0\leq q_t\leq k\). The upper bound follows from \(A_{tj}\in\{0,1\}\), nonnegative \(y_j\), and \(\sum_j y_j=k\).
The proposed prefix assignment to the auxiliary variables is feasible and has value \(\mu_t H_{q_t}\).
The displayed calculation proving optimality against fractional assignments is correct:
The separate cases \(q=0\) and \(q=k\) are correctly handled. Since every \(\mu_t\) is positive, multiplication by \(\mu_t\) preserves these comparisons.
Thus the auxiliary optimization gives exactly the committee objective whenever \(y\) is integral. The absence of explicit monotonicity constraints on the \(x_{t,\ell}\) variables is harmless.
The direct proof of total unimodularity is sound.
Selecting columns in their inherited order preserves consecutive ones within each row of a square submatrix \(Q\). After transposition, the lower difference matrix \(D\) transforms each consecutive block of ones into at most one positive and one negative entry.
The determinant argument covers every case:
Since \(\det D=1\), the conclusion about \(\det Q\) follows.
All subsequent matrix operations are justified:
Converting the oriented constraints into a common inequality direction only changes row signs, which also preserves total unimodularity.
The cited mechanism agrees with the PAV formulation in [Peters (2018), Section 3](https://www.dominik-peters.de/publications/tum.pdf). The submitted proof supplies its own integrality argument, so it does not rely on extending the finite-electorate theorem without justification.
The right-hand sides are integral, including the potentially large block capacities \(d_j\).
At a vertex, a full-rank selection of active constraints gives a nonsingular square matrix. Total unimodularity makes its determinant \(1\) or \(-1\), and the adjugate argument therefore gives integral coordinates.
The feasible region is nonempty and bounded. The capacities sum to \(m\geq k\), allowing feasible block counts, and the auxiliary variables may all be zero. All variables have finite bounds.
Consequently, an optimum exists at an integral vertex. Combined with Section 2, this proves exact equivalence between LP optimization and the requested committee optimization.
The statement that mass denominators do not affect integrality is correct: the masses occur only in the objective.
The extraction procedure is valid even when the LP algorithm initially returns a nonvertex optimum.
The optimal set is a nonempty face of the original polytope. Each successive coordinate minimization produces another nonempty face. Its vertices remain vertices of the original polytope and are therefore integral.
Accordingly, each fixed coordinate minimum is an integer. After all block coordinates are fixed, the resulting counts realize a committee. Its score equals \(F\): Section 2 gives its best auxiliary objective, while membership in the original optimal face ensures that value is the global optimum.
The additional objective equality need not preserve total unimodularity. The proof correctly uses the face property instead.
The variable and inequality counts are correct:
\(N=s+\tau k\) and \(2N+\tau+2\).
The stated dense encoding bound is sufficient. Constraint coefficients have constant bit length; objective coefficients repeat each mass \(k\) times and add only \(O(\log(k+1))\) denominator bits per coefficient. The block capacities require \(O(s\log(m+1))\) bits.
The denominator bound also checks out. Each harmonic denominator divides \(k!\), so every integral committee score has denominator dividing
\(D=(\prod_t b_t)k!\).
Its bit length is \(O(L+k\log(k+1))\). Since the optimum is attained by an integral committee and \(0\leq F\leq k\), the exact optimum has polynomial bit length.
The fixed block counts likewise have polynomial bit length. Thus all successive LPs remain polynomially encoded, and the stated aggregate running-time bound follows.
For succinctly indexed candidates, the conclusion is polynomial in the requested parameters, including \(k\). The proof correctly distinguishes this from a claim of polynomial time solely in succinct input length: explicit committee output can itself require \(k\) entries.
The argument covers \(m=1\), \(k=1\), \(k=m\), empty and full approval intervals, and a support consisting solely of the empty interval. None invalidates compression, feasibility, integrality, or extraction.
Required clarification or repair: none.
⟨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.