An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
From MaRDI portal
Publication:2391186
DOI10.1007/S00453-007-9142-2zbMATH Open1194.68258OpenAlexW2177686805MaRDI QIDQ2391186FDOQ2391186
Authors: 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
Recommendations
- An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
- Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Greedy maximum-clique decompositions
- LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
- Clustered maximum weight clique problem: algorithms and empirical analysis
- A note on improved results for one round distributed clique listing
- Worst-case analysis of clique MIPs
- An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
- The greedy clique decomposition of a graph
Cites Work
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- AdWords and generalized online matching
- The dense \(k\)-subgraph problem
- An improved approximation ratio for the minimum latency problem
- 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
- Maximum dispersion problem in dense graphs
- Approximation of geometric dispersion problems
- Approximation algorithms for maximum dispersion
- Maximum dispersion and geometric maximum weight cliques
- Approximation algorithms for dispersion problems
- Title not available (Why is that?)
- Facility dispersion problems under capacity and cost constraints
- Finding Subsets Maximizing Minimum Structures
- Obtaining online approximation algorithms for facility dispersion from offline algorithms
Cited In (11)
- Title not available (Why is that?)
- Efficient Approximations for the Online Dispersion Problem
- Away from each other
- An improved analysis of local search for max-sum diversification
- Weakly Submodular Function Maximization Using Local Submodularity Ratio.
- Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
- 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
- Obtaining approximately optimal and diverse solutions via dispersion
- An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
This page was built for publication: An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391186)
