4 papers
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…