Parameterized Algorithms for Computing Pareto Sets

Joshua Marc Könen, Heiko Röglin, Tarek Stuck · 2025

Read Parameterized Algorithms for Computing Pareto Sets by Joshua Marc Könen, Heiko Röglin, Tarek Stuck (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06124.txt.

Description

Computing all trade-off-optimal solutions, the Pareto set, for problems with several goals is the subject of a 2025 paper by Joshua Könen and two co-authors. Their tool is dynamic programming over tree decompositions, a standard parameterized technique whose power for multiobjective problems was unclear. The team first settles the multicriteria s-t cut problem.

The same machinery then handles a polygon aggregation problem from cartography, the multiobjective minimum spanning tree, and the traveling salesman problem. Running times depend on treewidth and the largest intermediate Pareto set. An implementation with a purpose-built data structure and heuristics solves real polygon instances of treewidth up to twenty-two, and a preprocessing study compares decomposition choices. The work shows tree-based dynamic programming can carry multiobjective optimization further than expected.

Catalog record

CREATORJoshua Marc Könen, Heiko Röglin, Tarek Stuck
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06124

Browse the full library · About the Tower of Babel