Efficient approximation algorithms for the Hamming center problem

Leszek Gasieniec, Jesper Andreas Jansson, Andrzej Lingas

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

38 Citations (Scopus)

Abstract

The Hamming center problem for a set S of k binary strings, each of length n, is to find a binary string β of length n that minimizes the maximum Hamming distance between β and any string in S. Its decision version is known to be NP-complete. We provide several approximation algorithms for the Hamming center problem. Our main result is a randomized (4/3+ε) approximation algorithm running in polynomial time if the Hamming radius of S is at least superlogarithmic in k. Furthermore, we show how to find in polynomial time a set B of O(log k) strings of length n such that for each string in S there is at least one string in B within Hamming distance not exceeding the radius of S.
Original languageEnglish
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)
PublisherSIAM
Publication statusPublished - 1 Jan 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999 - Baltimore, MD, United States
Duration: 17 Jan 199919 Jan 1999

Conference

ConferenceProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999
CountryUnited States
CityBaltimore, MD
Period17/01/9919/01/99

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Cite this