More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

Anannya Upasana; Pallavi Jain; Saket Saurabh; Souvik Saha; Sushmita Gupta

REVIEW 2 major objections 5 minor 27 references

More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For approval profiles with no d voters approving the same d candidates, this paper gives fixed-parameter approximation schemes, a lossy kernel, a one-extra-seat approximation, and an FPT algorithm for PAV parameterized by score threshold.

desk verdict Genuinely new results and a clean generalization to submodular Thiele rules, but a false K_{d,d}-free edge bound in Claim 5 and false harmonic-number inequalities in Section 6 put the main theorems at risk. read the letter →

arxiv 2505.12699 v2 pith:PUPHWIKM submitted 2025-05-19 cs.GT cs.DS

Sushmita Gupta , Pallavi Jain , Souvik Saha , Saket Saurabh , Anannya Upasana This is my paper · ORCID

classification cs.GTcs.DS MSC 68Q2768W2591B12

keywords approval-basedmultiwinnerelectionsThielerulessubmodularmaximizationfixed-parameterapproximationschemeslossykernelizationbiclique-freegraphsproportionalapprovalvotingparameterizedcomplexity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies approval-based multiwinner elections, where each voter approves a set of candidates and a committee of $k$ candidates is scored by summing a monotone submodular satisfaction function over voters. Its central claim is that when the approval profile is $K_{d,d}$-free (no $d$ voters approve the same $d$ candidates), committee selection becomes fixed-parameter approximable: an algorithm running in time $(dk/\varepsilon)^{O(d^2 k)} n^{O(1)}$ returns a committee whose score is at least $(1-\varepsilon)$ times the target. The paper further claims a lossy kernel that shrinks the election to $(dk/\varepsilon)^{O(d^2)}$ candidates and $(dk/\varepsilon)^{O(d^3)}$ voters, an algorithm that finds a $(k+1)$-member committee matching the optimal $k$-member score, and an FPT algorithm for the PAV (proportional approval voting) rule parameterized by the score threshold $t$, resolving an open question from earlier work. If these results hold, many practically used approval rules become tractable exactly on profiles where voting patterns are diverse rather than tightly clustered.

What carries the argument

The central object is the bipartite approval profile graph $G=(C,V,E)$, with an edge between candidate and voter when the voter approves the candidate; the structural assumption is that $G$ is $K_{d,d}$-free, and $d$ is the smallest integer such that no $d$ voters approve the same set of $d$ candidates. The scoring is carried by per-voter OWA vectors $\lambda^v_j = f(j)-f(j-1)$, which are non-increasing exactly when each voter's satisfaction function is monotone submodular. The algorithmic workhorses are a sunflower lemma for $K_{a,b}$-free bipartite graphs, which justifies deleting low-score candidates without losing the optimum, and a counting argument showing that the $r$ highest-singleton-score candidates contain a near-optimal committee; the threshold-FPT proof uses color-coding and perfect hash families to isolate an optimal committee and the voters it satisfies.

What would settle it

Construct a $K_{d,d}$-free instance with $r = 4dk/(\varepsilon\lambda_{\min})+k$ top-scoring candidates and voters each approving slightly more than $d$ of them, arranged so the induced approval-edge count exceeds $|C_r|d(d-1)$ by the amount standard biclique-free counting allows; then evaluate the inequality $(|C_r|-k)\alpha_i \le 2d\,\mathrm{sco}(O)/\lambda_{\min} + |C_r|d(d-1)$ from Claim 5 and check whether the summation bound still holds.

Watch

Extended reading notes

Core claim

The paper's main theorem says that SM-MWE (submodular multiwinner election), with voter-specific non-increasing OWA vectors $\lambda^v$ encoding monotone submodular satisfaction, admits a $(1-\varepsilon)$-approximation in time $(dk/\varepsilon)^{O(d^2 k)} n^{O(1)}$ whenever the profile graph is $K_{d,d}$-free. The proof splits at a threshold: when the target score $t$ is low, a sunflower-based reduction rule deletes low-score candidates until exhaustive search becomes feasible; when $t$ is high, the top $r = 4dk/(\varepsilon\lambda_{\min})+k$ candidates by singleton score are shown to contain a near-optimal committee. The same machinery yields a polynomial-time lossy kernel and, by running the approximation on a carefully chosen high-score set $H$, a $(k+1)$-member committee whose score is at least the optimal $k$-member score. Section 6 additionally claims that under the PAV rule (the OWA vector $\lambda_i = 1/i$), winner determination is FPT parameterized by the score threshold $t$, via color-coding over candidate and voter color classes derandomized with perfect hash families.

Load-bearing premise

The high-threshold proof assumes that the voters who approve more than $d$ of the top-scoring candidates contribute at most $|C_r|d(d-1)$ approval edges in total; this bound is asserted without proof and is not implied by the no-$K_{d,d}$ condition, so Theorem 1 (and the kernel and additive results that lean on it) would fall if the bound is false.

Editorial extensions

If this is right

Theorem 1 gives a $(1-\varepsilon)$-approximation for any monotone submodular Thiele rule in time $(dk/\varepsilon)^{O(d^2 k)} n^{O(1)}$ on $K_{d,d}$-free profiles, where $d$ can be much smaller than the maximum approval-set size.
Theorem 2 shrinks any such instance in polynomial time to $(dk/\varepsilon)^{O(d^2)}$ candidates and $(dk/\varepsilon)^{O(d^3)}$ voters, so exact search on the reduced instance is feasible when $k$ is small.
Theorem 3 says one additional committee seat suffices to recover the full optimal score of a size-$k$ committee, so approximation loss disappears when committee size is flexible.
If Section 6 is correct, PAV winner determination is FPT by the score threshold $t$, matching the Chamberlin-Courant rule's known status and closing the open question.
All these algorithms work with a different Thiele function per voter, so they cover a strictly wider model than the standard single-rule formulation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The high-threshold counting step invites a testable generalization: replace the asserted linear edge bound with the standard biclique-free counting bound; the approximation may survive with a worse dependence on $d$, or may force a larger choice of $r$.
The color-coding scheme in the threshold algorithm suggests a neighbouring problem: whether the same FPT result holds for other Thiele rules whose OWA weights decay, or only for rules with a harmonic structure such as PAV.
The lossy kernel implies a practical workflow: reduce a large election to a small residual instance in polynomial time, then search exactly; the usefulness in practice depends on $d$ being small in real approval data, which is an empirical question.
The one-extra-seat theorem gives a policy reading: allowing $k+1$ seats instead of $k$ can remove the approximation loss entirely, which may matter for committees with flexible size.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the paper does something genuinely new: it extends the FPT-AS and lossy kernel results for MAX COVERAGE on K_{d,d}-free graphs to all monotone submodular Thiele rules, and adds a one-additive FPT approximation. The sunflower-based low-threshold case (Case 1 of Theorem 1) looks sound, and the use of Manurangsi's sunflower lemma and Jain et al.'s high-degree set bound is legitimate black-box use, not circular. Second, the high-threshold case has a real hole that propagates. Claim 5 asserts that in the graph induced on Cr\Oℓ and N(O∪Oℓ), voters of degree > d contribute at most |Cr|d(d−1) edges, justified solely by K_{d,d}-freeness. That is not a consequence of K_{d,d}-freeness. Kővári–Sós–Turán-type counting only gives O(|Cr|^{1+1/d}) such voters, and their total incident edges can be far larger than linear in |Cr|. The bound is false as stated, and it is exactly what converts the per-step replacement loss α_i into the final ε guarantee. Claim 6, the lossy kernel of Theorem 2, and the additive approximation of Theorem 3 all inherit the gap.

Section 6 has independent trouble. To get PAV FPT parameterized by t, the paper infers k ≤ 2t from t ≥ H_k and δ < 2t from t > H_δ. Both are false; H_k ≈ ln k, so the first gives k ≤ exp(t) at best. The harmonic steps are the ones that remove k from the parameter; without them, the algorithm is FPT in t+k, which was already known. So the claimed resolution of the Yang–Wang open question is not established.

What is good: the OWA reformulation and Lemma 1 are clean, the reduction rules are carefully argued, and the paper is honest about what it builds on. The contributions are significant if the gaps can be closed. Researchers working on parameterized approximation for multiwinner voting will want to read this carefully; it is a good test case for where K_{d,d}-free counting arguments can go wrong.

The paper deserves a serious referee, but it is not ready for publication. I would send it to review with a clear request to fix Claim 5 and Section 6, and to re-check the derived kernel and additive results once the edge-count bound is repaired.

Referee Report

2 major / 5 minor

Summary. The paper studies the Submodular Multiwinner Election (SM-MWE) problem under Thiele rules, assuming the approval profile graph is K_{d,d}-free. It claims an FPT approximation scheme with running time (dk/ε)^{O(d^2 k)} n^{O(1)} (Theorem 1), a (1-ε)-approximate polynomial-time lossy kernel (Theorem 2), an additive one-member approximation (Theorem 3), and an FPT algorithm for the PAV rule parameterized by the score threshold t, which would resolve an open question of Yang and Wang. The framework also allows voter-specific Thiele functions. The proof of Theorem 1 splits into a low-threshold case handled by a sunflower-based reduction and a high-threshold case based on restricting to the top r candidates. The lossy kernel combines a candidate-reduction step and a voter-reduction step. The PAV FPT algorithm uses color coding with additional case distinctions to eliminate the committee size k from the parameter.

Significance. If correct, the results would generalize Skowron's FPT approximation scheme from bounded approval sets to K_{d,d}-free profiles, would provide the first lossy kernel for SM-MWE, and would settle an open question on PAV. The paper also introduces voter-specific OWA vectors, which is a useful modeling generalization. However, two central technical pillars are not sound as written: the edge-count bound in Claim 5 is false, and the harmonic-number inequalities in Section 6 are mathematically incorrect. These flaws invalidate the high-threshold case of Theorem 1 and the claimed FPT parameterization by t for PAV.

major comments (2)

[Section 3, Claim 5 (Theorem 1, Case 2)] The proof of Claim 5 asserts that in a K_{d,d}-free bipartite graph, the high-degree vertices contribute at most |C_r|d(d-1) edges to N(O∪Oℓ), and the surrounding text alternatively claims the bound \binom{|C_r|}{d}(d-1). The linear bound is false: for d=3, take C_r as the point set of an affine plane of order q and V as the set of all q^2+q lines. Each line has degree q, and any three lines have at most one common point, so the graph is K_{3,3}-free; yet the total number of edges is q^3+q^2, which exceeds 6q^2 = |C_r|·3·2 for q≥7. The binomial bound, while true, is not the bound used in the displayed inequality and is superlinear in |C_r|, so the subsequent derivation of Σ α_i ≤ ε·sco(O) in Claim 5 fails. Therefore the high-threshold case of Theorem 1, and with it Theorem 2 and Theorem 3, are not established as written.
[Section 6, Lemma 18 and PAV parameterization] The case analysis for the PAV rule relies on the inferences 'if t ≥ H_k then k ≤ 2t' and 'if t > H_δ then δ < 2t', where H_m is the m-th harmonic number. These inferences are false: H_m = ln m + γ + o(1), so H_m ≥ t only implies m ≥ e^{t-γ}, which is not bounded by 2t for large t. The same type of error appears when bounding |O| ≤ t·2t. Because these steps are what remove k from the parameter, Lemma 18 only yields an FPT algorithm for the combined parameter (t,k). The claimed resolution of the Yang-Wang open question is therefore not proved.

minor comments (5)

[Abstract and Introduction] There are several typographical artifacts, including 'Manurangasi 2025', 'Aziz et el. 2015', 'PA V', and 'FPT -AS', which should be corrected before any resubmission.
[Section 3, Claim 5] The text uses both \binom{|C_r|}{d}(d-1) and |C_r|d(d-1) for the same claimed edge bound; this inconsistency should be resolved, and the actual bound used in the inequality must be stated unambiguously.
[Section 6, derandomization paragraph] The definition of an (n,k)-perfect hash family as one that 'splits S evenly' is nonstandard; the authors should either use the standard injective perfect hash family and argue via permutations of the color names, or cite a construction that guarantees balanced splits.
[Section 4, Lemma 13] The symbol n is used inconsistently for both |C| and |V| in the counting argument; the bounds on the number of voters with degree at least d and with unique neighborhoods should be restated with explicit cardinalities such as |C| and |V|.
[Section 3, Algorithm 1 and Case 2 analysis] The algorithm defines r = 4dk/(ε λmin) + k and uses C_r as the ⌈r⌉ highest-score candidates, but the proof then writes |C_r| = r; the rounding should be handled consistently throughout the inequalities.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main weaknesses are unsupported graph-theoretic and harmonic-number inferences, not self-referential derivation.

full rationale

After walking the derivation chain, I find no step in which a claimed prediction or first-principles result is, by construction, equivalent to its inputs. The main theorems use external lemmas as black boxes: Manurangsi's sunflower lemma for K_{a,b}-free graphs (Proposition 3), Jain et al.'s β-high-degree set bound (Proposition 16), Nemhauser-Wolsey-Fisher's greedy approximation (Lemma 9), Lokshtanov et al.'s lossy-kernel definitions, and standard perfect-hash derandomization. The Jain et al. citation shares authors with this paper, but it is a published, parameter-free combinatorial bound whose assumptions do not include the target results, so under the review rules it is independent support rather than a load-bearing self-citation chain. No parameter is fitted to data and then renamed as a prediction: the r-threshold in Algorithm 1, the λ_min normalization, and the lossy-kernel scalings are all analytic quantities defined before the algorithms run. The OWA reformulation is a standard equivalence, not a renaming of the result. The serious weaknesses in the paper are correctness gaps, not circularity: Claim 5 asserts an edge-count bound that is not a consequence of K_{d,d}-freeness, and Section 6 uses the false implication t ≥ H_k ⇒ k ≤ 2t (and similarly for δ). Those are unsupported mathematical inferences; the conclusions neither reduce to the premises nor are they assumed in the premises. Accordingly, no circular step can be quoted, and the circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters are fitted to data. The central claims rest on the K_{d,d}-free domain assumption, monotone submodular scoring, and several external lemmas from the literature. One questionable ad hoc bound appears in the proof of Claim 5. No invented entities are introduced.

assumptions (7)

domain assumption The input profile graph is K_{d,d}-free (no d voters approve the same set of d candidates).
This is the central structural parameter d; all theorems assume it. It is stated in Section 1 and used throughout.
domain assumption Each voter's satisfaction function is monotone submodular, equivalently its OWA vector λ^v is non-increasing (Lemma 1).
Used to justify greedy approximation and the score-loss arguments; Section 2.
standard math Manurangsi's sunflower lemma for K_{a,b}-free bipartite graphs (Proposition 3).
External combinatorial result used in Reduction Rule 1 and Theorem 1 Case 1.
standard math Nemhauser-Wolsey-Fisher greedy (1-1/e)-approximation for monotone submodular maximization.
Used for the polynomial-time approximation in Lemma 9.
standard math Existence and construction of perfect hash families of size e^k k^{O(log k)} log n.
Used to derandomize the color-coding FPT algorithm in Section 6.
ad hoc to paper In the proof of Claim 5, high-degree voters contribute at most |C_r| d(d-1) edges to N(O∪O_l).
This bound is asserted without proof and is not derivable from standard K_{d,d}-free counting; it is load-bearing for Theorem 1's Case 2.
domain assumption λmin = min_v λ^v_1 > 0, and each positive voter contributes at least λmin.
Used for bounds like |N(O)| ≤ sco(O)/λmin; if λmin = 0, those divisions fail.

how reviews work

0 comments

Cite this review

Pith. "Pith review of More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules." pith.science (2026). https://pith.science/paper/PUPHWIKM

@misc{pith2026250512699,
  author       = {Pith},
  title        = {Pith review of: More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PUPHWIKM}},
  note         = {Machine review of arXiv:2505.12699}
}

abstract

Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. We contribute to this area by designing parameterized approximation algorithms and also resolving an open question by Yang and Wang [AAMAS'18]. More formally, given a set of candidates, \mathcal{C}, a set of voters,\mathcal{V}, approving a subset of candidates (called approval set of a voter), and an integer $k$, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-\frac{1}{e}-\epsilon)\footnote{Here, $e$ denotes the base of the natural logarithm.}-approximation algorithm in f(k)(|\mathcal{C}| + |\mathcal{V}|)^{o(k)} time for any fixed $\epsilon > 0$ and any computable function $f$, and no {\sf PTAS} even when the length of approval set is two. Skowron [WINE'16] designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set and $k$. In this paper, we consider a parameter $d+k$ (no $d$ voters approve the same set of $d$ candidates), where $d$ is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., $1$-additive approximation). Additionally, we resolve an open question by Yang and Wang~[AAMAS'18] regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 13 canonical work pages

[1]

https://ballotpedia.org/Multi-winner_system, 2024

Multi-winner system. https://ballotpedia.org/Multi-winner_system, 2024

work page 2024
[2]

Color-coding

Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM , 42 0 (4): 0 844--856, 1995. doi:10.1145/210332.210337. URL https://doi.org/10.1145/210332.210337

arXiv 1995
[3]

Computational aspects of multi-winner approval voting

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. In Gerhard Weiss, Pinar Yolum, Rafael H. Bordini, and Edith Elkind, editors, Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May...

work page 2015
[4]

On the computation of fully proportional representation

Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. J. Artif. Intell. Res., 47: 0 475--519, 2013. doi:10.1613/JAIR.3896. URL https://doi.org/10.1613/jair.3896

work page doi:10.1613/jair.3896 2013
[5]

Multiwinner elections with diversity constraints

Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, and Piotr Skowron. Multiwinner elections with diversity constraints. In Sheila A. McIlraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), an...

2018
[6]

Chamberlin and Paul N

John R. Chamberlin and Paul N. Courant. Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule . American Political Science Review, 77 0 (3): 0 718--733, September 1983. URL https://ideas.repec.org/a/cup/apsrev/v77y1983i03p718-733_24.html

work page 1983
[7]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. ISBN 978-3-319-21274-6. doi:10.1007/978-3-319-21275-3. URL https://doi.org/10.1007/978-3-319-21275-3

doi:10.1007/978-3-319-21275-3 2015
[8]

Online approval committee elections

Virginie Do, Matthieu Hervouin, J \' e r \^ o me Lang, and Piotr Skowron. Online approval committee elections. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 , pages 251--257. ijcai.org, 2022. doi:10.24963/IJCAI.2022/36. URL https://doi.org/10...

doi:10.24963/ijcai.2022/36 2022

Show all 27 references

[9]

Properties of multiwinner voting rules

Edith Elkind, Piotr Faliszewski, Piotr Skowron, and Arkadii Slinko. Properties of multiwinner voting rules. Soc. Choice Welf., 48 0 (3): 0 599--632, 2017. doi:10.1007/S00355-017-1026-Z. URL https://doi.org/10.1007/s00355-017-1026-z

2017 doi
[10]

Multiwinner voting: A new challenge for social choice theory, volume 74 of Trends in computational social choice, pages 27--47

Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory, volume 74 of Trends in computational social choice, pages 27--47. Lulu Publisher, 2017. ISBN 1326912097

2017
[11]

Satisfiability to coverage in presence of fairness, matroid, and global constraints

Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to coverage in presence of fairness, matroid, and global constraints. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st Internatio...

2024 doi
[12]

Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage

Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-...

2023 doi
[13]

Phragm \'e n’s and thiele’s election methods

Svante Janson. Phragm \'e n’s and thiele’s election methods. Technical report, Technical report, 2016

2016
[14]

Consistent approval-based multi-winner rules

Martin Lackner and Piotr Skowron. Consistent approval-based multi-winner rules. J. Econ. Theory, 192: 0 105173, 2021. doi:10.1016/J.JET.2020.105173. URL https://doi.org/10.1016/j.jet.2020.105173

2021
[15]

Multi-Winner Voting with Approval Preferences - Artificial Intelligence, Multiagent Systems, and Cognitive Robotics

Martin Lackner and Piotr Skowron. Multi-Winner Voting with Approval Preferences - Artificial Intelligence, Multiagent Systems, and Cognitive Robotics. Springer Briefs in Intelligent Systems. Springer, 2023. ISBN 978-3-031-09015-8. doi:10.1007/978-3-031-09016-5. URL https://doi...

2023 doi
[16]

Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017...

2017
[17]

Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem)

Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA...

2020 doi
[18]

Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back

Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back. CoRR, abs/2403.06335, 2024. doi:10.48550/ARXIV.2403.06335. URL https://doi.org/10.48550/arXiv.2403.06335

2024 doi arXiv
[19]

Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back

Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back. Theor. Comput. Sci., 1028: 0 115033, 2025

2025
[20]

Schulman, and Aravind Srinivasan

Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182--191. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.49...

1995
[21]

Nemhauser, Laurence A

George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I . Math. Program., 14 0 (1): 0 265--294, 1978. doi:10.1007/BF01588971. URL https://doi.org/10.1007/BF01588971

1978 doi
[22]

Approval-based elections and distortion of voting rules

Grzegorz Pierczynski and Piotr Skowron. Approval-based elections and distortion of voting rules. In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 , pages 543--549. i...

2019 doi
[23]

Procaccia, Jeffrey S

Ariel D. Procaccia, Jeffrey S. Rosenschein, and Aviv Zohar. Multi-winner elections: Complexity of manipulation, control and winner-determination. In Manuela M. Veloso, editor, IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hydera...

2007
[24]

FPT approximation schemes for maximizing submodular functions

Piotr Skowron. FPT approximation schemes for maximizing submodular functions. Inf. Comput., 257: 0 65--78, 2017. doi:10.1016/J.IC.2017.10.002. URL https://doi.org/10.1016/j.ic.2017.10.002

2017 doi
[25]

Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time

Piotr Skowron and Piotr Faliszewski. Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. J. Artif. Intell. Res., 60: 0 687--716, 2017. doi:10.1613/JAIR.5628. URL https://doi.org/10.1613/jair.5628

2017 doi
[26]

Fully proportional representation with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time

Piotr Krzysztof Skowron and Piotr Faliszewski. Fully proportional representation with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificia...

2015 doi
[27]

Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability

Yongjie Yang and Jian - xin Wang. Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability. Auton. Agents Multi Agent Syst., 37 0 (2): 0 28, 2023. doi:10.1007/S10458-023-09610-Z. URL https://doi.org/10.1007/s10458-023-09610-z

2023 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

https://ballotpedia.org/Multi-winner_system, 2024

Multi-winner system. https://ballotpedia.org/Multi-winner_system, 2024

work page 2024

[2] [2]

Color-coding

Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM , 42 0 (4): 0 844--856, 1995. doi:10.1145/210332.210337. URL https://doi.org/10.1145/210332.210337

arXiv 1995

[3] [3]

Computational aspects of multi-winner approval voting

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. In Gerhard Weiss, Pinar Yolum, Rafael H. Bordini, and Edith Elkind, editors, Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May...

work page 2015

[4] [4]

On the computation of fully proportional representation

Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. J. Artif. Intell. Res., 47: 0 475--519, 2013. doi:10.1613/JAIR.3896. URL https://doi.org/10.1613/jair.3896

work page doi:10.1613/jair.3896 2013

[5] [5]

Multiwinner elections with diversity constraints

Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, and Piotr Skowron. Multiwinner elections with diversity constraints. In Sheila A. McIlraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), an...

2018

[6] [6]

Chamberlin and Paul N

John R. Chamberlin and Paul N. Courant. Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule . American Political Science Review, 77 0 (3): 0 718--733, September 1983. URL https://ideas.repec.org/a/cup/apsrev/v77y1983i03p718-733_24.html

work page 1983

[7] [7]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. ISBN 978-3-319-21274-6. doi:10.1007/978-3-319-21275-3. URL https://doi.org/10.1007/978-3-319-21275-3

doi:10.1007/978-3-319-21275-3 2015

[8] [8]

Online approval committee elections

Virginie Do, Matthieu Hervouin, J \' e r \^ o me Lang, and Piotr Skowron. Online approval committee elections. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022 , pages 251--257. ijcai.org, 2022. doi:10.24963/IJCAI.2022/36. URL https://doi.org/10...

doi:10.24963/ijcai.2022/36 2022