3 papers
cs.DS2026
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +1
The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients and a set of facilities in a metric space $(C \…
cs.DS2025
A Approximation for -Vertex-Connectivity
Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph . Ou…
cs.DS2024
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
JarosÅaw Byrka, Fabrizio Grandoni, Vera Traub
The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task i…