English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The k-median problem has been widely applied in many research fields such as clustering, logistic center etc. Its approximated algorithm has been interested by many computer theory scientists. In 2006, a reverse greedy algorithm for the metric k-median problem has been proposed by Chrobak and the approximative ratio is proved between Ω(lg(n)/lg(lg(n))) and Ω(lg(n)). In this paper, we present an improved version for the algorithm. In our improved algorithm, there are two central ideas, which include are randomized sample and reverse greedy. We proved the expected approximation ratio of the improved algorithm is 2 ln !! !) !" !! α − 1 + 2 and its running time [ ! (ln  (!))]2n, where n represents the size of the given point set and α denotes the balanced parameter of the given point set.

Metric k-median Problem and Its Application in Reverse Greedy Randomized Algorithm