3 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…
math.CO2023
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP
Leonid Gurvits, Nathan Klein, Jonathan Leake
We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem…