An O(loglog n)-Approximation for Submodular Facility Location

Speaker(s)

Krzysztof Sornat

Affiliation

AGH University of Science and Technology

Language of the talk

English

Date

Nov. 7, 2024, noon

Information about the event

online

Seminar

Seminar Games, Mechanisms, and Social Networks

---

In the Submodular Facility Location problem (SFL) we are given a collection of n clients and m facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility f to which we assign the subset of clients S^f, one has to pay the opening cost g(S^f), where g() is a monotone submodular function with g(emptyset)=0. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA’06] gave the current-best O(log n) approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an O(loglog n) approximation.

Based on the following paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.5

---