Showing 2023Show all
2 papers · 1 filter
cs.DS2023
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio
Mayank Goswami, Riko Jacob
The problem of sorting with priced information was introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparison…
cs.DS2023
Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A saddlepoint of an matrix is an entry of that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding…