Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Accelerating data-driven algorithm selection for combinatorial partitioning problems
Authors: Vaggos Chatziafratis, Ishani Karmarkar, Yingxi Li, Ellen Vitercik
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We provide size generalization guarantees for three widely used clustering algorithms (single-linkage, k-means++, and Gonzalez’s k-centers heuristic) and two canonical max-cut algorithms (Goemans-Williamson and Greedy). We characterize the subsample size sufficient to ensure that performance on the subsample reflects performance on the full instance, and our experiments support these findings. Finally, in Section 4, we empirically validate our theoretical findings. |
| Researcher Affiliation | Academia | Vaggos Chatziafratis UC Santa Cruz EMAIL Ishani Karmarkar Stanford University EMAIL Yingxi Li Stanford University EMAIL Ellen Vitercik Stanford University EMAIL |
| Pseudocode | Yes | Algorithm 1: Apx Seeding(X, k, m, f) Algorithm 2: SL(X, k) Algorithm 3: Seeding(X, k, f) Algorithm 4: Rounding Procedure GWRound(X) Algorithm 5: Greedy(G) |
| Open Source Code | Yes | We release our code for the experiments at https://github.com/Yingxi-Li/Size-Generalization. |
| Open Datasets | Yes | Clustering. We present experiments on four datasets. (1) The MNIST generator [13]: handwritten digits with images labeled corresponding to them. (2) GM: points from a 2-dimensional isotropic Gaussian mixture model... (3) The Omniglot generator [13]: handwritten characters from various languages... (4) The noisy circles (NC) generator [69]: points on two concentric circles (with noise level 0.05, distance factor 0.2), labeled by the circle to which they belong. |
| Dataset Splits | No | All instances contain n points evenly divided into k = 2 clusters except the last panel of the bottom row, where k = 10. On the top row, for MNIST, GM, and NC, n = 500. For Omniglot, n = 40 (instances from this dataset are inherently smaller). On the bottom row, n = 2000 for all except the last panel, where we use n = 4000. |
| Hardware Specification | Yes | We include as part of our supplementary material the type of CPU we used to run our experiment. |
| Software Dependencies | No | Our work is mostly theoretical, and experiments done are proof-of-concept that use only open-sourced packages and data. |
| Experiment Setup | Yes | All instances contain n points evenly divided into k = 2 clusters except the last panel of the bottom row, where k = 10. On the top row, for MNIST, GM, and NC, n = 500. For Omniglot, n = 40 (instances from this dataset are inherently smaller). On the bottom row, n = 2000 for all except the last panel, where we use n = 4000. ... The noisy circles (NC) generator [69]: points on two concentric circles (with noise level 0.05, distance factor 0.2)... Max-cut. We test four random graph families with with n = 50 vertices: Erdös-Réyni (p = 0.7), Barbell with 5 random inter-clique edges, random geometric (radius 0.9), and Barabási-Albert (m = 5). |