5 papers
Local Search for Fair Max-Min Diversification
Sepideh Mahabadi, Shyam Narayanan, Varun Sivashankar
Given points in a metric space, Max-Min diversification asks for a subset of points maximizing the minimum pairwise distance between the selected points. This is arguably t…
On a Ramsey--Turán variant of Roth's theorem
Matija Bucić, Micha Christoph, Jaehoon Kim +2
A classical theorem of Roth states that the maximum size of a solution-free set of a homogeneous linear equation in is if and only if the sum of…
Intersecting hypergraphs with large cover number
Matija Bucić, Vanshika Jain, Varun Sivashankar
In their famous 1974 paper introducing the local lemma, Erdős and Lovász posed a question-later referred by Erdős as one of his three favorite open problems: What is the minimum nu…
Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
Given a set of vectors in , the goal of the \emph{determinant maximization} problem is to pick vectors with the maximum volume. Determinant maximization is th…
Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints
Varun Suriyanarayana, Varun Sivashankar, Siddharth Gollapudi +1
The joint replenishment problem (JRP) is a classical inventory management problem. We consider a natural generalization with outliers, where we are allowed to reject (that is, not…