Universal Sorting: Finding a DAG with Priced Comparisons

Start Date: December 7, 2022
Event Start Time: 11:00 AM
Event End Time: 12:15 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Mayank Goswami - The City College and Graduate Center / CUNY
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
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.

Events