Fabrizio Grandoni

A PTAS for triangle-free 2-matching

Abstract In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph $$G=(V,E)$$ G = ( V , E ) . Our goal is to compute a maximum-cardinality $$M\subseteq E$$ M ⊆ E satisfying the following properties: (1) at most two edges of M are incident on each node (i....

The Bidirected Cut Relaxation for Steiner Tree Has Integrality Gap Smaller than 2

Abstract. 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 is to compute a minimum-weight tree containing all terminals (and possibly further vertices...

A \({(2+\varepsilon )}\)-Approximation Algorithm for Metric \({k}\)-Median

Abstract. In the classical NP-hard (metric) [Formula: see text]-median problem, we are given a set of [Formula: see text] clients and centers with metric distances between them, along with an integer parameter [Formula: see text]. The objective is to select a subset of [Formula:...