Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives. (arXiv:1911.09813v1 [cs.GT])

We consider the facility location problem in the one-dimensional setting
where each facility can serve a limited number of agents from the algorithmic
and mechanism design perspectives. From the algorithmic perspective, we prove
that the corresponding optimization problem, where the goal is to locate
facilities to minimize either the total cost to all agents or the maximum cost
of any agent is NP-hard. However, we show that the problem is fixed-parameter
tractable, and the optimal solution can be computed in polynomial time whenever
the number of facilities is bounded, or when all facilities have identical
capacities. We then consider the problem from a mechanism design perspective
where the agents are strategic and need not reveal their true locations. We
show that several natural mechanisms studied in the uncapacitated setting
either lose strategyproofness or a bound on the solution quality for the total
or maximum cost objective. We then propose new mechanisms that are
strategyproof and achieve approximation guarantees that almost match the lower

Source link

Related posts

#10: Human + Machine: Reimagining Work in the Age of AI


Facebook’s $500k deepfake-detector AI contest drama: Winning team disqualified on buried consent technicality


Let’s save the bees with machine learning


This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More

Privacy & Cookies Policy


COVID-19 (Coronavirus) is a new illness that is having a major effect on all businesses globally LIVE COVID-19 STATISTICS FOR World