6 papers
An optimal deterministic algorithm for finding a strict saddlepoint
Justin Dallant
Given an matrix , a saddlepoint of is an entry that is the maximum in its row and the minimum in its column. It is a strict saddlepoint if no other entry in its…
Quantum Space-Time Tradeoffs for TSP and Hypercube Path via Extremal Set Systems
Justin Dallant
We give a quantum analogue of the extremal set-system framework introduced by Ameli, Nederlof and Wang (FOCS 2026) and Dallant and Kozma (FOCS 2026) for space-time tradeoffs in TSP…
Optimal chain density, entropy, and space-time tradeoffs for the TSP
Alexandr Andoni, Justin Dallant, László Kozma +1
We nearly settle a natural extremal question about set systems over : the tradeoff between the {size} (number of sets) and the number of {full chains}. This question was initi…
Improved space-time tradeoff for TSP via extremal set systems
Justin Dallant, László Kozma
The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximat…
An Optimal Randomized Algorithm for Finding the Saddlepoint
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A \emph{saddlepoint} of an matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum…
Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A saddlepoint of an matrix is an entry of that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding…