4 papers · 1 filter
A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
Sophia Saller, Jana Koehler, Andreas Karrenbauer
The traveling salesman (or salesperson) problem, short TSP, is a problem of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP vari…
Improving Order with Queues
Andreas Karrenbauer, Kurt Mehlhorn, Pranabendu Misra +4
Given a sequence of numbers and parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that queues suffice to sort…
Algorithm Engineering of SSSP With Negative Edge Weights
Alejandro Cassis, Andreas Karrenbauer, André Nusser +1
Computing shortest paths is one of the most fundamental algorithmic graph problems. It is known since decades that this problem can be solved in near-linear time if all weights are…
Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices
Angikar Ghosal, Andreas Karrenbauer
We investigate structural properties of the binary rank of Kronecker powers of binary matrices, equivalently, the biclique partition numbers of the corresponding bipartite graphs.…