IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v29y2015i4d10.1007_s10878-013-9622-z.html
   My bibliography  Save this article

A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

Author

Listed:
  • Theodoros Gevezes

    (Aristotle University of Thessaloniki)

  • Leonidas Pitsoulis

    (Aristotle University of Thessaloniki)

Abstract

The shortest superstring problem (SSP) is an $$NP$$ NP -hard combinatorial optimization problem which has attracted the interest of many researchers, due to its applications in computational molecular biology problems such as DNA sequencing, and in computer science problems such as string compression. In this paper a new heuristic algorithm for solving large scale instances of the SSP is presented, which outperforms the natural greedy algorithm in the majority of the tested instances. The proposed method is able to provide multiple near-optimum solutions and admits a natural parallel implementation. Extended computational experiments on a set of SSP instances with known optimum solutions indicate that the new method finds the optimum solution in most of the cases, and its average error relative to the optimum is close to zero.

Suggested Citation

  • Theodoros Gevezes & Leonidas Pitsoulis, 2015. "A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem," Journal of Combinatorial Optimization, Springer, vol. 29(4), pages 859-883, May.
    • Handle: RePEc:spr:jcomop:v:29:y:2015:i:4:d:10.1007_s10878-013-9622-z
    DOI: 10.1007/s10878-013-9622-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-013-9622-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-013-9622-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Manuel Laguna & Rafael Marti, 1999. "GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 44-52, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sudip Kumar De & Avishek Banerjee & Koushik Majumder & Samiran Chattopadhyay, 2022. "Minimizing the Energy Consumption of WSN Using Noble SMOWA-GA Algorithm," International Journal of Applied Metaheuristic Computing (IJAMC), IGI Global, vol. 13(1), pages 1-22, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fatma-Zohra Baatout & Mhand Hifi, 2023. "A two-phase hybrid evolutionary algorithm for solving the bi-objective scheduling multiprocessor tasks on two dedicated processors," Journal of Heuristics, Springer, vol. 29(2), pages 229-267, June.
    2. Rafael Martí & Abraham Duarte & Manuel Laguna, 2009. "Advanced Scatter Search for the Max-Cut Problem," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 26-38, February.
    3. Napoletano, Antonio & Martínez-Gavara, Anna & Festa, Paola & Pastore, Tommaso & Martí, Rafael, 2019. "Heuristics for the Constrained Incremental Graph Drawing Problem," European Journal of Operational Research, Elsevier, vol. 274(2), pages 710-729.
    4. Nathan Sudermann‐Merx & Steffen Rebennack & Christian Timpe, 2021. "Crossing Minimal Edge‐Constrained Layout Planning using Benders Decomposition," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3429-3447, October.
    5. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    6. Fred Glover & Vicente Campos & Rafael Martí, 2021. "Tabu search tutorial. A Graph Drawing Application," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 319-350, July.
    7. Bierwirth, C. & Kuhpfahl, J., 2017. "Extended GRASP for the job shop scheduling problem with total weighted tardiness objective," European Journal of Operational Research, Elsevier, vol. 261(3), pages 835-848.
    8. Kyriakakis, Nikolaos A. & Marinaki, Magdalene & Matsatsinis, Nikolaos & Marinakis, Yannis, 2022. "A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning," European Journal of Operational Research, Elsevier, vol. 300(3), pages 992-1004.
    9. Ramón Alvarez-Valdes & Rafael Martí & Jose M. Tamarit & Antonio Parajón, 2007. "GRASP and Path Relinking for the Two-Dimensional Two-Stage Cutting-Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 261-272, May.
    10. Mauricio Resende & Renato Werneck, 2007. "A fast swap-based local search procedure for location problems," Annals of Operations Research, Springer, vol. 150(1), pages 205-230, March.
    11. Fred Glover & Vicente Campos & Rafael Martí, 2021. "Rejoinder on: Tabu search tutorial. A Graph Drawing Application," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 363-371, July.
    12. Markus Frey & Ferdinand Kiermaier & Rainer Kolisch, 2017. "Optimizing Inbound Baggage Handling at Airports," Transportation Science, INFORMS, vol. 51(4), pages 1210-1225, November.
    13. Palubeckis, Gintaras & Tomkevičius, Arūnas & Ostreika, Armantas, 2019. "Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization," Applied Mathematics and Computation, Elsevier, vol. 348(C), pages 84-101.
    14. Michel Gendreau & Jean-Yves Potvin, 2005. "Metaheuristics in Combinatorial Optimization," Annals of Operations Research, Springer, vol. 140(1), pages 189-213, November.
    15. F. Rodriguez & C. Blum & C. García-Martínez & M. Lozano, 2012. "GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times," Annals of Operations Research, Springer, vol. 201(1), pages 383-401, December.
    16. Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.
    17. Maria Albareda-Sambola & Elena Fernández & Francisco Saldanha-da-Gama, 2017. "Heuristic Solutions to the Facility Location Problem with General Bernoulli Demands," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 737-753, November.
    18. Thekra Al-douri & Mhand Hifi & Vassilis Zissimopoulos, 2021. "An iterative algorithm for the Max-Min knapsack problem with multiple scenarios," Operational Research, Springer, vol. 21(2), pages 1355-1392, June.
    19. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    20. Renata M. Aiex & Mauricio G. C. Resende & Panos M. Pardalos & Gerardo Toraldo, 2005. "GRASP with Path Relinking for Three-Index Assignment," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 224-247, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:29:y:2015:i:4:d:10.1007_s10878-013-9622-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.