4 papers
A PTAS for Weighted Triangle-free 2-Matching
Miguel Bosch-Calvo, Fabrizio Grandoni, Yusuke Kobayashi +1
In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e…
A -Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni +3
The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a s…
A PTAS for Triangle-Free 2-Matching
Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli
In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph . Our goal is to compute a maximum-cardinality satisfying the following pr…
An O(loglog n)-Approximation for Submodular Facility Location
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo +4
In the Submodular Facility Location problem (SFL) we are given a collection of clients and facilities in a metric space. A feasible solution consists of an assignment of ea…