Efficient approximation algorithms for the Hamming center problem

Leszek Gasieniec; Jesper Andreas Jansson; Andrzej Lingas

Efficient approximation algorithms for the Hamming center problem

Leszek Gasieniec
, Jesper Andreas Jansson
, Andrzej Lingas

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

52 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 language	English
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)
Publisher	SIAM
Publication status	Published - 1 Jan 1999
Externally published	Yes
Event	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999 - Baltimore, MD, United States Duration: 17 Jan 1999 → 19 Jan 1999

Conference

Conference	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999
Country/Territory	United States
City	Baltimore, MD
Period	17/01/99 → 19/01/99

ASJC Scopus subject areas

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

Cite this

@inproceedings{a48376382d1840b697c0e92d446ead1f,

title = "Efficient approximation algorithms for the Hamming center problem",

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.",

author = "Leszek Gasieniec and Jansson, \{Jesper Andreas\} and Andrzej Lingas",

year = "1999",

month = jan,

day = "1",

language = "English",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)",

publisher = "SIAM",

note = "Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999 ; Conference date: 17-01-1999 Through 19-01-1999",

}

Efficient approximation algorithms for the Hamming center problem. / Gasieniec, Leszek; Jansson, Jesper Andreas; Lingas, Andrzej.
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999). SIAM, 1999.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Efficient approximation algorithms for the Hamming center problem

AU - Gasieniec, Leszek

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0032762037

M3 - Conference article published in proceeding or book

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)

PB - SIAM

T2 - Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999

Y2 - 17 January 1999 through 19 January 1999

ER -

Efficient approximation algorithms for the Hamming center problem

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this