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

The Capacitated Facility Location (CFL), a long-standing classic problem withintriguing approximability and literature dated back to the 90s, is considered.Following the open question posted in [Williamson and Shmoys, 2011] and thenotable work due to [An et al., FOCS~2014], we present an LP-basedapproximation algorithm with a guarantee of $(10+\sqrt{67})/2 \approx 9.0927$,a significant improvement upon the previous LP-based ratio of $288$ due to Anet al. in 2014. Our contribution for this part is a simple and elegant roundingalgorithm that brings clear insights for the MFN relaxation and the CFLproblem.  For CFL with cardinality facility cost (CFL-CFC), we present an LP-based$4$-approximation algorithm, which improves upon the decades-old ratio of 5 dueto Levi et al. that ages up since 2004. Prior to our work, it was not clearwhether or not LP-based methods can be used to provide a guarantee better than5 for the CFL problem, even for restricted versions of this problem, for whichnatural LPs are already known to have small integrality gaps. Our roundingalgorithm provides the first affirmative answer on the case with cadinalityfacility cost.

Improved LP-based Approximation Algorithms for Facility Location with Hard Capacities