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

Mount Sinai opens biomedical blockchain research center


Batch weight for domain adaptation with mass shift. (arXiv:1905.12760v1 [cs.LG])


Illumina Releases Open Source AI Software


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