polynomial time approximation scheme

Closing the Gap: Efficient Algorithms for Discrete Wasserstein Barycenters

  • Jiaqi Wang
  • Weijun Xie
    • Categories Integer Programming, Optimization in Data Science Tags , , , ,

    The Wasserstein barycenter problem seeks a probability measure that minimizes the weighted average of the Wasserstein distances to a given collection of probability measures. We study the discrete setting, where each measure has finite support — a regime that frequently arises in machine learning and operations research. The discrete Wasserstein barycenter problem is known to … Read more

    A PTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics

  • T-H. Hubert Chan
  • Shaofeng H.-C. Jiang
    • Categories Approximation Algorithms Tags , , ,

    We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion … Read more