2 papers
cs.DS2025
Dual Charging for Half-Integral TSP
Nathan Klein, Mehrshad Taziki
We show that the max entropy algorithm is a randomized 1.49776 approximation for half-integral TSP, improving upon the previous known bound of 1.49993 from Karlin et al. This also…
cs.DS2025
A Randomized Rounding Approach for DAG Edge Deletion
Sina Kalantarzadeh, Nathan Klein, Victor Reis
In the DAG Edge Deletion problem, we are given an edge-weighted directed acyclic graph and a parameter , and the goal is to delete the minimum weight set of edges so that the re…