Minimum common string partition problem: Hardness and approximations

DOI10.1007/978-3-540-30551-4_43MaRDI QIDQ5712138zbMATH OpenOpenAlexFDO

Authors Avraham Goldstein, Petr Kolman, Jie Zheng

Publication date 22 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b104582

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Minimum common string partition problem: hardness and approximations
• Minimum common string partition revisited
• Minimum common string partition revisited
• Exponential and polynomial time algorithms for the minimum common string partition problem
• The greedy algorithm for the minimum common string partition problem

Cited in

(32)

• The greedy algorithm for edit distance with moves
• ILP-based reduced variable neighborhood search for large-scale minimum common string partition
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• A comparative analysis of two matheuristics by means of merged local optima networks
• The complexity of string partitioning
• Solving the minimum common string partition problem with the help of ants
• An approximation algorithm for genome sorting by reversals to recover all adjacencies
• Solving the maximum duo-preservation string mapping problem with linear programming
• Minimum common string partition problem: hardness and approximations
• A 1.5-approximation algorithm for two-sided scaffold filling
• Mathematical programming strategies for solving the minimum common string partition problem
• The Complexity of String Partitioning
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies
• Quick greedy computation for minimum common string partitions
• Approximation and nonapproximability for the one-sided scaffold filling problem
• Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization
• On the Minimum Common Integer Partition Problem
• Minimum common string partition revisited
• Better Approximations for the Minimum Common Integer Partition Problem
• Minimum common string partition revisited
• Notes on the \(\frac{6}{5}\)-approximation algorithm for one-sided scaffold filling
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Exponential and polynomial time algorithms for the minimum common string partition problem
• On the exact block cover problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Computational performance evaluation of two integer linear programming models for the minimum common string partition problem
• Signed rearrangement distances considering repeated genes, intergenic regions, and indels
• On the role of metaheuristic optimization in bioinformatics
• Minimum common string partition: on solving large‐scale problem instances
• Sorting by multi-cut rearrangements
• Approximating reversal distance for strings with bounded number of duplicates

This page was built for publication: Minimum common string partition problem: Hardness and approximations

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