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

DOI10.1007/S10878-013-9622-ZMaRDI QIDQ2344005zbMATH OpenOpenAlexFDO

Authors Theodoros P. Gevezes, Leonidas Pitsoulis

Publication date 11 May 2015

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-013-9622-z

zbMATH Keywords

heuristicscombinatorial optimizationdata compressionDNA sequencingpath relinkingGRASP

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Recommendations

• Approximating Shortest Superstrings
• Linear approximation of shortest superstrings
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• A \(2_3^2\) superstring approximation algorithm
• Greedy algorithms for the shortest common superstring that are asymtotically optimal

Cites work

• scientific article; zbMATH DE number 5074400 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 1420898 (Why is no real title available?)
• A greedy approximation algorithm for constructing shortest common superstrings
• A hybrid heuristic for the \(p\)-median problem
• Data compression via textual substitution
• Fundamentals of scatter search and path relinking
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
• GRASP: An annoted bibliography
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• Improved length bounds for the shortest superstring problem
• Information compression by factorising common strings
• Integer Programming Formulation of Traveling Salesman Problems
• Linear approximation of shortest superstrings
• On finding minimal length superstrings
• Parallel and sequential approximation of shortest superstrings
• Proof verification and the hardness of approximation problems
• Rotations of Periodic Strings and Short Superstrings
• Shortest common superstrings and scheduling with coordinated starting times
• The greedy algorithm for shortest superstrings
• The macro model for data compression (extended abstract)
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Why Greed Works for Shortest Common Superstring Problem
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring

Cited in

(3)

• Hybridizations of GRASP with path relinking for the far from most string problem
• A beam search for the shortest common supersequence problem guided by an approximate expected length calculation
• Recognition of overlap graphs

Describes a project that uses

Uses Software

• GRASP
• Scatter Search
• Tabu search

This page was built for publication: A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344005)