Randomized algorithm for the sum selection problem

DOI10.1016/j.tcs.2007.02.027zbMath1115.68170OpenAlexW1999057066MaRDI QIDQ884471

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

selection problemrandomized algorithmbioinformaticsrandom samplingmaximum sum problem\(k\) maximum sum segment problemmaximum sums problemorder-statistic treesum selection problem

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (4)

Two parallel algorithms for finding all minimal maximum subsequences ⋮ Optimal algorithms for the average-constrained maximum-sum segment problem ⋮ Efficient algorithms for the sum selection problem and \(k\) maximum sums problem ⋮ MINKOWSKI SUM SELECTION AND FINDING

Uses Software

• Find

Cites Work

• Unnamed Item
• Unnamed Item
• A note on a standard strategy for developing loop invariants and loops
• Randomized optimal algorithm for slope selection
• Time bounds for selection
• Applications of a strategy for designing divide-and-conquer algorithms
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Improved algorithms for the \(k\) maximum-sums problems
• Efficient algorithms for \(k\) maximum sums
• An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics
• APPLICATION OF BROADCASTING WITH SELECTIVE REDUCTION TO THE MAXIMAL SUM SUBSEGMENT PROBLEM
• Expected time bounds for selection
• Probability and Computing
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION

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