6 sierpnia 2024 11:15
[Seminarium ZOK] Mayank Goswami: On Instance Optimal Algorithms for Sorting Nuts and Bolts and Sorting with Priced Information
Abstract: In this talk we will discuss instance-optimal algorithms for three variants of classical comparison-based sorting: bichromatic sorting, bipartite sorting, and sorting with priced information. For all of the problems, we will give algorithms that are either almost-instance-optimal, or improve upon previously known algorithms. Of particular interest is a new definition of instance optimality that is applicable to many other problems and generalizes previous notions of instance optimality in existing literature.
Joint work with Riko Jacob at ITU Copenhagen, appearing at ITCS 2024 and APPROX 2024.