3 papers
cs.DS2023
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…
cs.DS2023
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
Marvin Künnemann, Bodo Manthey, Rianne Veenstra
The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of…
cs.DS2010
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements
Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigat…