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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we study the uniform capacitated k-median problem. In the problem, we are given a set F of potential facility locations, a set C of clients, a metric d over F ∪ C, an upper bound k on the number of facilities we can open and an upper bound u on the number of clients each facility can serve. We need to open a subset S ⊆ F of k facilities and connect clients in C to facilities in S so that each facility is connected by at most u clients. The goal is to minimize the total connection cost over all clients. Obtaining a constant approximation algorithm for this problem is a notorious open problem; most previous works gave constant approximations by either violating the capacity constraints or the cardinality constraint. Notably, all these algorithms are based on the natural LP-relaxation for the problem. The LP-relaxation has unbounded integrality gap, even when we are allowed to violate the capacity constraints or the cardinality constraint by a factor of 2 − ε. Our result is an exp(O(1/ε2))-approximation algorithm for the problem that violates the cardinality constraint by a factor of 1 + ε. That is, we find a solution that opens at most (1 + ε)k facilities whose cost is at most exp(O(1/ε2)) times the optimum solution when at most k facilities can be open. This is already beyond the capability of the natural LP relaxation, as it has unbounded integrality gap even if we are allowed to open (2 − ε)k facilities. Indeed, our result is based on a novel LP for this problem. We hope that this LP is the first step towards a constant approximation for capacitated k-median. The version as we described is the hard-capacitated version of the problem, as we can only open one facility at each location. This is as opposed to the soft-capacitated version, in which we are allowed to open more than one facilities at each location. The hard-capacitated version is more general, since one can convert a soft-capacitated instance to a hard-capacitated instance by making enough copies of each facility location. We give a simple proof that in the uniform capacitated case, the soft-capacitated version and the hard-capacitated version are actually equivalent, up to a small constant loss in the approximation ratio. Moreover, we show that the given potential facility locations do not matter: we can assume F = C.

On Uniform Capacitated k -Median Beyond the Natural LP Relaxation