Artykuł w czasopiśmie
Brak miniatury
Licencja

CC-BYCC-BY - Uznanie autorstwa
 

Constant-factor FPT approximation for capacitated k-median

dc.abstract.enCapacitated k-median is one of the few outstanding optimization problems for which the existence of a polynomial time constant factor approximation algorithm remains an open problem. In a series of recent papers algorithms producing solutions violating either the number of facilities or the capacity by a multiplicative factor were obtained. However, to produce solutions without violations appears to be hard and potentially requires different algorithmic techniques. Notably, if parameterized by the number of facilities k, the problem is also W[2] hard, making the existence of an exact FPT algorithm unlikely. In this work we provide an FPT-time constant factor approximation algorithm preserving both cardinality and capacity of the facilities. The algorithm runs in time 2^O(k log k) n^O(1) and achieves an approximation ratio of 7+epsilon.
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2019-09-11
dc.conference.datestart2019-09-09
dc.conference.placeMunich/Garching
dc.conference.series27th Annual European Symposium on Algorithms
dc.conference.series27th Annual European Symposium on Algorithms
dc.conference.shortcutESA 2019
dc.contributor.authorMarcinkowski, Jan
dc.contributor.authorByrka, Jarosław
dc.contributor.authorMeesum, Syed Mohammad
dc.contributor.authorWłodarczyk, Michał
dc.contributor.authorAdamczyk, Marek
dc.date.accessioned2024-01-24T20:07:40Z
dc.date.available2024-01-24T20:07:40Z
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ESA.2019.1
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/103594
dc.identifier.weblinkhttps://doi.org/10.4230/LIPIcs.ESA.2019.1
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1:1-1:14
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.enK-median
dc.subject.enClustering
dc.subject.enApproximation Algorithms
dc.subject.enFixed Parameter Tractability
dc.titleConstant-factor FPT approximation for capacitated k-median
dc.typeJournalArticle
dspace.entity.typePublication