Pith. sign in

REVIEW 2 major objections 4 minor 29 references

Constant-Factor Distortion Mechanisms for $k$-Committee Election

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read Top-l committee elections can achieve constant-factor distortion with very few value queries, despite ordinal-only mechanisms being unbounded for k≥2.

desk verdict Strong A=C results for constant-distortion Top-l committees; the A≠C mechanisms query alternatives as agents and don't work under the stated model. read the letter →

arxiv 2501.19148 v2 pith:FZNCGETG submitted 2025-01-31 cs.GT cs.DScs.MA

Haripriya Pulyassary , Chaitanya Swamy This is my paper · ORCID
classification cs.GTcs.DScs.MA MSC 68W2591B1291B14
keywords k-committeeelectiondistortionTop-ℓobjectiveℓ-centrumproblemvaluequeriesadaptivesamplingmetricpreferencesclustering
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 elections where voters rank candidates but the goal is metric: each voter has a true distance to each candidate, and a committee of $k$ candidates should minimize the sum of the $\ell$ largest distances from voters to their closest committee member. Because rankings alone cannot guarantee bounded performance for $k \ge 2$, the paper allows a small number of value queries, each revealing one voter's distance to one candidate, and measures the resulting worst-case distortion. The central claim is that randomized mechanisms can achieve $O(1)$ distortion for every $k \ge 2$ and every $\ell$ using $O(\log k \log n)$ value queries per voter, or $\tilde{O}(k \log(\min\{\ell, n/\ell\}))$ queries per voter, or $O(k^2 \log^2 n \log \ell)$ queries in total. If correct, this gives the first constant-factor distortion upper bounds for the general Top-$\ell$ committee problem and partially answers an open question about norm-based $k$-clustering.

What carries the argument

The load-bearing object is the separable proxy for the Top-$\ell$ cost: for any vector $v$ of agent costs and any threshold $\rho$, $\mathrm{Top}_\ell(v) \le \ell\rho + \sum_i (v_i-\rho)_+$, with equality up to a $(1+\varepsilon)$ factor when $\rho$ is close to the $\ell$-th largest entry of $v$ (Claim 2.4). This identity turns the non-separable Top-$\ell$ objective into a $k$-median-like sum of truncated distances, so adaptive sampling can be applied: at each step, sample a voter with probability proportional to $(d(i,S)-2t_\ell)_+$. The mechanisms combine this proxy with coarse cost estimates from a greedy minimum-cost $k$-forest and standard $k$-center/$k$-median approximation algorithms, and with a black-box reduction that replaces the true metric by a close metric learned through binary search over each voter's ranking.

What would settle it

Fix a small instance (say $n=4$, $k=2$, $\ell=2$) and a preference profile, enumerate all metric distances consistent with it, and check whether Mechanism SAMPLE-MECH always returns a committee whose Top-$\ell$ cost is within the claimed constant factor of OPT; a single consistent metric on which the mechanism exceeds that factor would falsify the paper's central claim. A more targeted check is to compute the grids $T_1$ and $T_2$ from the two estimates and verify that some $t_\ell$ in them satisfies $t^*_\ell \le t_\ell \le \max\{(1+\varepsilon)t^*_\ell, \varepsilon\,\mathrm{OPT}/\ell\}$; an instance where neither grid contains such a threshold would pinpoint the failure.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that the $\ell$-centrum $k$-committee problem—select $k$ points minimizing the sum of the $\ell$ largest assignment costs in a metric space—admits constant-factor distortion mechanisms despite ordinal-only impossibilities, provided the mechanism may issue value queries. It proves this by first computing a coarse estimate of the optimal cost, then converting the ordinal instance into a nearly equivalent cardinal instance. The main technical discovery is an adaptive-sampling procedure for the Top-$\ell$ objective: sampling the next center with probability proportional to $(d(i,S)-2t_\ell)_+$, for a suitably chosen threshold $t_\ell$, yields an $O(1)$-approximate bicriteria solution ($O(k)$ centers, constant cost), even though the same sampling rule fails badly for $k$-center. A ring-based version of the same procedure gives a total-query bound that is polylogarithmic in $n$. All mechanisms are randomized and succeed with constant probability, which can be boosted by repetition.

Load-bearing premise

The whole adaptive-sampling argument depends on finding a threshold $t_\ell$ in one of two geometric grids that is between the $\ell$-th largest cost in an optimal solution and $\max\{(1+\varepsilon)$ times that cost, $\varepsilon\, \mathrm{OPT}/\ell\}$; if the randomized $k$-median estimate used to build one grid fails its success probability, no valid threshold may be present and the guarantee collapses.

Editorial extensions

If this is right

  • For every $k\ge2$ and every $1\le\ell\le n$, Top-$\ell$ committee election now has a mechanism whose distortion is a universal constant rather than a function of $n$.
  • The per-agent bound $O(\log k\log n)$ means each voter answers only logarithmically many distance queries, so the mechanism is viable when respondent effort is the bottleneck.
  • The total-query bound $O(k^2\log^2 n \log \ell)$ means the average number of queries per voter goes to $0$ as $n$ grows, so large electorates do not require proportionally more cardinal information.
  • For $k$-median ($\ell=n$), the mechanism gives a true $k$-committee with $O(1)$ distortion using $O(k^2\log^3 n)$ total queries, improving on prior bicriteria results that output more than $k$ centers.
  • The adaptive-sampling algorithm itself provides a simple constant-factor bicriteria algorithm for the cardinal $\ell$-centrum clustering problem, independent of the election application.

Reading between the lines

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

  • Going beyond the paper, the proxy-plus-adaptive-sampling template should extend to any ordered-optimization objective that admits a separable $\rho$-proxy with the Claim 2.4 property, not just Top-$\ell$.
  • If the mechanisms are run on real preference data with a heuristic cost estimate, the observed distortion will likely be far below the worst-case constant; this is a testable empirical prediction the paper does not make.
  • The sparsification step suggests a practical recipe for large electorates: reduce voters to $O(k)$ weighted representatives with a cheap bicriteria solution, then run any cardinal committee algorithm on the reduced instance.
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.

Referee Report

2 major / 4 minor

Summary. The paper studies the k-committee election problem under the Top-ℓ (ℓ-centrum) cost objective when agents and alternatives lie in a metric space, and the mechanism has access only to ordinal preferences together with a limited number of value queries. The authors' main technical contributions are: (i) a black-box reduction (Mechanism BB-Topℓ, Section 4.1) that approximates the true metric by a consistent metric using O(log^2 n) value queries per agent; (ii) a sparsification step based on a Meyerson-style facility-location algorithm, yielding O(log k log n) per-agent queries (Mechanism MEYERSON-BB); (iii) adaptive-sampling mechanisms for the Top-ℓ objective (Mechanisms SAMPLE MECH and SAMPLE MECH-TOT) with per-agent and total query bounds; and (iv) estimates of the optimal value from a Borůvka-style minimum k-forest computation, k-center, and k-median. The paper claims O(1) distortion in all cases, and Section 5 extends the per-agent query bounds to the setting A≠C. The abstract also advertises O(k^2 log^2 n) total queries, while Table 1 and Theorem 4.19 state O(k^2 log^2 n log ℓ).

Significance. If the results in Section 4 are correct, they would be the first constant-factor distortion upper bounds for the general Top-ℓ k-committee objective with k>1, and the paper gives a clean black-box reduction that turns any cardinal ℓ-centrum approximation into a low-query ordinal mechanism. The use of the separable proxy function of Chakrabarty--Swamy and the adaptation of adaptive sampling to a non-separable objective are elegant and potentially reusable. The A=C results are detailed with proofs that are for the most part internally consistent, and the manuscript does not engage in circular parameter fitting: the estimates B1, Bn, and B′ are derived from standard approximation algorithms rather than from the distortion bound being proved. However, two load-bearing gaps affect substantial parts of the advertised results: the A≠C mechanisms in Section 5 are not implementable under the stated value-query model, and the success-probability analysis of SAMPLE MECH does not account for the 1/2 failure probability of the randomized k-median estimate used to build one of its threshold grids.

major comments (2)
  1. [§5.1–5.2, Definition 2.3] The A≠C mechanisms are not executable under the paper's own query model. Definition 2.3 defines a value query as d(i,j) for an agent i∈C and alternative j∈A, so only agents can be queried. In Mechanism BORUVKA-GEN (Section 5.1, Step 5), when a supernode S is a singleton {a} with a∈~A⊆A\C, the instruction 'For each v∈S, query the value of min_{e∈δ(v)∩δ(S)} d(e)' requires a value query originating at the alternative a, which the model does not allow. The same problem affects the modified k-center procedure in Section 5.1: the pseudocode of Mechanism k-CENTER queries d(i, bottom_{C_i}(i)) with i∈S_{t-1}, and once centers are opened at top(s_t)∈A, these queries originate at alternatives. More decisively, Mechanism MEYERSON-BB-GEN (Section 5.2, Step 14) passes the alternative set S as the first argument to BB-Topℓ; BB-Topℓ's binary search (Mechanism BB, Lines 2–4) requires the preference ordering of each weighted point over A, but an alternative a∈S has no ordering in the profile σ, and no number of agent-side value queries can supply d(a,·) when the metric is accessible only as d(i,·) for i∈C. Consequently the A≠C entries in Table 1 and the claims of Theorems 5.2 and 5.3 are unsupported as written. This is not a high-probability gap that repetition can fix; it is a mismatch between the stated query model and the objects the mechanisms manipulate. The A=C results in Section 4 are not affected by this issue.
  2. [§4.2, Claim 4.15, Theorem 4.16] The success probability of Mechanism SAMPLE MECH is not established as stated because the grid T2 is built from the randomized estimate Bn of Theorem 1.2(b), which satisfies OPT≤Bn≤8(ln k+2)(n/ℓ)OPT only with probability at least 1/2. In the proof of Claim 4.15, the existence of t'_ℓ∈T2 relies on exactly this upper and lower bound on Bn. If Bn is too small or too large—an event of probability up to 1/2—then T2 may contain no value tℓ with t*_ℓ ≤ tℓ ≤ max{(1+ε)t*_ℓ, εOPT/ℓ}, and the good-cluster analysis in Section 4.5 cannot be applied. Mechanism SAMPLE MECH chooses T = argmin{|T1|,|T2|}, so when |T2|<|T1| (which happens when ℓ is large relative to n), the entire guarantee depends on the single run of the k-median estimate. The proof of Theorem 4.16 does not condition on this event or boost the estimate, so the claimed 'probability at least 1−δ' is not proven; in the affected regime the failure probability is only bounded away from 1 by a constant. This is repairable: one can run Mechanism k-MEDIAN O(log(1/δ)) times and take the minimum cost, since the lower bound Bn≥OPT is deterministic and the upper bound then holds with probability 1−δ while adding only O(k log(1/δ)) queries per agent; alternatively one can always include the deterministic grid T1. As written, however, the theorem's stated query-versus-success-probability tradeoff is not supported.
minor comments (4)
  1. [Abstract and Table 1] The abstract states a total-query bound of O(k^2 log^2 n), while Table 1 and Theorem 4.19 state O(k^2 log^2 n log ℓ); the abstract should be corrected to match the theorem.
  2. [§2, metric definition] The 'triangle inequality' displayed for d:C×A→R≥0 is d(i,a)≤d(i,b)+d(j,b)+d(j,a), which does not define distances between two alternatives or between two agents; Section 5's graph on ~A∪C implicitly assumes symmetry and additional metric structure, and this assumption should be stated explicitly.
  3. [§3.2, Mechanism k-MEDIAN] Line 4 of Mechanism k-MEDIAN writes 'Sample s_t with probability proportional to d(s_i, S_{t-1})' but the subscript should be s_t; also Line 3's 'C\S_{t-1}' is only meaningful when A=C, so the mechanism as stated is for the A=C estimate only.
  4. [§4.2, proof of Theorem 4.16] The query-complexity calculation contains the typo 'O(log(min{ℓ, ln(k)n/ℓ})) = ~O(ln(min{ℓ,n/ℓ}))'; the first expression should be O(log(min{ℓ, (ln k)·n/ℓ})), and the equality should be stated with the usual hiding of O(log log k) factors.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the mechanisms' guarantees are proven in-paper from external approximation primitives, with non-load-bearing self-citations.

full rationale

Walking the derivation chain, the constant-factor distortion claims are not built by defining outputs in terms of the quantities being predicted. OPT estimates (Boruvka, k-center, k-median) are computed by standard external approximation algorithms and only used as scale parameters; the black-box reduction (Mechanism BB-Topℓ), the Meyerson-style sparsification (Algorithm MEYERSON-TOPℓ), and the adaptive-sampling analyses (Theorem 4.14/4.18) contain self-contained proofs that relate their outputs to OPT without importing the target claim. The proxy function of Claim 2.4 is cited to [13], but the inequality is elementary and independently checkable, so the citation is real evidence rather than an ansatz smuggled in by citation. Self-citations [28] and [29] are preliminary/related-work references and are not load-bearing: [28] is mentioned as a preliminary version, and [29] only contextualizes single-winner distortion. I found no fitted parameter renamed as a prediction, no author-imported uniqueness theorem, and no equation that reduces to its own input by construction. The Section 5 concern that BORUVKA-GEN and MEYERSON-BB-GEN query alternatives as though they were agents is an implementation/query-model correctness issue, not a circularity; it does not change the circularity assessment.

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

There are no instance-dependent fitted parameters: all numerical constants in the proofs are universal and chosen to satisfy inequalities, not fitted to data. The paper relies on the metric-setting domain assumption, the value-query model, and external approximation algorithms. No new physical or mathematical entities are introduced.

assumptions (5)
  • domain assumption Agents and candidates are embedded in a metric space satisfying the triangle inequality, and the preference profile is consistent with the metric.
    Stated in the introduction and used throughout; the distortion definition in Section 2 quantifies over all metrics consistent with a given preference profile.
  • domain assumption The mechanism may issue value queries, each asking an agent for its distance to a specific alternative.
    Definition 2.3 in Section 2; this is the information-elicitation model. The A!=C mechanisms in Section 5 appear to violate this by querying alternatives as if they were agents.
  • domain assumption The main mechanisms assume A=C, so every candidate is also a queryable agent.
    Section 1.1 states 'We focus on the setting A=C'; this is what lets Boruvka, sparsification, and the black-box reduction query centers directly.
  • standard math Standard approximation and sampling results from prior work hold: Gonzalez 2-approximation for k-center, Arthur-Vassilvitskii O(log k) for k-median, Chakrabarty-Swamy (5+epsilon)-approximation for l-centrum, Meyerson facility location, Aggarwal et al. adaptive sampling, and Liberty et al. lemma.
    Invoked in Sections 3, 4, and the appendix with citations [20], [9], [13], [24], [2], [22]; the paper does not reprove these.
  • standard math The proxy function from Chakrabarty-Swamy correctly relates Top-l cost to a separable k-median-like objective.
    Claim 2.4 is used to translate the non-separable Top-l objective into sums of truncated distances, and its two inequalities are central to the adaptive-sampling analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Constant-Factor Distortion Mechanisms for $k$-Committee Election." pith.science (2026). https://pith.science/paper/FZNCGETG

@misc{pith2026250119148,
  author       = {Pith},
  title        = {Pith review of: Constant-Factor Distortion Mechanisms for $k$-Committee Election},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FZNCGETG}},
  note         = {Machine review of arXiv:2501.19148}
}
abstract

In the $k$-committee election problem, we wish to aggregate the preferences of $n$ agents over a set of alternatives and select a committee of $k$ alternatives that minimizes the cost incurred by the agents. While we typically assume that agent preferences are captured by a cardinal utility function, in many contexts we only have access to ordinal information, namely the agents' rankings over the outcomes. As preference rankings are not as expressive as cardinal utilities, a loss of efficiency is inevitable, and is quantified by the notion of \emph{distortion}. We study the problem of electing a $k$-committee that minimizes the sum of the $\ell$-largest costs incurred by the agents, when agents and candidates are embedded in a metric space. This problem is called the $\ell$-centrum problem and captures both the utilitarian and egalitarian objectives. When $k \geq 2$, it is not possible to compute a bounded-distortion committee using purely ordinal information. We develop the first algorithms (that we call mechanisms) for the $\ell$-centrum problem (when $k \geq 2$), which achieve $O(1)$-distortion while eliciting only a very limited amount of cardinal information via value queries. We obtain two types of query-complexity guarantees: $O(\log k \log n)$ queries \emph{per agent}, and $O(k^2 \log^2 n)$ queries \emph{in total} (while achieving $O(1)$-distortion in both cases). En route, we give a simple adaptive-sampling algorithm for the $\ell$-centrum $k$-clustering problem.

Figures

Figures reproduced from arXiv: 2501.19148 by the authors.

Figure 1
Figure 1. A k-winner selection instance with unbounded distortion 6 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Abramowitz, E

    B. Abramowitz, E. Anshelevich, and W. Zhu. Awareness of Voter Passion Greatly Improves the Distor- tion of Metric Social Choice. In Web and Internet Economics - 15th International Conference , WINE 2019, pages 3–16, 2019. 5

    work page 2019

  2. [2]

    Aggarwal, A

    A. Aggarwal, A. Deshpande, and R. Kannan. Adaptive Sampl ing for k-Means Clustering. In Approx- imation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 5687, pages 15–28. 2009. 4, 9, 16, 25

    work page 2009

  3. [3]

    Amanatidis, G

    G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. V ou douris. Don’t roll the dice, ask twice: the two-query distortion of matching problems and beyond. Advances in Neural Information Processing Systems, 35:30665–30677, 2022. 5

    work page 2022

  4. [4]

    Amanatidis, G

    G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. A. V oudouris. Peeking behind the ordinal cur- tain: Improving distortion via cardinal queries. In Proceedings of the Thirty-F ourth AAAI Conference on Artificial Intelligence, AAAI 2020 , pages 1782–1789, 2020. 5, 7, 33

    work page 2020

  5. [5]

    Anari, M

    N. Anari, M. Charikar, and P . Ramakrishnan. Distortion i n metric matching with ordinal preferences. In Proceedings of the 24th ACM Conference on Economics and Comp utation, pages 90–110, 2023. 5

    work page 2023

  6. [6]

    Anshelevich, O

    E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P . S kowron. Approximating optimal social choice under metric preferences. Artificial Intelligence , 264:27–51, Nov. 2018. 5

    work page 2018

  7. [7]

    Anshelevich and J

    E. Anshelevich and J. Postl. Randomized Social Choice Fu nctions Under Metric Preferences. In J. Artif. Intell. Res., volume 58, pages 797–827, 2017. 5 33

    work page 2017

  8. [8]

    Anshelevich and W

    E. Anshelevich and W. Zhu. Ordinal Approximation for Soc ial Choice, Matching, and Facility Lo- cation Problems Given Candidate Positions. In Web and Internet Economics - 14th International Conference, WINE 2018, pages 3–20, 2018. 2, 6

    work page 2018

Show all 29 references
  1. [9]

    Arthur and S

    D. Arthur and S. V assilvitskii. K-means++: The advantag es of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorith ms, SODA, pages 1027–1035. SIAM,

  2. [10]

    Borodin, D

    A. Borodin, D. Halpern, M. Latifian, and N. Shah. Distort ion in voting with top-t preferences. In IJCAI, pages 116–122, 2022. 5

    2022

  3. [11]

    Burkhardt, I

    J. Burkhardt, I. Caragiannis, K. Fehrs, M. Russo, C. Sch wiegelshohn, and S. Shyam. Low-distortion clustering with ordinal and limited cardinal information. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 9555–9563, 2024. 2, 3, 5, 7, 10

    2024

  4. [12]

    Caragiannis, N

    I. Caragiannis, N. Shah, and A. A. V oudouris. The metric distortion of multiwinner voting. Artificial Intelligence, 313:103802, 2022. 5, 6

    2022

  5. [13]

    Chakrabarty and C

    D. Chakrabarty and C. Swamy. Approximation algorithms for minimum norm and ordered optimiza- tion problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theor y of Computing, STOC 2019, pages 126–137, June 2019. 4, 7, 15, 17, 19, 31

    2019

  6. [14]

    Charikar and P

    M. Charikar and P . Ramakrishnan. Metric distortion bou nds for randomized social choice. In Proceed- ings of the 2022 Annual ACM-SIAM Symposium on Discrete Algor ithms (SODA), pages 2986–3004. SIAM, 2022. 5

    2022

  7. [15]

    Charikar, P

    M. Charikar, P . Ramakrishnan, K. Wang, and H. Wu. Breaki ng the metric voting distortion barrier. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA) , pages 1621–1640. SIAM, 2024. 5

    2024

  8. [16]

    X. Chen, M. Li, and C. Wang. Favorite-candidate voting f or eliminating the least popular candidate in a metric space. In Proceedings of the AAAI Conference on Artificial Intelligen ce, volume 34, pages 1894–1901, 2020. 5

    1901

  9. [17]

    Faliszewski, P

    P . Faliszewski, P . Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74(2017):27–47, 2017. 5

    2017

  10. [18]

    Gkatzelis, D

    V . Gkatzelis, D. Halpern, and N. Shah. Resolving the Opt imal Metric Distortion Conjecture. In 61st IEEE Annual Symposium on F oundations of Computer Science, F OCS 2020, pages 1427–1438, 2020. 5

    2020

  11. [19]

    A. Goel, R. Hulett, and A. K. Krishnaswamy. Relating met ric distortion and fairness of social choice rules. In Proceedings of the 13th Workshop on Economics of Networks, S ystems and Computation , pages 1–1, 2018. 5

    2018

  12. [20]

    T. F. Gonzalez. Clustering to minimize the maximum inte rcluster distance. Theoretical computer science, 38:293–306, 1985. 3, 9

    1985

  13. [21]

    D. Kempe. Communication, distortion, and randomness i n metric voting. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 34, pages 2087–2094, 2020. 5

    2020

  14. [22]

    Liberty, R

    E. Liberty, R. Sriharsha, and M. Sviridenko. An Algorit hm for Online K-Means Clustering. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 81–89. Society for Industrial and Applied Mathematics, Jan . 2016. 21 34

    2016

  15. [23]

    T. Ma, V . Menon, and K. Larson. Improving Welfare in One- Sided Matchings using Simple Threshold Queries. In Proceedings of the Thirtieth International Joint Conferen ce on Artificial Intelligence, IJCAI 2021, pages 321–327, 2021. 7, 33

    2021

  16. [24]

    Meyerson

    A. Meyerson. Online facility location. In Proc. FOCS’01, pages 426–431, Nov. 2001. 4, 13, 20

    2001

  17. [25]

    Munagala and K

    K. Munagala and K. Wang. Improved Metric Distortion for Deterministic Social Choice Rules. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 245–262, June 2019. 5

    2019

  18. [26]

    Ostrovsky, Y

    R. Ostrovsky, Y . Rabani, L. Schulman, and C. Swamy. The e ffectiveness of Lloyd-type methods for the k-means problem. Journal o the ACM , 59(6):28, 2012. 4

    2012

  19. [27]

    A. D. Procaccia and J. S. Rosenschein. The distortion of cardinal preferences in voting. In International Workshop on Cooperative Information Agents, pages 317–331. Springer, 2006. 1, 2, 5

    2006

  20. [28]

    Pulyassary

    H. Pulyassary. Algorithm design for ordinal settings. Master’s thesis, University of Waterloo, 2022. 3, 4, 5

    2022

  21. [29]

    Pulyassary and C

    H. Pulyassary and C. Swamy. On the Randomized Metric Dis tortion Conjecture. arXiv:2111.08698 [cs], Nov. 2021. 5 A Proof of Theorem 4.18 The proof closely mirrors that of Theorem 4.14. We first obser ve that the ring-based implementation is akin to using the earlier adaptive-sa...

    2021 arXiv

Pith tools

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