10 papers
A Better-than-2 Approximation for k-Median Part I: The Power of General Bids
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus th…
A Better-than- Approximation for -Median Part II: Stable Instances
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6
We consider the -median problem on general metric spaces, subject to the condition that the instances are -stable (i.e., the optimal solution using centers has a cost a…
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality
Aditi Laddha, Madhusudhan Reddy Pittu
Computing the permanent of a non-negative matrix is a computationally challenging, \#P-complete problem with wide-ranging applications. We introduce a novel permanental analogue of…
Max-Cut with Multiple Cardinality Constraints
Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian
We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph , a partition of the vert…
Guessing Efficiently for Constrained Subspace Approximation
Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu +2
In this paper we study constrained subspace approximation problem. Given a set of points in , the goal of the {\em subspace approximation} pr…
Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs
Adam Brown, Aditi Laddha, Madhusudhan Reddy Pittu +1
In an instance of the weighted Nash Social Welfare problem, we are given a set of indivisible items, , and agents, , where each agent $i \in \math…
The Price of Explainability for Clustering
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson +1
Given a set of points in -dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 20…
Efficient Determinant Maximization for All Matroids
Adam Brown, Aditi Laddha, Madhusudhan Pittu +1
Determinant maximization provides an elegant generalization of problems in many areas, including convex geometry, statistics, machine learning, fair allocation of goods, and networ…
Determinant Maximization via Matroid Intersection Algorithms
Adam Brown, Aditi Laddha, Madhusudhan Pittu +2
Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics \cite{pukelsheim2006optimal}, convex geometry \cite{Khach…