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
| CREATOR | Joshua Marc Könen, Heiko Röglin, Tarek Stuck |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06124