An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
From MaRDI portal
Publication:2391186
DOI10.1007/s00453-007-9142-2zbMath1194.68258OpenAlexW2177686805MaRDI QIDQ2391186
Benjamin Birnbaum, Kenneth J. Goldman
Publication date: 24 July 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1179&context=cse_research
Related Items (10)
Result diversification by multi-objective evolutionary algorithms with theoretical guarantees ⋮ Away from each other ⋮ Obtaining approximately optimal and diverse solutions via dispersion ⋮ An Improved Analysis of Local Search for Max-Sum Diversification ⋮ Efficient Approximations for the Online Dispersion Problem ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Unnamed Item ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Max-min dispersion on a line ⋮ Maximization problems of balancing submodular relevance and supermodular diversity
Cites Work
- Unnamed Item
- An improved approximation ratio for the minimum latency problem
- Approximation algorithms for maximum dispersion
- Maximum dispersion and geometric maximum weight cliques
- Facility dispersion problems under capacity and cost constraints
- Approximation Algorithms for Dispersion Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- AdWords and generalized online matching
- A new greedy approach for facility location problems
- Obnoxious Facility Location on Graphs
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
- Heuristic and Special Case Algorithms for Dispersion Problems
- Finding Subsets Maximizing Minimum Structures
- Obtaining online approximation algorithms for facility dispersion from offline algorithms
- Maximum dispersion problem in dense graphs
- The dense \(k\)-subgraph problem
- Approximation of geometric dispersion problems
This page was built for publication: An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
