Research map / Learning theory and algorithms / Clustering
Near-optimal Linear Predictive Clustering in Non-separable Spaces via MIP and QPBO Reductions
Jiazhou Liang, Hassan Khurram, Scott Sanner
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 |
|---|---|---|---|
| use LPC-NS-MIP instead of Greedy on real datasets | Greedy · UCI datasets (10) | SSE: e.g. 17.1278 -> 12.4745 (Stock Portfolio) | Improved |
| use LPC-NS-QPBO instead of Greedy on real datasets | Greedy · Heart Failure Prediction (519) | SSE: 25.0644 -> 4.733 x 10^-30 | Improved |
| use LPC-NS-MIP instead of Greedy on Solar Flare | Greedy · Solar Flare (89) | SSE: 8.3014 -> 11.0511 | Hurt |
| use LPC-NS-QPBO instead of LPC-NS-MIP on Servo | LPC-NS-MIP · Servo (87) | SSE: 2.5305 -> 12.4865 | Hurt |
| use LPC-NS-QPBO instead of LPC-NS-MIP on Parkinsons Telemonitoring | LPC-NS-MIP · Parkinsons Telemonitoring (189) | SSE: 146.9704 -> 135.3372 | Improved |
| use w* approximation on non-separable features | global MIP · Synthetic 2-cluster non-separable | objective deviation from optimum: 0.0208 | Improved |
| use K-Means+Ridge CLR on non-separable instead of separable features | CLR · Synthetic 2-cluster | objective deviation from optimum: 0.5996 -> 72.2481 | Hurt |
| use LPC-NS-QPBO instead of GlobalOpt for large samples | GlobalOpt · Synthetic K=2 | scalability (samples within 2 hours): 200 -> 2000 | Improved |
| use LPC-NS-QPBO with K=3 instead of K=2 | LPC-NS-QPBO · Synthetic | deviation from GlobalOpt | Hurt |
| use Gurobi MIP solver instead of SCIP PBO solver for QPBO (ablation) | LPC-NS-QPBO · Synthetic K=2, D=1 | runtime scalability | Improved |
| increase feature dimensionality | Greedy · Synthetic | objective deviation | Hurt |
Closest papers by meaning
- Scalable and Globally Optimal Generalized L₁ K-center Clustering via Constraint Generation in Mixed Integer Linear Programming (AAAI 2023 · similarity 0.86)
- A Three-Level Optimization Model for Nonlinearly Separable Clustering (AAAI 2020 · similarity 0.85)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.84)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.84)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.83)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.83)
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.
