Output-Polynomial Knapsack Pareto | Interactive Research Explorer

Open Problem

Determine whether there exists an output-polynomial time algorithm for computing the full Pareto set of the bi-objective 0-1 knapsack problem, where solutions are evaluated by simultaneously minimizing total weight and maximizing total profit, and the running time must be polynomial in the input size n and in the size of the Pareto set |P|.

4

Instance Classes

7

Experiments

225+

Data Points

Open

Problem Status

Problem Background

Given n items with weights and profits, the bi-objective 0-1 knapsack problem seeks all Pareto-optimal subsets -- subsets not dominated by any other feasible subset in both weight (minimize) and profit (maximize). The Pareto set can be exponentially large.

Output-polynomial: time = poly(n, |P|) where |P| = number of Pareto-optimal solutions

The classical Nemhauser-Ullmann (NU) algorithm processes items via dynamic programming but can have intermediate sets much larger than the final output. Nikoleit et al. (2026) showed NU is not output-polynomial, leaving the general question open.

Key Findings

Finding 1: Pareto set growth is strongly instance-dependent, ranging from O(n) to O(n^2) for stochastic instances.

Finding 2: Weight-profit correlation is the dominant structural predictor of Pareto set size.

Finding 3: Reverse-search trees have bounded average branching factor (<1) on random instances with 100% reachability.

Finding 4: NU runtime is well-predicted by the final Pareto set size on all tested instance classes.

Instance Types Studied

Type	Description
Random	Independent uniform weights and profits
Correlated	Profit approximately equals weight
Anti-correlated	Profit approximately equals 110 minus weight
Adversarial	Deterministic constructions for NU

Pareto Set Size Scaling

How does the number of Pareto-optimal solutions grow with the number of items?

Detailed Results

Type	n=6	n=8	n=10	n=12	n=14	n=16	n=18
Random	8.7	14.6	18.6	26.0	34.6	49.8	59.9
Correlated	18.6	36.6	58.8	88.8	109.8	146.0	175.2
Anti-correlated	5.1	7.8	10.9	12.3	18.8	20.5	26.8
Adversarial	7	9	11	13	15	17	19

Stochastic results averaged over 10 trials. Adversarial instances are deterministic and produce exactly n+1 Pareto points.

Nemhauser-Ullmann Algorithm: Intermediate Set Profiles

The NU algorithm processes items one by one. At each step k, we track the size of the intermediate Pareto front.

Instance type:

Runtime Scaling

NU runtime as a function of n for different instance types.

NU Algorithm Visualization

Intermediate Pareto front sizes at each DP step for a random instance (n=18, final=71):

Each bar represents the intermediate Pareto set size at DP step k. The front grows monotonically as more items are processed.

Reverse-Search Tree Analysis

We implement a reverse-search enumerator following the Avis-Fukuda framework. The parent function removes the highest-indexed item yielding another Pareto-optimal solution.

Tree Statistics

n	Avg \|P\|	Avg Depth	Avg Branch	Max Branch	Reached
6	9.2	3.2	0.88	3	100%
8	15.4	4.6	0.93	4	100%
10	19.6	6.2	0.94	4	100%
12	27.8	7.0	0.96	5	100%

Key insight: Average branching factor stays below 1.0, meaning most nodes are leaves. The tree is path-like, traversing the Pareto set roughly in order. 100% reachability confirms the parent function defines a valid spanning tree.

Structural Predictors

How do instance properties predict Pareto set size? We analyze 225 instances across 3 types.

Interpretation

Positive correlation (p approximately w): Items have similar profit/weight ratios, making them nearly interchangeable. Many subsets with different cardinalities achieve non-dominated points, producing large Pareto sets.

Anti-correlation (p approximately 110-w): Ratios vary widely. High-profit items are light, creating clear dominance relationships that prune the Pareto set aggressively.

Random (independent p, w): Moderate correlation near 0 produces intermediate-sized Pareto sets.

Pareto Front Geometry (n=14)

Visualizing the shape of Pareto fronts for different instance types.