Approximation algorithms for Hamming clustering problems

DOI10.1016/S1570-8667(03)00079-0zbMATH Open1118.68762OpenAlexW2033556263MaRDI QIDQ876719FDOQ876719

Jesper Jansson, Andrzej Lingas, Leszek Gąsieniec

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

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

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)

Cites Work

• Title not available (Why is that?)
• Algorithms on Strings, Trees and Sequences
• Title not available (Why is that?)
• On covering problems of codes
• Clustering to minimize the maximum intercluster distance
• A Best Possible Heuristic for the k-Center Problem
• On the complexity of integer programming
• Finding similar regions in many strings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Title not available (Why is that?)

Cited In (9)

• A new class of weighted similarity indices using polytomous variables
• Low-Rank Binary Matrix Approximation in Column-Sum Norm.
• Title not available (Why is that?)
• 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)