9 papers · 1 filter
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…