I detta arbete överväger vi allmän anläggningsplats och sociala problem, där grupper av agenter A och anläggningar F är belägna i ett metriska utrymme, och vårt mål är att tilldela agenter till anläggningar (samt välja vilka anläggningar att öppna) för att optimera den sociala kostnaden. Vi bildar nya algoritmer för att göra detta i närvaro av enbart ordinal information, d.v.s. när de verkliga kostnaderna eller avstånden från agenterna till lokalerna är okända, och endast de ordinala preferenserna hos agenterna för lokalerna är tillgängliga. Den största skillnaden mellan vårt arbete och tidigare arbete inom detta område är att medan vi antar att endast ordinal information om agent preferenser i kända, vi vet de exakta platserna för de möjliga anläggningar F. På grund av denna extra information om anläggningarna, kan vi bilda kraftfulla algoritmer som har liten distorsion, dvs., utföra nästan lika väl som allvetande algoritmer men använder endast ordinal information om agent preferenser. Till exempel, vi presenterar naturliga sociala val mekanismer för att välja en enda möjlighet att öppna med en snedvridning på högst 3 för att minimera både den totala och median sociala kostnaden; denna faktor är bevisligen den bästa möjliga. Vi analyserar många allmänna problem inklusive matchning, k-center, och k-median, och presentera svart-box minskningar från allvetande approximation algoritmer med approximationsfaktor β till ordinal algoritmer med approximation faktor 1 + 2β; gör detta ger nya ordinal algoritmer för många viktiga problem, och upprättar en verktygslåda för att analysera sådana problem i framtiden.
Sociala val och lokaliseringsproblem inom ramen för snedvridning studeras i REF.
Ordinal Approximation for Social Choice, Matching, and Facility Location Problems given Candidate Positions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}