Additive Bounding, Worst-Case Analysis, and the Breakpoint Median Problem

DOI10.1137/S1052623401384849MaRDI QIDQ4785892zbMATH OpenOpenAlexFDO

Authors Alberto Caprara

Publication date 5 January 2003

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s1052623401384849

zbMATH Keywords

additive boundingapproximation algorithmbreakpoint median problemlinear programmingperfect matchingtraveling salesman problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximation algorithms for the median problem in the breakpoint model
• scientific article; zbMATH DE number 1615284
• A lower bound for the breakpoint phylogeny problem
• A further improved approximation algorithm for breakpoint graph decomposition
• scientific article; zbMATH DE number 1088277

Cited in

(2)

• Median approximations for genomes modeled as matrices
• Matheuristics: survey and synthesis

This page was built for publication: Additive Bounding, Worst-Case Analysis, and the Breakpoint Median Problem

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