Research map / Learning theory and algorithms / Clustering
Low-Distortion Clustering with Ordinal and Limited Cardinal Information
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends metric distortion to clustering with only ordinal rankings, showing resource augmentation (more centers) or a few cardinal queries yield constant/low distortion for k-center, k-median and (k,z)-clustering, with matching lower bounds.
Problem
Clustering agents in an unknown metric accessible only through n rankings (ordinal information); the goal is to minimize social cost objectives (k-center, k-median, (k,z)-clustering, facility location) with low metric distortion, using few distance queries or extra centers.
Approach
Derive deterministic k-center algorithms using farthest-first traversal adapted to ordinal rankings, with 2-distortion using k^2-k over 2 queries, 4-distortion with 2k queries, and 2^(k-1)-center bicriteria with zero queries; for (k,z)-clustering, sample centers via ordinal-approximated k-means++ style sampling with oversampling by log n.
Key results
- Deterministic 2-distortion k-center with (k^2-k)/2 queries, and 4-distortion k-center with 2k queries; the latter's query count is shown optimal up to constants.
- Zero-query bicriteria algorithm for k-center returns 2^(k-1) centers with 2-distortion, and any finite-distortion algorithm must use Omega(2^k) centers.
- O(1)-distortion for (k,z)-clustering with O(k^4 log^5 n) queries in expectation, and O(log n) centers for (2,z) clustering with constant probability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ordinal farthest-first traversal with (k^2 - k)/2 distance queries | k-center · k-center | distortion: 2 | Helped |
| Use a 1/2-approximate farthest-first traversal with 2k queries | k-center · k-center | distortion: 4 | Helped |
| Return 2^{k-1} centers using ordinal preferences only | k-center · k-center | distortion: 2 | Helped |
| Oversample points from ordinal rings without distance queries | Ordinal ring sampling · (2,z)-clustering | distortion: O(1) | Helped |
| Use ordinal ring sampling without distance queries | Ordinal ring sampling · (k,z)-clustering | distortion: O(1) | Helped |
| Estimate ring costs with distance queries and emulate (k,z)++ sampling | Cardinal-query emulation of (k,z)++ · (k,z)-clustering | expected distortion: O(1) | Helped |
| Use one distance query per point in a Meyerson adaptation | Facility location · facility location | distortion: constant | Helped |
| Allow exponentially many centers in the ordinal bicriteria setting | Ordinal k-center · k-center | number of centers for finite distortion: Ω(2^k) | Mixed |
| Use fewer than Ω(k) distance queries | Ordinal k-center · k-center | distortion: Ω(k) | Hurt |
| Use fewer than Ω(n/α) distance queries | Facility location · facility location | distortion: Ω(n/α) | Hurt |
Surprising findings
- Facility location requires Omega(n) queries for constant distortion, so the simple Meyerson adaptation with n queries is essentially optimal.
- Purely ordinal algorithms cannot achieve bounded distortion for k-median with k=2 without extra centers or queries.
Limitations
- Exponential number of centers (2^(k-1)) or polylog-many centers needed in zero-query regimes.
- Gap between 4-distortion with 2k queries and the subquadratic-query lower bound remains open.
- Ordered clustering and other objectives such as graph clustering not addressed.
Experimental setup
Metrics: metric distortion approximation ratio number of distance queries number of centers
Builds on: k-means++ farthest-first traversal (Gonzalez) metric distortion framework
Closest papers by meaning
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.87)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.87)
- Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (AAAI 2025 · similarity 0.87)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.86)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.86)
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.