Randomized algorithm for the sum selection problem

DOI10.1016/J.TCS.2007.02.027zbMATH Open1115.68170OpenAlexW1999057066MaRDI QIDQ884471FDOQ884471

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

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

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)

Cites Work

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

Cited In (10)

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

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)