I detta dokument överväger vi en generalisering av det klassiska k-centrumproblemet med kapacitet. Vårt mål är att välja k centra i en graf, och tilldela varje nod till en närliggande centrum, så att vi respekterar kapacitetsbegränsningar på centra. Målet är att minimera det maximala avståndet en nod måste resa för att komma till sitt tilldelade centrum. Detta problem är NP -hård, även när centra inte har några kapacitetsbegränsningar och optimal faktor 2 approximation algoritmer är kända. Med kapacitet, när alla centra har identiska kapaciteter, är en 6 approximation känd med inga bättre lägre gränser än för den oändliga kapacitetsversionen. Även om många generaliseringar och variationer av detta problem har studerats i stor utsträckning, gjordes inga framsteg med den kapacierade versionen för en allmän kapacitetsfunktion. Vi utvecklar den första konstant faktor approximation algoritm för detta problem. Vår algoritm använder en LP-avrundningsmetod för att lösa detta problem, och fungerar för fall av icke-uniform hård kapacitet, när flera kopior av en nod inte kan väljas och kan utvidgas till fallet när det finns en hård bunden på antalet kopior av en nod som kan väljas. Slutligen, för icke-uniforma mjuka kapaciteter presenterar vi en mycket enklare 11 approximationsalgoritm, som vi finner som ytterligare bevis på att hårda kapaciteter är mycket svårare att hantera.
Två decennier efter de första algoritmerna för det enhetliga fallet tillhandahöll REF den första konstanta faktor approximationen för icke-uniform kapacitet.
LP Rounding for k-Centers with Non-uniform Hard Capacities
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}