iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S00453-010-9419-8
Reoptimization of the Shortest Common Superstring Problem | Algorithmica Skip to main content
Springer Nature Link
Log in

Reoptimization of the Shortest Common Superstring Problem

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A reoptimization problem describes the following scenario: given an instance of an optimization problem together with an optimal solution for it, we want to find a good solution for a locally modified instance.

In this paper, we deal with reoptimization variants of the shortest common superstring problem (SCS) where the local modifications consist of adding or removing a single string. We show the NP-hardness of these reoptimization problems and design several approximation algorithms for them. First, we use a technique of iteratively using any SCS algorithm to design an approximation algorithm for the reoptimization variant of adding a string whose approximation ratio is arbitrarily close to 8/5 and another algorithm for deleting a string with a ratio tending to 13/7. Both algorithms significantly improve over the best currently known SCS approximation ratio of 2.5. Additionally, this iteration technique can be used to design an improved SCS approximation algorithm (without reoptimization) if the input instance contains a long string, which might be of independent interest. However, these iterative algorithms are relatively slow. Thus, we present another, faster approximation algorithm for inserting a string which is based on cutting the given optimal solution and achieves an approximation ratio of 11/6. Moreover, we give some lower bounds on the approximation ratio which can be achieved by algorithms that use such cutting strategies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks 42(3), 154–159 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  2. Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0-1 knapsack problem. Technical Report 267, University of Brescia (2006)

  3. Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.T.: Reoptimization of minimum and maximum traveling salesman’s tours. In: Arge, L., Freivalds, R.V. (eds.) Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science, vol. 4059, pp. 196–207. Springer, Berlin (2006)

    Google Scholar 

  4. Bilò, D., Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Widmayer, P., Zych, A.: Reoptimization of Steiner trees. In: Gudmundsson, J. (ed.) Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008). Lecture Notes in Computer Science, vol. 5124, pp. 258–269. Springer, Berlin (2008)

    Google Scholar 

  5. Bilò, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Bampis, E., Skutella, M. (eds.) Proc. of the 6th International Workshop on Approximation and Online Algorithms (WAOA 2008). Lecture Notes in Computer Science, vol. 5426, pp. 201–213. Springer, Berlin (2009)

    Chapter  Google Scholar 

  6. Böckenhauer, H.-J., Bongartz, D.: Algorithmic Aspects of Bioinformatics. Natural Computing Series, Springer, Berlin (2007)

    MATH  Google Scholar 

  7. Böckenhauer, H.-J., Komm, D.: Reoptimization of the metric deadline TSP. In: Ochmanski, E., Tyszkiewicz, J. (eds.) Proc. of the 33th International Symposium on Mathematical Foundations of Computer Science (MFCS 2008). Lecture Notes in Computer Science, vol. 5162, pp. 156–167. Springer, Berlin (2008)

    Chapter  Google Scholar 

  8. Böckenhauer, H.-J., Forlizzi, L., Hromkovič, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances (extended abstract). In: Navarro, G., Bertossi, L.E., Kohayakawa, Y. (eds.) Proc. of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006). IFIP, vol. 209, pp. 251–270. Springer, New York (2006)

    Chapter  Google Scholar 

  9. Böckenhauer, H.-J., Hromkovič, J., Mömke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds.) Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008). Lecture Notes in Computer Science, vol. 4910, pp. 50–65. Springer, Berlin (2008)

    Google Scholar 

  10. Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Rossmanith, P.: Reoptimization of Steiner trees: Changing the terminal set. Theor. Comput. Sci. 410(36), 3428–3435 (2009)

    Article  MATH  Google Scholar 

  11. Escoffier, B., Milanič, M., Paschos, V.T.: Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Oper. Res. 4(2), 86–94 (2009)

    MathSciNet  Google Scholar 

  12. Gallant, J., Maier, D., Storer, J.A.: On finding minimal length superstrings. J. Comput. Syst. Sci. 20(1), 50–58 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kaplan, H., Shafrir, N.: The greedy algorithm for shortest superstrings. Inf. Process. Lett. 93(1), 13–17 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4), 602–626 (2005)

    Article  MathSciNet  Google Scholar 

  15. Schäffter, M.W.: Scheduling with forbidden sets. Discrete Appl. Math. 72(1–2), 155–166 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  16. Setubal, C., Meidanis, J.: Introduction to Computational Molecular Biology. Natural Computing Series, PWS Publishing Company, Boston (1997)

    Google Scholar 

  17. Sweedyk, Z.: A \(2\frac{1}{2}\)-approximation algorithm for shortest superstring. SIAM J. Comput. 29(3), 954–986 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  18. Tarhio, J., Ukkonen, E.: A greedy approximation algorithm for constructing shortest common superstrings. Theor. Comput. Sci. 57(1), 131–145 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  19. van Hoesel, S., Wagelmans, A.: On the complexity of postoptimality analysis of 0/1 programs. Discrete Appl. Math. 91(1–3), 251–263 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  20. Vassilevska, V.: Explicit inapproximability bounds for the shortest superstring problem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) Proc. of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005). Lecture Notes in Computer Science, vol. 3618, pp. 793–800. Springer, Berlin (2005)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of L’Aquila, L’Aquila, Italy

    Davide Bilò

  2. Department of Computer Science, ETH Zurich, Zurich, Switzerland

    Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke & Anna Zych

  3. Department of Computer Science, RWTH Aachen University, Aachen, Germany

    Sebastian Seibert

Authors
  1. Davide Bilò
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hans-Joachim Böckenhauer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dennis Komm
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Richard Královič
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tobias Mömke
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Sebastian Seibert
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Anna Zych
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dennis Komm.

Additional information

This work was partially supported by SNF grant 200021-121745/1 and SBF grant C 06.0108 as part of the COST 293 (GRAAL) project funded by the European Union. An extended abstract of this paper appeared at CPM 2009 [D. Bilò, H.-J. Böckenhauer, D. Komm, R. Královič, T. Mömke, S. Seibert, A. Zych, Reoptimization of the shortest common superstring problem. In: Proc. of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009). LNCS, vol. 5577, pp. 78–91. Springer, Berlin (2009) (extended abstract)].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bilò, D., Böckenhauer, HJ., Komm, D. et al. Reoptimization of the Shortest Common Superstring Problem. Algorithmica 61, 227–251 (2011). https://doi.org/10.1007/s00453-010-9419-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-010-9419-8

Keywords

Search

Navigation