Online facility location

By Adam Meyerson. Proceedings IEEE International Conference on Cluster Computing, 2001

321 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/8fa146a47927ace433ba93f71d23ed35830bb80e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Organizational Behavior and Human Resource Management

Citations in the corpus

k-means++: the advantages of careful seeding (2007, methodology): “Overall, the seeding technique we propose is similar in spirit to that used by Meyerson [23] for online facility location, and Mishra et al. [12] and Charikar et al. [6] in the context of k-median clustering.”
Data stream clustering: A survey (2013, methodology): “Each chunk of m objects is summarized in 2k representative objects by using a variant of the k-medoids algorithm [Kaufman and Rousseeuw 1990] known as Facility Location [Charikar and Guha 1999; Meyerson 2001].”
Efficient Non-parametric Estimation of Multiple Embeddings per Word in Vector Space (2014, methodology): “In the non-parametric version of our method, we build on facility location (Meyerson, 2001): a new cluster is created with probability proportional to the distance from the context to the”
CAQL: Continuous Action Q-Learning (2019, methodology): “Clustering To reduce the number of max-Q solves further still, we apply online state aggregation (Meyerson, 2001), which picks a number of centroids from the batch of next states B as the centers of p -metric balls with radius b > 0 , such that the union of these balls form a minimum covering of B…”
An Algorithm for Online K-Means Clustering (2014, methodology): “Meyerson [21] suggested a simple and elegant algorithm for the online uncapacitated facility location with competitive ratio of O (log n ) .”
Clustering Data Streams: Theory and Practice (2003, background): “This algorithm runs in time proportional to n times the number of facilities it opens and obtains an expected 8-approximation to optimum [61].”
Creating efficient codebooks for visual recognition (2005, unknown): “Our algorithm: Our proposed strategy combines the advantages of on-line clustering [20] and mean-shift [4] in an undersampling framework [8].”
Improved Online Algorithms for Knapsack and GAP in the Random Order Model (2020, methodology): “The model has also been successfully applied to other problem classes including scheduling [3, 21, 40], packing [1,17,26,28,41], graph problems [9,27,34], facility location [38], budgeted allocation [39], and submodular welfare maximization [31].”
An Online Algorithm for Maximizing Submodular Functions (2008, background): “Likewise, our work is orthogonal to work on online facility location problems [24].”
From Word to Sense Embeddings: A Survey on Vector Representations of Meaning (2018, methodology): “The model applies the online non-parametric clustering procedure of Meyerson (2001) to the task by creating a new sense for a word type only if its similarity (as computed using the current context) to existing senses for the word is less than a parameter λ .”
Streaming-data algorithms for high-quality clustering (2002, background): “This algorithm runs in time proportional to n times the number of facilities it opens and obtains an expected 8-approximation to optimum [24].”