Randomized algorithm for the sum selection problem

DOI10.1016/J.TCS.2007.02.027MaRDI QIDQ884471zbMATH OpenOpenAlexFDO

Authors Tien-Ching Lin, Der-Tsai Lee

Publication date 6 June 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.02.027

zbMATH Keywords

randomized algorithmrandom samplingbioinformaticsselection problemmaximum sum problem\(k\) maximum sum segment problemmaximum sums problemorder-statistic treesum selection problem

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• Algorithms and Computation
• Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem
• Efficient algorithms for the sum selection problem and \(k\) maximum sums problem
• Optimal randomized algorithm for the density selection problem
• Ranking \(k\) maximum sums

Cites work

• scientific article; zbMATH DE number 1303586 (Why is no real title available?)
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION
• A note on a standard strategy for developing loop invariants and loops
• APPLICATION OF BROADCASTING WITH SELECTIVE REDUCTION TO THE MAXIMAL SUM SUBSEGMENT PROBLEM
• An optimal algorithm for maximum-sum segment and its application in bioinformatics (extended abstract)
• Applications of a strategy for designing divide-and-conquer algorithms
• Efficient algorithms for \(k\) maximum sums
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Expected time bounds for selection
• Improved algorithms for the \(k\) maximum-sums problems
• Probability and Computing
• Randomized optimal algorithm for slope selection
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Time bounds for selection

Cited in

(10)

• Optimal algorithms for the average-constrained maximum-sum segment problem
• Algorithms and Computation
• On the cost of algorithms for random selection
• Minkowski sum selection and finding
• Finding maximum sum segments in sequences with uncertainty
• Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem
• Optimal randomized algorithm for the density selection problem
• Finding maximum sum segments in sequences with uncertainty
• Two parallel algorithms for finding all minimal maximum subsequences
• Efficient algorithms for the sum selection problem and \(k\) maximum sums problem

Describes a project that uses

Uses Software

• Find

This page was built for publication: Randomized algorithm for the sum selection problem

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