Approximating NP-Hard Combinatorial Subset Selection

57 concepts46 papers1 proposal

Imagine you are handed a massive collection of items—they could be data points in a dataset, potential locations for sensors, logic rules, or candidates for a committee. Your goal is to select a small, fixed-size subset of these items that maximizes a global utility or minimizes a global error.

This problem, known as combinatorial subset selection, appears across almost every domain of computer science:

  • Active Learning: Selecting the most informative subset of unlabeled data points to send to human annotators (Chen et al.).
  • Social Choice & Recommendation: Choosing a committee or a small menu of items that maximizes the collective satisfaction of a diverse group of users (Skowron et al.; Lu et al.).
  • System Control & Infrastructure: Finding the minimum number of inputs to make a structural linear system controllable (Pequito et al.), or selecting data replicas to optimize cloud platform costs (Zhang et al.).

At first glance, these problems seem straightforward. Why not just evaluate every possible subset and pick the best one? The issue is a brutal combinatorial explosion: choosing a subset of size $k$ from a pool of $n$ items requires evaluating $\binom{n}{k}$ combinations. As $n$ grows, this quickly becomes computationally impossible.

The Landscape of Computational Hardness

Across different domains, researchers have repeatedly hit a mathematical wall when trying to solve subset selection exactly. The underlying optimization problems are almost universally intractable:

  • NP-Hardness and NP-Completeness: Finding the optimal subset to maximize case-base coverage (Remembering to Add: Competence-preserving (ijcai 1999)), designing treatment portfolios (Giaever et al.), minimizing welfare loss in voting (Caragiannis et al.), and finding $k$-regret minimizing sets in three or more dimensions (Agarwal et al.) are all proven to be NP-hard or NP-complete.
  • Beyond NP: In some scenarios, the complexity is even more severe. Popa et al. demonstrated that selecting the optimal subset of logic rules to minimize data errors is DP-complete (requiring both an NP search and a coNP proof that no better solution exists). For data cleaning in fact-checking, Sintos et al. showed that evaluating the utility of a subset can be #P-hard.

Because finding the absolute best subset is mathematically out of reach for large-scale systems, the research direction shifts from exact optimization to provably good approximations.

Why Greedy Strategies Work: Submodularity

The most common and intuitive weapon against NP-hard subset selection is the greedy algorithm. A greedy algorithm builds the subset step-by-step, at each iteration picking the single item that provides the highest immediate marginal benefit.

While greedy choices can sometimes lead to terrible global solutions in general optimization, they are remarkably effective for subset selection. As surveyed by Liu et al., this success is driven by a mathematical property called submodularity.

Submodularity formalizes the law of diminishing returns. A set function $f$ is submodular if adding an item $x$ to a small subset $S$ provides a greater or equal marginal gain than adding that same item $x$ to a larger superset $T$ (where $S \subseteq T$):

$$f(S \cup \{x\}) - f(S) \geq f(T \cup \{x\}) - f(T)$$

When an objective function is monotone and submodular, a foundational mathematical guarantee applies: the greedy algorithm is guaranteed to find a subset that achieves at least $(1 - 1/e) \approx 63\%$ of the optimal utility.

This explains why simple sequential heuristics perform so well in practice for multi-winner voting rules (Lackner et al.), group recommendation (Skowron 0001 et al.), and budgeted social choice (Lu et al.). The greedy approach turns an exponential search space into a linear one, while guaranteeing that the result is never too far from perfect.

Exploiting Geometric and Structural Properties

When an objective function lacks submodularity, or when a $(1 - 1/e)$ approximation is insufficient, researchers look for hidden structure within the data to make the problem tractable.

Coresets and Hitting Sets

In geometric and multi-attribute data selection, we can often find a tiny proxy dataset—a coreset—that approximates the geometric properties of the full dataset within a small error bound $\epsilon$. Agarwal et al. leveraged coresets and hitting sets to solve the $k$-regret minimization problem, providing scalable summaries of massive datasets in polynomial time.

Intrinsic Dimension

In metric spaces, the complexity of subset selection can be bounded by the space's doubling dimension (a measure of how many small balls are needed to cover a larger ball). Gottlieb et al. utilized this geometric constraint to create near-optimal sample compression algorithms for Nearest Neighbor classifiers, proving that we can drastically shrink a training set while preserving its decision boundaries. Even in non-metric spaces, greedy geometric covering approaches provide a pathway to near-optimal compression (Gottlieb et al.).

Graph Homophily

Kazemi et al. proved that in the absence of extra structure, selecting an optimal representative subset for model training is completely impossible to approximate well in polynomial time. However, they showed that if you map the dataset to a graph, you can leverage homophily (the tendency of similar points to connect). By using Graph Neural Networks (RS-GNN) to exploit this structural alignment, they bypassed the theoretical hardness barrier entirely.

Continuous Relaxations and Alternative Frameworks

When dealing with dynamic or uncertain environments, discrete greedy choices can become unstable. To solve this, researchers often temporarily abandon the discrete nature of the problem.

For instance, in Online Two-Stage Submodular Maximization, a system must pre-select a shortlist of items before a user's specific utility function is even revealed. To navigate this uncertainty, Nikolaou et al. utilized a continuous relaxation of the submodular function. By treating the selection as a continuous probability distribution, optimizing it, and then applying randomized rounding, they successfully mapped the continuous solution back to a high-quality discrete shortlist.

Other successful paradigms bypass traditional greedy selection by adapting alternative algorithmic frameworks:

  • Affinity Propagation: Giaever et al. adapted message-passing clusters to efficiently design biological treatment portfolios.
  • Lookahead Minimization: Marchesoni-Acland et al. framed human data annotation as an optimal encoding problem, using lookahead strategies to group samples and minimize user interactions.
  • Adaptive Discretization: In multi-armed bandit scenarios where options change dynamically, Nika et al. used adaptive zooming to focus computational resources only on the most promising subsets of the feature space.

Summary

Combinatorial subset selection is fundamentally hard because the number of possible combinations grows exponentially. However, it is practically solvable because real-world selection problems are rarely random. They possess mathematical structure—whether it is the diminishing returns of submodularity, the spatial constraints of geometry, or the connectivity of graphs. By identifying and exploiting these properties, approximation algorithms turn impossible combinatorial explosions into fast, reliable, and provably near-optimal solutions.

Key Foundational Work

Remembering to Add: Competence-preserving Case-Addition Policies for Case- Base Maintenance (1999) — contributed 1 concept elements to this direction.
Semantic Compression and Pattern Extraction with Fascicles (1999) — contributed 1 concept elements to this direction.
Robust Recovery of Eigenimages in the Presence of Outliers and Occlusions (1996) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_np_hard_subset_selection_75265b90,
  title = {NP-hard subset selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/np-hard-subset-selection/rdr_75265b90ca8a4c90b0c35d9faf072140},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_np_hard_subset_selection_75265b90_v1,
  title = {NP-hard subset selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/np-hard-subset-selection/rdr_75265b90ca8a4c90b0c35d9faf072140/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake