Mayank Goswami, The City College and Graduate Center / CUNY

Abstract

In this talk we will consider the sorting with priced information problem, where different comparisons have different costs and the goal is to develop a cheap sorting algorithm. I will present two results (joint with Riko Jacob from ITU Copenhagen): 1. An algorithm for bichromatic sorting that is within O(polylog n) factor of the optimal. This case was left open in the original paper by Charikar et al. [STOC 2000] that introduced priced information. 2. An algorithm for sorting with comparisons costs in {0, 1, n, or infinity}, which is within O(n^{3/4} log n) of the optimal. This result refutes the hypothesis that an existing Omega(n) lower bound for the maximum (which uses costs in 0,1,n, infinity) extends to sorting, and was cited by previous works as the reason why the general sorting problem was bleak and hopeless. The results will be obtained by defining the universal sorting problem, and analyzing instance optimal algorithms for this problem.

See: https://theory.cs.rutgers.edu/theory_seminar