Research map / Learning theory and algorithms / Submodular and game algorithms
Improved Theoretically-Grounded Evolutionary Algorithms for Subset Selection with a Linear Cost Constraint
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.
Re-analyzes POMC to prove a 1/2 approximation for monotone submodular subset selection under a linear cost constraint, and proposes EPOL (residual-problem decomposition over POMC) with a 0.6174 guarantee that outperforms baselines on maximum coverage and influence maximization.
Problem
Subset selection with a monotone submodular objective under a linear cost (knapsack-like) budget constraint; existing evolutionary algorithms lag greedy methods in approximation guarantees, and POMC's bound of (1/2)(1-1/e) may not be tight.
Approach
A finer-grained lower-bound analysis shows POMC achieves a 1/2 approximation rather than (1/2)(1-1/e); EPOL decomposes the problem into residual subproblems (one per item v, with f(.|v) and budget B-c(v)), runs POMC on each, and returns the best combined solution, reaching 0.6174 approximation.
Key results
- POMC's approximation ratio is improved from (1/2)(1-1/e) to 1/2 (Theorem 3.1).
- EPOL achieves a 0.6174 approximation guarantee (Theorem 4.1), matching the best-known practical greedy ratio.
- On frb35-17-1 with q=5, EPOL attains the best objective at every budget (e.g., 445.7 vs. 441.5 for POMC and 440.0 for 1-guess-Greedy+ at B=500) and has the best average rank in all six maximum coverage and influence maximization settings shown in Table 3 except for IM2 and IM3 where POMC/EAMC are cl
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EPOL instead of POMC | POMC · Maximum coverage, frb35-17-1, q=5, B=300 | covered vertices: 314.6 ± 1.8 -> 319.1 ± 0.8 | Helped |
| Use EPOL instead of POMC | POMC · Maximum coverage, frb35-17-1, q=5, B=350 | covered vertices: 350.9 ± 2.4 -> 356.6 ± 0.9 | Helped |
| Use EPOL instead of POMC | POMC · Maximum coverage, frb35-17-1, q=5, B=400 | covered vertices: 383.7 ± 2.6 -> 389.8 ± 0.6 | Helped |
| Use EPOL instead of POMC | POMC · Maximum coverage, frb35-17-1, q=5, B=450 | covered vertices: 413.8 ± 2.6 -> 419.0 ± 0.6 | Helped |
| Use EPOL instead of POMC | POMC · Maximum coverage, frb35-17-1, q=5, B=500 | covered vertices: 441.5 ± 2.4 -> 445.7 ± 0.6 | Helped |
| Improve POMC's approximation analysis | POMC · Subset selection with a linear cost constraint | approximation ratio: (1/2)(1 − 1/e) -> 1/2 | Helped |
| Use EPOL instead of POMC | POMC · Subset selection with a linear cost constraint | approximation ratio: 1/2 -> 0.6174 | Helped |
| Run EPOL on all residual problems rather than only the top-KB residual problems | EPOL · Maximum coverage and influence maximization | objective value | Helped |
Surprising findings
- EPOL is outperformed by nothing on maximum coverage in the reported setting, but on influence maximization with edge probability 0.05 it is not uniformly best (average rank 1.6 on IM2 and 1.4 on IM3).
Limitations
- EPOL's runtime grows with the budget since the number of residual problems run is KB, which is non-decreasing in B.
- Approximation guarantee of EPOL (0.6174) is below the optimal 1-1/e; the 1/2 result for POMC is a theoretical improvement but still below the greedy-optimal ratio.
- Experiments are restricted to maximum coverage and influence maximization on small graphs.
Experimental setup
Datasets: frb30-15-1 frb35-17-1 congress graph100 graph200 insecta
Benchmarks: frb30-15-1 frb35-17-1 congress graph100 graph200 insecta
Metrics: objective value (covered vertices / expected influence) average rank Wilcoxon signed-rank test
Baselines: GGA Greedy+ 1-guess-Greedy+ POMC EAMC EVO-SMC FPOMC
Builds on: POMC 1-guess-Greedy+ GSEMO
Closest papers by meaning
- An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints (AAAI 2020 · similarity 0.93)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.85)
- Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination (ICML 2025 · similarity 0.85)
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization (ICML 2024 · similarity 0.84)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.84)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · 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.