A General Approach for Incremental Approximation and Hierarchical Clustering

DOI10.1137/070698257zbMath1209.68648OpenAlexW2064594923MaRDI QIDQ5390609

Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070698257

zbMATH Keywords

hierarchical clusteringfacility locationapproximation algorithms\(k\)-median problemincremental approximation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Theory of computing (68Q99)

Related Items (12)

Incremental network design with shortest paths ⋮ Computing knapsack solutions with cardinality robustness ⋮ Competitive Strategies for Online Clique Clustering ⋮ A 16-competitive algorithm for hierarchical median problem ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ A theory and algorithms for combinatorial reoptimization ⋮ An approximation algorithm for the Euclidean incremental median problem ⋮ Robust Independence Systems ⋮ Online clique clustering ⋮ Unnamed Item ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ General bounds for incremental maximization

This page was built for publication: A General Approach for Incremental Approximation and Hierarchical Clustering