A 1.488 approximation algorithm for the uncapacitated facility location problem

By Shi Li. Information and Computation, 2011

384 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/70f6e73d59dbfa8c1540f2595577c44da0a9ce30

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Melanie Schmidt
2. Clemens Rösner
3. David P. Woodruff

In Computer Networks and Communications

1. Melanie Schmidt
2. Clemens Rösner

In Organizational Behavior and Human Resource Management

1. Melanie Schmidt
2. Clemens Rösner
3. Sina Baharlouei
4. Meisam Razaviyayn
5. Maher Nouiehed

Citations in the corpus

• On the cost of essentially fair clusterings (2018, background): “488 -approximated [29], which is very close to the known APX-hardness of 1 .”
• Privacy preserving clustering with constraints (2018, background): “The currently best approximation ratio for facility location is 1.488 [31], while the best lower bound is 1.463 [21].”