Approximation algorithms for Hamming clustering problems

DOI10.1016/S1570-8667(03)00079-0MaRDI QIDQ876719zbMATH OpenOpenAlexFDO

Authors Leszek Gąsieniec, Jesper Jansson, Andrzej Lingas

Publication date 26 April 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1570-8667(03)00079-0

zbMATH Keywords

Hamming distanceinteger programmingapproximation algorithms\(p\)-clustering problemnp-hardness

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1615274
• The center location improvement problem under the Hamming distance
• scientific article; zbMATH DE number 1305511
• On the Efficiency of the Hamming C-Centerstring Problems
• Clustering to minimize the maximum intercluster distance

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• scientific article; zbMATH DE number 1305511 (Why is no real title available?)
• scientific article; zbMATH DE number 871893 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• Algorithms on Strings, Trees and Sequences
• Approximation algorithms for NP-hard problems.
• Clustering to minimize the maximum intercluster distance
• Finding similar regions in many strings
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• On covering problems of codes
• On the complexity of integer programming

Cited in

(9)

• A new class of weighted similarity indices using polytomous variables
• Low-Rank Binary Matrix Approximation in Column-Sum Norm.
• scientific article; zbMATH DE number 1615274 (Why is no real title available?)
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• Clustering, Hamming Embedding, Generalized LSH and the Max Norm
• On the interpoint distances of Bernoulli vectors
• On the parameterized complexity of clustering problems for incomplete data
• Anonymizing binary and small tables is hard to approximate
• The complexity of binary matrix completion under diameter constraints

This page was built for publication: Approximation algorithms for Hamming clustering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876719)