An official website of the United States government
Abstract Imagine, you enter a grocery store to buy food. How many people do you overlap with in this store? How much time do you overlap with each person in the store? In this paper, we answer these questions by studying the overlap times between customers in the infinite server queue. We compute in closed form the steady-state distribution of the overlap time between a pair of customers and the distribution of the number of customers that an arriving customer will overlap with. Finally, we define a residual process that counts the number of overlapping customers that overlap in the queue for at least$$\delta$$time units and compute its distribution.
more »
« less
Overlap times in the G/G/1 queue via Laplace transforms
Abstract In this paper, we analyze the steady-state maximum overlap time distribution in the G/G/1 queue. Our methodology exploits Laplace-Stieltjes transforms with a novel decomposition of the maximum overlap time. Explicit expressions are provided for the special cases of the M/G/1 and G/M/1 queues. We also study the steady-state distribution of the minimum overlap time of a customer with its two adjacent customers. We show a novel relationship between the minimum, maximum and the steady-state waiting time.
more »
« less
- Award ID(s):
- 2206286
- PAR ID:
- 10670341
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Queueing Systems
- Volume:
- 109
- Issue:
- 1
- ISSN:
- 0257-0130
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M/G/k, is a much more difficult problem. In this work we give the first general analysis of Gittins in the M/G/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M/G/k is at most its mean response time in the M/G/1 plus an $O(łog(1/(1 - ρ)))$ additive term, where ρ is the system load. A consequence of this result is that Gittins is heavy-traffic optimal in the M/G/k if the service requirement distribution S satisfies $$\mathbfE [S^2(łog S)^+] < \infty$$. This is the most general result on minimizing mean response time in the M/G/k to date. To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses.more » « less
-
null (Ed.)We consider the classical Minimum Balanced Cut problem: given a graph $$G$$, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first {\em deterministic, almost-linear time} approximation algorithm for this problem. Specifically, our algorithm, given an $$n$$-vertex $$m$$-edge graph $$G$$ and any parameter $$1\leq r\leq O(\log n)$$, computes a $$(\log m)^{r^2}$$-approximation for Minimum Balanced Cut on $$G$$, in time $$O\left ( m^{1+O(1/r)+o(1)}\cdot (\log m)^{O(r^2)}\right )$$. In particular, we obtain a $$(\log m)^{1/\epsilon}$$-approximation in time $$m^{1+O(1/\sqrt{\epsilon})}$$ for any constant $$\epsilon$$, and a $$(\log m)^{f(m)}$$-approximation in time $$m^{1+o(1)}$$, for any slowly growing function $$m$$. We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of $$G$$ that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an $$n$$-vertex graph is $$n^{o(1)}$$, thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in $$n$$ factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.more » « less
-
Finding from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems that attempt to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker for subgraph finding algorithms, which adopts a task-based computation model, and which also provides a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph finding algorithms that can be easily adapted from existing serial algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the idle time of CPU cores. To further improve load balancing on graphs where the workloads of individual tasks can be drastically different due to biased graph density distribution, we propose to prioritize the scheduling of those tasks that tend to be long running for processing and decomposition, plus a timeout mechanism for task decomposition to prevent long-running straggler tasks. The idea has been integrated into a novelty algorithm for maximum clique finding (MCF) that adopts a hybrid task decomposition strategy, which significantly improves the running time of MCF on dense and large graphs: The algorithm finds a maximum clique of size 1,109 on a large and dense WikiLinks graph dataset in 70 minutes. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation.more » « less
-
Abstract A total solar eclipse (TSE) traversed the continental US (CONUS) from west to east on 21 August 2017. Ionosondes located under the eclipse totality at Lusk (Wyoming) and Boulder (Colorado) observed the ionospheric G‐condition 20 min after totality. The Millstone Hill mid‐latitude incoherent scatter radar recorded an anomalous low altitude F2peak during the recovery phase of the eclipse, which can be attributed to an ionospheric G‐condition. We perform WACCM‐X simulations to investigate the physical processes that drive the ionospheric G‐condition. Specifically, we conducted a diagnostic analysis of the simulated atomic oxygen ion continuity equation to examine the source of the G‐condition. We defined two metrics describing the G‐condition: (a) the duration and (b) the maximum difference between and . Results indicate that E‐ and F1plasma density reduction closely follow the eclipse obscuration, whereas the F2‐layer density depletion lags the obscuration by 20 min. This delay increases with altitude and is caused by slower radiative recombination and transport processes in the diffusion‐dominated F2‐region. The delay creates a period during the eclipse recovery when the F1‐plasma density exceeds that of the F2‐peak, which manifests as the ionospheric G‐condition. The simulation study illuminates the space‐time behavior of the G‐condition indicating that this state can last for more than 50 min during the recovery phase of the eclipse.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1007/s11134-025-09938-1
