Linear Relaxations for Finding Diverse Elements in Metric Spaces
Choosing a diverse subset of a large collection of points in a metric space is a fundamental problem, with applications in feature selection, recommender systems, web search, data summarization, etc. Various notions of diversity have been proposed, tailored to different applications. The general algorithmic goal is to find a subset of points that maximize diversity, while obeying a cardinality (or more generally, matroid) constraint. The goal of this paper is to develop a novel linear programming (LP) framework that allows us to design approximation algorithms for such problems. We study an objective known as {\em sum-min} diversity, which is known to be effective in many applications, and give the first constant factor approximation algorithm. Our LP framework allows us to easily incorporate additional constraints, as well as secondary objectives. We also prove a hardness result for two natural diversity objectives, under the so-called {\em planted clique} assumption. Finally, we study the empirical performance of our algorithm on several standard datasets. We first study the approximation quality of the algorithm by comparing with the LP objective. Then, we compare the quality of the solutions produced by our method with other popular diversity maximization algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
Data SummarizationDiversityfeature selectionRecommendation SystemsSimilar Papers 제목 키워드 기반
Convex relaxations of structured matrix factorizations
We consider the factorization of a rectangular matrix $X $ into a positive linear combination of rank-one factors of the form $u v^\top$, where $u$ and $v$ belongs to certain sets $\mathcal{U}$ and $\mathcal{V}$, that ma…
Clusters and Coarse Partitions in LP Relaxations
We propose a new class of consistency constraints for Linear Programming (LP) relaxations for finding the most probable (MAP) configuration in graphical models. Usual cluster-based LP relaxations enforce joint consistenc…
Protein DesignShifting-based Optimizable Linear Relaxations for General Activation Functions
The use of neural networks (NNs) is rapidly increasing, including in safety- and security-critical domains. To provide formal guarantees about NN behavior, many verification methods rely on optimizable linear relaxations…
Polynomial Optimization: Enhancing RLT relaxations with Conic Constraints
Conic optimization has recently emerged as a powerful tool for designing tractable and guaranteed algorithms for non-convex polynomial optimization problems. On the one hand, tractability is crucial for efficiently solvi…
Set-based state estimation of nonlinear discrete-time systems using constrained zonotopes and polyhedral relaxations
This paper presents a new algorithm for set-based state estimation of nonlinear discrete-time systems with bounded uncertainties. The novel method builds upon essential properties and computational advantages of constrai…
State Estimation