Research map / Learning theory and algorithms / Sample complexity
Proportional Representation under Single-Crossing Preferences Revisited
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the O(n^2mk) line algorithm with the auxiliary-variable dynamic program | CC-Winner-SC · Single-crossing preferences on a line | time complexity: O(n^2mk) -> O(nmk) | Helped |
| Reduce winner determination to k-link path with concave Monge weights | CC-Winner-SC when k=Ω(log n) · Single-crossing preferences on a line | time complexity: O(nmk) -> nm2^{O\left(\sqrt{\log k\log\log n}\right)} | Helped |
| Use Borda misrepresentation with the concave Monge reduction | CC-Winner-SC · Borda misrepresentation | time complexity: O(nm\log(nm)) | Helped |
| Replace the earlier tree algorithm that indexes arbitrary subtrees with the new tree dynamic program | CC-Winner-SCT · Single-crossing preferences on a tree | time complexity: exponential -> O(nmk) | Helped |
| Assume optimal grid tilings are laminar and apply the rectangular dynamic program | CC-Winner-SCG · Single-crossing preferences on a grid | time complexity: O(n_1^2n_2^2k(n_1k + n_2k + n_1n_2m)) | Helped |
| Allow k^2 representatives and refine an optimal k-tiling into a laminar tiling | CC-Winner-SCG · Single-crossing preferences on a grid | dissatisfaction relative to optimum k-assignment: at most their dissatisfaction under an optimal k-assignment | Helped |
| Use the direct tree dynamic program before the tighter analysis | CC-Winner-SCT · Single-crossing preferences on a tree | time complexity: O(nmk^2) -> O(n^2m) | Helped |
| Apply the strongly-polynomial concave Monge k-link path algorithm | CC-Winner-SC · Single-crossing preferences on a line, k=Ω(log n) | time complexity: O(nmk) -> nm2^{O\left(\sqrt{\log k\log\log n}\right)} | Helped |
Closest papers by meaning
- Algorithms for Structured Elections Under Thiele Voting Rules (AAAI 2026 · similarity 0.89)
- On Recognising Nearly Single-Crossing Preferences (AAAI 2018 · similarity 0.88)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.88)
- Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences (NeurIPS 2026 · similarity 0.87)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.87)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.