An Improved Analysis of Local Search for Max-Sum Diversification
From MaRDI portal
Publication:5108253
DOI10.1287/moor.2018.0982zbMath1437.90134OpenAlexW2974768792MaRDI QIDQ5108253
Friedrich Eisenbrand, Rico Zenklusen, Alfonso Cevallos
Publication date: 30 April 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.2018.0982
dispersionlocal searchsubmodular maximizationmatroid constraintsnegative type distancesremote clique
Analysis of algorithms and problem complexity (68Q25) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Approximation algorithms for maximum dispersion
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Maximum dispersion and geometric maximum weight cliques
- An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
- Metric spaces and completely monontone functions
- Randomized Rounding for the Largest Simplex Problem
- Max-sum diversity via convex programming
- A threshold of ln n for approximating set cover
- The Dissimilarity Representation for Pattern Recognition
- Introduction to Information Retrieval
- Similarity estimation techniques from rounding algorithms
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Heuristic and Special Case Algorithms for Dispersion Problems
- Local Search for Max-Sum Diversification
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Metric Transforms and Euclidean Embeddings
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- Comments on bases in dependence structures
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Geometry of cuts and metrics
- Unnamed Item
- Unnamed Item
This page was built for publication: An Improved Analysis of Local Search for Max-Sum Diversification
