More Web Proxy on the site http://driver.im/

article

The Minimum Substring Cover problem

Authors:

Danny Hermelin,

Stéphane VialetteAuthors Info & Claims

Information and Computation, Volume 206, Issue 11

Pages 1303 - 1312

https://doi.org/10.1016/j.ic.2008.06.002

Published: 01 November 2008 Publication History

Abstract

In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms-the local-ratio technique and linear programming rounding.

References

[1]

P. Alimonti, V. Kann, Hardness of approximating problems on cubic graphs, in: Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC), 1997.

[2]

Bar-Yehuda, R., One for the price of two: a unified approach for approximating covering problems. Algorithmica. v27 i2. 131-144.

[3]

Bar-Yehuda, R. and Even, S., A linear time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms. v2. 198-203.

[4]

Bar-Yehuda, R. and Even, S., A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics. v25. 27-46.

[5]

Bodlaender, H., Downey, R., Fellows, M., Hallett, M. and Wareham, H., Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences. v11 i1. 49-57.

[6]

Choffrut, C. and Karhumäki, J., Combinatorics of words. In: Rozenberg, G., Salomaa, A. (Eds.), Handbook of Formal Languages, Springer-Verlag.

[7]

Chvátal, V., A greedy heuristic for the set-covering problem. Mathematics of Operations Research. v4 i3. 233-235.

[8]

Dinur, I., Guruswami, V., Khot, S. and Regev, O., A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing. v34 i5. 1129-1146.

[9]

Dorit, R. and Gilbert, W., The limited universe of exons. Current Opinions in Structural Biology. v1. 973-977.

[10]

Ehrenfeucht, A. and Rozenberg, G., Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoretical Computer Science. v7. 169-183.

[11]

M. Hajiaghayi, K. Jain, L. Lau, I. Mandoiu, A.Russell, V. Vazirani, Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping, in: Proceedings of the 6th International Conference on Computational Science (ICCS), 2006.

[12]

R. Hassin, D. Segev, The set cover with pairs problem, in: Proceedings of the 25th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2005.

Digital Library

[13]

Hochbaum, D., Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing. v11 i3. 555-556.

[14]

Y.-T. Huang, K.-M. Chao, T. Chen, An approximation algorithm for haplotype inference by maximum parsimony, in: Proceedings of the 20'th ACM Symposium on Applied Computing (SAC), 2005.

[15]

Johnson, D., Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences. v9. 256-278.

[16]

Lovász, L., On the ratio of optimal integeral and fractional solutions. Discrete Mathematics. v13. 383-390.

[17]

Néraud, J., Elementariness of a finite set of words is co-NP-complete. Theoretical Informatics and Applications. v24 i5. 459-470.

[18]

Papadimitriou, C. and Yannakakis, M., Optimization, approximation, and complexity classes. Journal of Computer and Systems Sciences. v43. 425-440.

[19]

Patthy, L., Exons---original building blocks of proteins?. BioEssays. v13 i4. 187-192.

[20]

R. Raz, S. Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, in: Proceedings of the 29th ACM Symposium on the Theory Of Computing (STOC), 1997.

Digital Library

[21]

Rozenberg, G. and Salomaa, A., The Mathematical Theory of L Systems. 1980. Academic Press, New York.

Cited By

Gershtein SMilo TNovgorodov SRazmadze KIves ZBonifati AEl Abbadi A(2022)Classifier Construction Under Budget ConstraintsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517863(1160-1174)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517863
Gershtein SMilo TMorami GNovgorodov SMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Minimization of Classifier Construction Cost for Search QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389755(1351-1365)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389755
Hirsch MRodríguez JMateos CZunino A(2017)A Two-Phase Energy-Aware Scheduling Approach for CPU-Intensive Jobs in Mobile GridsJournal of Grid Computing10.1007/s10723-016-9387-615:1(55-80)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10723-016-9387-6
Show More Cited By

Index Terms

The Minimum Substring Cover problem
1. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Randomness, geometry and discrete structures

Recommendations

Packing items into several bins facilitates approximating the separable assignment problem

( ( 1 - 1 e k ) β ) -approximation for k-SAP if the single bin problem admits a β-approximation. ( 1 - 1 e k ) -approximation for k-SAP if the single bin problem admits an FPTAS.For k 2 , our algorithm beats the upper bound of ( 1 - 1 e ) known for other ...
The Minimum Substring Cover Problem
Approximation and Online Algorithms
Abstract
In this paper we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem ...
Improved Approximation Algorithms for the Partial Vertex Cover Problem
APPROX '02: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization

The partial vertex cover problemis a generalization of the vertex cover problem: given an undirected graph G = ( V , E ) and an integer k , we wish to choose a minimum number of vertices such that at least k edges are covered. Just as for vertex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 206, Issue 11

November, 2008

118 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © © 2008.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 November 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gershtein SMilo TNovgorodov SRazmadze KIves ZBonifati AEl Abbadi A(2022)Classifier Construction Under Budget ConstraintsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517863(1160-1174)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517863
Gershtein SMilo TMorami GNovgorodov SMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Minimization of Classifier Construction Cost for Search QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389755(1351-1365)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389755
Hirsch MRodríguez JMateos CZunino A(2017)A Two-Phase Energy-Aware Scheduling Approach for CPU-Intensive Jobs in Mobile GridsJournal of Grid Computing10.1007/s10723-016-9387-615:1(55-80)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10723-016-9387-6
(2016)Battery-aware centralized schedulers for CPU-bound jobs in mobile GridsPervasive and Mobile Computing10.1016/j.pmcj.2015.08.00329:C(73-94)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.pmcj.2015.08.003
Lozano MRodriguez FGarcía-Martínez C(2015)A two-stage constructive method for the unweighted minimum string cover problemKnowledge-Based Systems10.1016/j.knosys.2015.01.00377:C(103-113)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.knosys.2015.01.003
(2015)Some algorithmic results for 2-sumset coversInformation Processing Letters10.1016/j.ipl.2014.07.008115:1(1-5)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.ipl.2014.07.008
Canzar SMarschall TRahmann SSchwiegelshohn C(2012)Solving the minimum string cover problemProceedings of the Meeting on Algorithm Engineering & Expermiments10.5555/2790265.2790273(75-83)Online publication date: 16-Jan-2012
https://dl.acm.org/doi/10.5555/2790265.2790273
He JSuel THersh WCallan JMaarek YSanderson M(2012)Optimizing positional index structures for versioned document collectionsProceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval10.1145/2348283.2348319(245-254)Online publication date: 12-Aug-2012
https://dl.acm.org/doi/10.1145/2348283.2348319

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents