4 papers · 1 filter
On Diverse Solutions to Max-k-CSP and Bounded Degree k-SAT
Mayank Goswami, Adarsh Srinivasan
We study the problem of generating diverse solutions to Max--CSP and bounded-degree -SAT, focusing on two distinct metrics: constraint diversity and variable diversity. For c…
How many users have been here for a long time? Efficient solutions for counting long aggregated visits
Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz +3
This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given users and regions, where each user spends some time visiting som…
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…
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
Mayank Goswami, Riko Jacob
We generalize the classical nuts and bolts problem to a setting where the input is a collection of nuts and bolts, and there is no promise of any matching pairs. It is not…