2 citations · 2 across the 7 of their papers we have counts for
10 papers
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Marek Eliáš, Fabrizio Grandoni, Adam Polak +1
The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent effor…
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
We give a new dual fitting algorithm which gives improved approximation ratios of and for -Means in (high-dimensional) Euclidean and genera…
An Improved Greedy Approximation for (Metric) -Means
Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao +3
Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the -Means…
FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
Fabrizio Grandoni, Anupam Gupta, Jatin Yadav
In the classical Min-Sum Radii problem (MSR) we are given a set of points in a metric space and a positive integer . Our goal is to partition into subsets…
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 Algorithm for Metric -Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +2
In the classical NP-hard metric -median problem, we are given a set of clients and centers with metric distances between them, along with an integer parameter . The…
On the Bidirected Cut Relaxation for Steiner Forest
Jarosław Byrka, Fabrizio Grandoni, Vera Traub
The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of ver…
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…
Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
Fabrizio Grandoni, Edin Husić, Mathieu Mari +1
In the maximum independent set of convex polygons problem, we are given a set of convex polygons in the plane with the objective of selecting a maximum cardinality subset of no…
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…