Cover Image

Improved space-time tradeoff for TSP via extremal set systems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dallant, Justin, Kozma, László
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

Non-adaptive Bellman-Ford: Yen's improvement is optimal
by: Hu, Jialu, et al.
Published: (2024)

Optimization with pattern-avoiding input
by: Berendsohn, Benjamin Aram, et al.
Published: (2023)

Balanced TSP partitioning
by: Berendsohn, Benjamin Aram, et al.
Published: (2025)

Better approximation guarantee for Asymmetric TSP
by: Vygen, Jens
Published: (2026)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p
by: Bell, Tolson, et al.
Published: (2023)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Compact representations of pattern-avoiding permutations
by: Kozma, László, et al.
Published: (2025)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)

Enumerating all minimal hitting sets in polynomial total time
by: Wild, Marcel
Published: (2023)

A General Technique for Searching in Implicit Sets via Function Inversion
by: Aronov, Boris, et al.
Published: (2023)

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
by: Biedl, Therese
Published: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
by: Gutekunst, Samuel C.
Published: (2025)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2020)

Theoretical Analysis of Byte-Pair Encoding
by: Kozma, László, et al.
Published: (2024)

Representative set statements for delta-matroids and the Mader delta-matroid
by: Wahlström, Magnus
Published: (2023)

Lower bounds for graph reconstruction with maximal independent set queries
by: Michel, Lukas, et al.
Published: (2024)

Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs
by: Fang, Qiming, et al.
Published: (2026)

Improved exploration of temporal graphs
by: Bastide, Paul, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

(No) Quantum space-time tradeoff for USTCON
by: Apers, Simon, et al.
Published: (2022)

Cover time of random subgraphs of the hypercube
by: Cooper, Colin, et al.
Published: (2025)

Treewidth of the $n \times n$ toroidal grid
by: Gima, Tatsuya, et al.
Published: (2026)

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
by: Bodwin, Greg, et al.
Published: (2023)

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
by: Leung, Yui Hin Arvin
Published: (2025)

Fast Rational Search via Stern-Brocot Tree
by: Weyers, Connor, et al.
Published: (2025)

A Unified View of Graph Regularity via Matrix Decompositions
by: Bodwin, Greg, et al.
Published: (2019)

Improved FPT Approximation for Non-metric TSP
by: Bampis, Evripidis, et al.
Published: (2024)

A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem
by: Arslanoğlu, Yılmaz
Published: (2026)

Fast computation of permanents over $\mathbb{F}_3$ via $\mathbb{F}_2$ arithmetic
by: Scheinerman, Danny
Published: (2024)

A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order
by: Glover, Charles N.
Published: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
by: Jenssen, Matthew, et al.
Published: (2023)