Nathan Klein

zbMath Openklein.nathanMaRDI QIDQ5144893

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Matroid partition property and the secretary problem	2024-09-25	Paper
An improved approximation algorithm for the minimum k -edge connected multi-subgraph problem Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP	2023-11-15	Paper
A (slightly) improved approximation algorithm for metric TSP Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
A deterministic better-than-3/2 approximation algorithm for metric TSP Integer Programming and Combinatorial Optimization	2023-11-09	Paper
A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP Integer Programming and Combinatorial Optimization	2023-11-09	Paper
A Lower Bound for the Max Entropy Algorithm for TSP	2023-11-03	Paper
Matroid Partition Property and the Secretary Problem	2021-11-24	Paper
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP	2021-05-20	Paper
An improved approximation algorithm for TSP in the half integral case Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing	2021-01-19	Paper
An Improved Approximation Algorithm for TSP in the Half Integral Case	2019-08-01	Paper
Ghost Value Augmentation for $k$-Edge-Connectivity	N/A	Paper

Research outcomes over time

This page was built for person: Nathan Klein