Introduction

In multi-objective optimization, a point is non-dominated if no other point is at least as good in every objective and strictly better in at least one. For a fixed input set, the "maximum non-dominated set" is usually just the set of all maximal points under that dominance relation, often called the Pareto frontier.

Clarify the Problem First

For a standard dominance relation on a finite set of candidate points, there is not a separate combinatorial search for the "largest good subset." The answer is determined directly:

• include every point not dominated by another input point
• exclude every dominated point

That resulting set is the maximal non-dominated set for the given input.

So the practical algorithmic problem is:

"How do I identify all non-dominated points efficiently?"

A Simple O(n^2) Algorithm

The direct method compares each point with every other point.

1def dominates(a, b):
2    return all(x <= y for x, y in zip(a, b)) and any(x < y for x, y in zip(a, b))
3
4
5def non_dominated_set(points):
6    result = []
7    for i, point in enumerate(points):
8        dominated = False
9        for j, other in enumerate(points):
10            if i != j and dominates(other, point):
11                dominated = True
12                break
13        if not dominated:
14            result.append(point)
15    return result
16
17
18points = [(1, 5), (2, 4), (3, 3), (4, 6), (5, 2)]
19print(non_dominated_set(points))

This is easy to understand and works well for moderate input sizes.

Why This Is the Right Set

If a point is dominated, keeping it in the output makes no sense because another point is at least as good in every objective and better in at least one. If a point is not dominated by any other point, excluding it would make the set incomplete.

So unlike many optimization problems, the objective is not "pick the best subset by search." The dominance relation itself uniquely determines which points survive.

Faster Special Cases

The naive algorithm is O(n^2), but some special cases can be solved faster.

For two objectives, you can sort by one coordinate and sweep through the other. For example, if smaller values are better in both objectives, sort by the first coordinate and track the best second coordinate seen so far.

1def non_dominated_2d(points):
2    points = sorted(points)
3    result = []
4    best_second = float("inf")
5
6    for x, y in points:
7        if y < best_second:
8            result.append((x, y))
9            best_second = y
10
11    return result
12
13
14points = [(1, 5), (2, 4), (3, 3), (4, 6), (5, 2)]
15print(non_dominated_2d(points))

This kind of optimization becomes more complex in higher dimensions, where the frontier can itself be large.

Duplicates and Equality

You should decide how to treat duplicate points. Under the usual dominance definition, identical points do not dominate each other strictly. That means duplicates may all survive unless you deduplicate them first for presentation or storage reasons.

So there are two separate outputs you might want:

• all non-dominated records, including duplicates
• unique non-dominated value vectors

The algorithm should match the intended output.

Common Pitfalls

The biggest pitfall is misunderstanding "maximum" to mean a hard combinatorial optimization problem over subsets. For a standard Pareto dominance relation, the correct answer is simply the full set of maximal elements.

Another common mistake is mixing objective directions. If one objective is to be minimized and another maximized, the dominance test must reflect that consistently.

Developers also forget that duplicates need a policy. Whether identical points should appear once or many times depends on the application, not on the raw dominance definition alone.

Summary

• The non-dominated set is the Pareto frontier of the input points.
• For a fixed input set, the maximal answer is just all points not dominated by any other point.
• A simple pairwise comparison algorithm runs in O(n^2).
• In low-dimensional special cases, faster sweep-based methods are possible.
• Be explicit about objective directions and duplicate handling before implementing the dominance test.