approximation algorithms 1discounted traversal 1graph search 1norm objectives 1traveling salesman problem 1
From the 1 of 3 linked papers with an AI index.
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Approximation Algorithms for Discounted Graph Search with Norm Objectives
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm
The paper proposes a unified model for graph search and routing problems that incorporates discounted edge costs and a p‑norm objective, and provides constant‑factor approximation…
cs.DS2024
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
Yann Disser, Svenja M. Griesbach, Max Klimm +1
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously ap…