Polynomial time approximation schemes for all 1-center problems on metric rational set similarities

DOI10.1007/s00453-020-00787-3OpenAlexW3119173924MaRDI QIDQ2663710

Mara Sorella, Michele Gentili, Chris Schwiegelshohn, Marc Bury

Publication date: 19 April 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00787-3

zbMATH Keywords

clusteringpolynomial time approximation schemes1-centerrational set similarity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Uses Software

• ROCK

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized fixed-parameter algorithms for the closest string problem
• Metric and Euclidean properties of dissimilarity coefficients
• The minisum location problem for the Jaccard metric
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Local search for string problems: brute-force is essentially optimal
• Optimal core-sets for balls
• LSH-Preserving Functions and Their Applications
• On the closest string and substring problems
• An Algorithm for the Single Facility Location Problem Using the Jaccard Metric
• Two Algorithms for the Minimum Enclosing Ball Problem
• Closest Substring Problems with Small Distances
• More Efficient Algorithms for Closest String and Substring Problems
• On Finding the Jaccard Center
• A Closer Look at the Closest String and Closest Substring Problem
• Lower Bounds for Approximation Schemes for Closest String
• Approximate minimum enclosing balls in high dimensions using core-sets
• Probability and Computing

This page was built for publication: Polynomial time approximation schemes for all 1-center problems on metric rational set similarities