Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Stochastic Minimum Spanning Trees with a Single Sample
Ruben Hoeksma, Gavin Speek, Marc Uetz
We consider the minimum spanning tree problem in a setting where the edge weights are stochastic from unknown distributions, and the only available information is a single sample o…
cs.DS2018
A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma +1
In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that vi…