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

DOI10.1007/S10878-013-9622-ZzbMATH Open1320.90069OpenAlexW2095463189MaRDI QIDQ2344005FDOQ2344005

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

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

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)

Cites Work

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

Cited In (1)

• Recognition of overlap graphs

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)