License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.25
URN: urn:nbn:de:0030-drops-73190
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7319/
Amir, Amihood ;
Levy, Avivit ;
Lewenstein, Moshe ;
Lubin, Ronit ;
Porat, Benny
Can We Recover the Cover?
Abstract
Data analysis typically involves error recovery and detection of regularities as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A common notion of regularity in strings is that of a cover. Data describing measures of a natural coverable phenomenon may be corrupted by errors caused by the measurement process, or by the inexact features of the phenomenon itself. Due to this reason, different variants of approximate covers have been introduced, some of which are NP-hard to compute. In this paper we assume that the Hamming distance metric measures the amount of corruption experienced, and study the problem of recovering the correct cover from data corrupted by mismatch errors, formally defined as the cover recovery problem (CRP). We show that for the Hamming distance metric, coverability is a powerful property allowing detecting the original cover and correcting the data, under suitable conditions.
We also study a relaxation of another problem, which is called the approximate cover problem (ACP). Since the ACP is proved to be NP-hard [Amir,Levy,Lubin,Porat, CPM 2017], we study a relaxation, which we call the candidate-relaxation of the ACP, and show it has a polynomial time complexity. As a result, we get that the ACP also has a polynomial time complexity in many practical situations. An important application of our ACP relaxation study is also a polynomial time algorithm for the cover recovery problem (CRP).
BibTeX - Entry
@InProceedings{amir_et_al:LIPIcs:2017:7319,
author = {Amihood Amir and Avivit Levy and Moshe Lewenstein and Ronit Lubin and Benny Porat},
title = {{Can We Recover the Coverl}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {25:1--25:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-039-2},
ISSN = {1868-8969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7319},
URN = {urn:nbn:de:0030-drops-73190},
doi = {10.4230/LIPIcs.CPM.2017.25},
annote = {Keywords: periodicity, quasi-periodicity, cover, approximate cover, data recovery}
}
|
Keywords: |
|
periodicity, quasi-periodicity, cover, approximate cover, data recovery |
|
Collection: |
|
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
30.06.2017 |
