Research map / Learning theory and algorithms / Combinatorial and search optimization
Measures of diversity and space-filling designs for categorical data
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.
Proposes exact integer-programming solvers and two greedy approximation algorithms (GIPPR, GAC) for selecting maximally diverse designs over categorical (boolean hypercube) spaces under packing radius, covering radius, and average covering criteria.
Problem
Selecting a small subset of categorical items that is maximally diverse (space-filling) when the space has no natural ordering, where continuous space-filling methods do not apply and exact combinatorial search is intractable.
Approach
Casts diverse categorical design as optimizing packing radius, covering radius, or average covering under Hamming distance; shows exact LP/IP formulations, proves GIPPR (greedy farthest-point via integer programming) gives 2-approximation guarantees for PR and CR, and GAC (greedy average covering, using supermodularity/submodularity) gives a (1-1/e-style) half-gap guarantee for AC.
Key results
- GIPPR and GAC consistently outperform Random, d-Halton and k-DPP on the packing and average covering measures across design sizes n up to 50 (d=7 and d=8).
- In data collection, GAC gives the lowest MSE on Ising (5.77) and MIS (47.2) and GIPPR gives the lowest LL on LAB (1.03) among methods, compared with Random at 6.33 and 63.4 MSE on Ising and MIS.
- Theoretical guarantees: GIPPR achieves CR*_n <= CR(D_n) <= 2 CR*_n and PR*_n/2 <= PR(D_n) <= PR*_n; GAC achieves half the optimal reduction in average covering.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GAC instead of d-Halton for categorical designs | GAC · Ising | MS: 6.14 -> 5.77 | Helped |
| Use GAC instead of d-Halton for categorical designs | GAC · Ising | LL: 3.53 -> 3.42 | Helped |
| Use GAC instead of Random for categorical designs | GAC · MIS | MS: 63.4 -> 47.2 | Helped |
| Use GAC instead of Random for categorical designs | GAC · MIS | LL: 295 -> 163 | Helped |
| Use GRIPPR instead of d-Halton for categorical designs | GRIPPR · LAB | MS: 3.58 -> 3.47 | Helped |
| Use GRIPPR instead of d-Halton for categorical designs | GRIPPR · LAB | LL: 1.09 -> 1.03 | Helped |
| Use GAC instead of k-DPP to select categorical hyperparameters | GAC · Cora | improvement over default configuration: 76.1 -> 78.2 | Helped |
| Use GAC instead of k-DPP to select categorical hyperparameters | GAC · Cite | improvement over default configuration: 83.0 -> 84.0 | Helped |
| Use GAC instead of d-Halton to select categorical hyperparameters | GAC · Item | improvement over default configuration: 37.4 -> 41.7 | Helped |
| Use GRIPPR instead of Random to select categorical hyperparameters | GRIPPR · Load | improvement over default configuration: 22.0 -> 25.0 | Helped |
| Use GRIPPR instead of k-DPP to select categorical hyperparameters | GRIPPR · Anon | improvement over default configuration: 47.7 -> 63.3 | Helped |
Surprising findings
- Discretizing a continuous design (d-Halton) can produce estimates with larger tails than random designs for categorical data.
Limitations
- Exact solvers are computationally expensive and only feasible for small designs (n < 6).
- Approximation guarantees are worse (ratio 1/2) than exact solutions.
- Current methods focus on binary variables with extension to non-binary via encoding; mixed continuous/discrete inputs not addressed.
Experimental setup
Datasets: Doerr et al. categorical benchmark (LAB, MIS, Ising Model) Cora CiteSeer SCIP linear solver tuning benchmark (NeurIPS 2011 competition)
Benchmarks: OneMax Harmonic LAB MIS Ising Model Cora CiteSeer SCIP Item/Load
Metrics: packing radius covering radius average covering approximation error of integration mean squared error log-likelihood average improvement over default configuration (%)
Baselines: Random d-Halton k-DPP
Builds on: Gonzalez farthest-point greedy k-center k-DPP Quasi-Monte Carlo / space-filling designs Nemhauser greedy submodular maximization coffee-house design
Closest papers by meaning
- Linear Relaxations for Finding Diverse Elements in Metric Spaces (NeurIPS 2016 · similarity 0.87)
- GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility (NeurIPS 2025 · similarity 0.83)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.82)
- Measuring Diversity: Axioms and Challenges (ICML 2025 · similarity 0.82)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.82)
- Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract) (AAAI 2025 · similarity 0.82)
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.