Research map / Learning theory and algorithms / Clustering
A Framework for Minimal Clustering Modification via Constraint Programming
Chia-Tung Kuo, S. Ravi, Thi-Bich-Hanh Dao, Christel Vrain, Ian Davidson
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| add minimal-modification objective to balanced-summary clustering (ablation) | CP model · Social network clustering | swaps/nodes moved: 1074 -> 69 | Improved |
| add minimal-modification objective (ablation) | CP model · Social network clustering | normalized cut cost: 3.04 -> 1.34 | Improved |
| modify clustering to satisfy balanced summary (versus initial) | CP model · Social network clustering | normalized cut cost: 0.97 -> 1.34 | Hurt |
| enforce x-diameter <= 15 for cluster 3 and y-diameter <= 30 for cluster 2 | CP model · fMRI spatial clustering | cluster 3 x-diameter: 48 -> 15 | Improved |
| enforce y-diameter <= 30 for cluster 2 | CP model · fMRI spatial clustering | cluster 2 y-diameter: 41 -> 26 | Improved |
| enforce diameter constraints on more dimensions (feature subset {1-4,6-7}) | CP model · Yeast | objective (points moved): 3 -> 16 | Hurt |
| enforce diameter constraints on {1-4,6-7} instead of {1} | CP model · Yeast | SWCD: 9328 -> 9473 | Hurt |
| enforce diameter constraints on {1-4} instead of {1-3} | CP model · Pima | objective (points moved): 3 -> 6 | Hurt |
| enforce diameter constraints on {1-5} | CP model · Pima | feasibility | Hurt |
| increase number of instances | CP model · Yeast/Pima | run time | No clear effect |
| shrink first diameter by 20% (modified clustering vs initial) | CP model · Yeast | SWCD: 9277 -> 9328 | No clear effect |
| shrink first diameter by 20% (modified clustering vs initial) | CP model · Pima | SWCD: 5829 -> 5849 | No clear effect |
Closest papers by meaning
- Hierarchical Clustering with Structural Constraints (ICML 2018 · similarity 0.87)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.87)
- Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach (AAAI 2026 · similarity 0.87)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.86)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.84)
- Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.84)
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.
