Two Probabilistic Results on Merging

DOI10.1137/0222019MaRDI QIDQ4032936zbMATH OpenOpenAlexFDO

Authors Sampath Kannan, Miklos Santha, W. Fernandez de la Vega

Publication date 17 May 1993

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

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

zbMATH Keywords

randomized algorithminformation theorylower boundmerging

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 4145014
• Merging with a set of probability measures: A characterization
• Probabilistic merging operators
• On mergers of distributions and distributions with exponential tails
• Reaching the bound in the \((2,n)\) merging problem
• Merging by Decomposition Revisited
• Fusions of a probability distribution
• Merging asymptotic expansions for semistable random variables

Cited in

(9)

• Optimal expected-time algorithms for merging
• Merging of weakly regnerative processes
• On mergers of distributions and distributions with exponential tails
• From time to space: fast algorithms that yield small and fast data structures
• A model of random merging of segments
• On the optimality of tape merge of two lists with similar size
• Reaching the bound in the \((2,n)\) merging problem
• On the optimality of tape merge of two lists with similar size
• Merging with a set of probability measures: A characterization

This page was built for publication: Two Probabilistic Results on Merging

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