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

DOI10.1007/s10878-013-9622-zzbMath1320.90069OpenAlexW2095463189MaRDI QIDQ2344005

Theodoros P. Gevezes, Leonidas S. 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

heuristicsdata compressioncombinatorial optimizationGRASPpath relinkingDNA sequencing

Mathematics Subject Classification ID

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

Related Items (1)

Recognition of overlap graphs

Uses Software

• GRASP
• Scatter Search
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The greedy algorithm for shortest superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• Shortest common superstrings and scheduling with coordinated starting times
• On finding minimal length superstrings
• Greedy algorithms for the shortest common superstring that are asymptotically optimal
• A hybrid heuristic for the \(p\)-median problem
• Proof verification and the hardness of approximation problems
• Integer Programming Formulation of Traveling Salesman Problems
• Why Greed Works for Shortest Common Superstring Problem
• Data compression via textual substitution
• Information compression by factorising common strings
• Linear approximation of shortest superstrings
• Rotations of Periodic Strings and Short Superstrings
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Parallel and sequential approximation of shortest superstrings
• Improved length bounds for the shortest superstring problem
• The macro model for data compression (Extended Abstract)

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