Stochastic service systems, random interval graphs and search algorithms

DOI10.1002/RSA.20485MaRDI QIDQ2930056zbMATH OpenOpenAlexFDO

Authors Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger, Patrick Eschenfeldt, Ben Gross

Publication date 17 November 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.4113

zbMATH Keywords

M/M/1stochastic service systems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Queues and service in operations research (90B22)

Abstract: We consider several stochastic service systems, and study the asymptotic behavior of the moments of various quantities that have application to models for random interval graphs and algorithms for searching for an idle server or empty waiting station. In two cases the moments turn out to involve Lambert series for the generating functions for the sums of powers of divisors of positive integers. For these cases we are able to obtain complete asymptotic expansions for the moments of the quantities in question.

Recommendations

• scientific article; zbMATH DE number 4001840
• scientific article; zbMATH DE number 3930084
• scientific article; zbMATH DE number 3174016
• scientific article; zbMATH DE number 879776
• The Complexity of Interval Routing on Random Graphs
• The complexity of interval routing on random graphs
• Stochastic bigraphs
• Lagrange dual bound computation for stochastic service network design
• The stochastic single resource service-provision problem

Cites work

• A new proof of the Voronoï summation formula
• A Proof for the Queuing Formula: L = λW
• A Stochastic Model of Fragmentation in Dynamic Storage Allocation
• An evolution of interval graphs
• scientific article; zbMATH DE number 3174016 (Why is no real title available?)
• scientific article; zbMATH DE number 3174848 (Why is no real title available?)
• scientific article; zbMATH DE number 3851501 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3755546 (Why is no real title available?)
• scientific article; zbMATH DE number 194092 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• On a property of the variance of the waiting time of a queue
• On the connectivity of a random interval graph
• Random interval graphs
• Random interval graphs
• The M/M/\(\infty\) service system with ranked servers in heavy traffic. With a preface by Franz Ferschl
• The Random Walk Between a Reflecting and an Absorbing Barrier

This page was built for publication: Stochastic service systems, random interval graphs and search algorithms

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