Speedy colorful subtrees

DC FieldValueLanguage
dc.contributor.authorWhite, W.T.J.
dc.contributor.authorBeyer, S.
dc.contributor.authorDührkop, K.
dc.contributor.authorChimani, M.
dc.contributor.authorBöcker, S.
dc.contributor.editorXu, D.
dc.contributor.editorDu, D.
dc.date.accessioned2021-12-23T16:32:30Z-
dc.date.available2021-12-23T16:32:30Z-
dc.date.issued2015
dc.identifier.isbn9783319213972
dc.identifier.issn03029743
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17387-
dc.descriptionConference of 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 ; Conference Date: 4 August 2015 Through 6 August 2015; Conference Code:158929
dc.description.abstractFragmentation trees are a technique for identifying molecular formulas and deriving some chemical properties of metabolites—small organic molecules—solely from mass spectral data. Computing these trees involves finding exact solutions to the NP-hard Maximum Colorful Subtree problem. Existing solvers struggle to solve the large instances involved fast enough to keep up with instrument throughput, and their performance remains a hindrance to adoption in practice. We attack this problem on two fronts: by combining fast and effective reduction algorithms with a strong integer linear program (ILP) formulation of the problem, we achieve overall speedups of 9.4 fold and 8.8 fold on two sets of real-world problems—without sacrificing optimality. Both approaches are, to our knowledge, the first of their kind for this problem. We also evaluate the strategy of solving global problem instances, instead of first subdividing them into many candidate instances as has been done in the past. Software (C++ source for our reduction program and our CPLEX/Gurobi driver program) available under LGPL at https://github.com/wtwhite/speedy_colorful_subtrees/. © Springer International Publishing Switzerland 2015.
dc.language.isoen
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectC++ (programming language)
dc.subjectCombinatorial mathematics
dc.subjectComputer software
dc.subjectForestry
dc.subjectInteger programming
dc.subjectTrees (mathematics), Exact solution
dc.subjectGlobal problems
dc.subjectInteger linear programs
dc.subjectMass spectral data
dc.subjectMolecular formula
dc.subjectReal-world problem
dc.subjectReduction algorithms
dc.subjectSmall organic molecules, Problem solving
dc.titleSpeedy colorful subtrees
dc.typeconference paper
dc.identifier.doi10.1007/978-3-319-21398-9_25
dc.identifier.scopus2-s2.0-84951207956
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84951207956&doi=10.1007%2f978-3-319-21398-9_25&partnerID=40&md5=2b6b1a2b512c884333b24cdceae418c2
dc.description.volume9198
dc.description.startpage310
dc.description.endpage322
dcterms.isPartOf.abbreviationLect. Notes Comput. Sci.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

5
Last Week
1
Last month
0
checked on May 23, 2024

Google ScholarTM

Check

Altmetric