7 papers
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…
Computing Diverse and Nice Triangulations
Waldo Gálvez, Mayank Goswami, Arturo Merino +2
We initiate the study of computing diverse triangulations to a given polygon. Given a simple -gon , an integer , a quality measure on the set of triangulation…
A Framework for the Design of Efficient Diversification Algorithms for Packing and Covering Problems
Waldo Gálvez, Mayank Goswami, Arturo Merino +3
There has been considerable recent interest in computing a diverse collection of solutions to a given optimization problem. Given a classical optimization problem (e.g., minimu…
Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
Per Austrin, Ioana O. Bercea, Mayank Goswami +2
Given a -CNF formula and an integer , we study algorithms that obtain solutions to the formula that are maximally dispersed. For , the problem of computing the diame…
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…