Provable randomized rounding for minimum-similarity diversification

DOI10.1007/S10618-021-00811-2MaRDI QIDQ2134050zbMATH OpenOpenAlexFDO

Authors Bruno Ordozgoiti, Ananth Mahadevan, Antonis Matakos, Aristides Gionis

Publication date 5 May 2022

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10618-021-00811-2

zbMATH Keywords

quadratic programmingdiversificationrandomized rounding

Mathematics Subject Classification ID

Quadratic programming (90C20) Computational aspects of data analysis and big data (68T09) Combinatorial probability (60C05)

Recommendations

• Max-sum diversification, monotone submodular functions, and dynamic updates
• Max-sum diversity via convex programming
• Local Search for Max-Sum Diversification
• An improved analysis of local search for max-sum diversification
• scientific article; zbMATH DE number 6961717

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 777866 (Why is no real title available?)
• A dependent LP-rounding approach for the \(k\)-median problem
• A proof of the Shepp-Olkin entropy concavity conjecture
• An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
• An algorithm for quadratic zero-one programs
• An analysis of approximations for maximizing submodular set functions—I
• Approximating the sparsest \(k\)-subgraph in chordal graphs
• Approximation algorithms for dispersion problems
• Approximation algorithms for diversified search ranking
• Approximation algorithms for indefinite quadratic programming
• Interior-point methods
• Max-sum diversification, monotone submodular functions, and dynamic updates
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• On the Distribution of the Number of Successes in Independent Trials
• On the Distribution of the Number of Successes in Independent Trials
• On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
• QPLIB: a library of quadratic programming instances
• Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
• Quadratic maximization and semidefinite relaxation
• Randomized rounding in the presence of a cardinality constraint
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• STACS 2005
• The design of approximation algorithms
• The indefinite zero-one quadratic problem

Describes a project that uses

Uses Software

• LETOR
• QPLIB
• Cython
• UCI

This page was built for publication: Provable randomized rounding for minimum-similarity diversification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2134050)