More Like this

1. When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1?

   https://doi.org/10.1287/opre.2022.0038  

   Scully, Ziv; van_Kreveld, Lucas (February 2024, Operations Research)

   We consider scheduling in the M/G/1 queue with unknown job sizes. It is known that the Gittins policy minimizes mean response time in this setting. However, the behavior of the tail of response time under Gittins is poorly understood, even in the large-response-time limit. Characterizing Gittins’s asymptotic tail behavior is important because if Gittins has optimal tail asymptotics, then it simultaneously provides optimal mean response time and good tail performance. In this work, we give the first comprehensive account of Gittins’s asymptotic tail behavior. For heavy-tailed job sizes, we find that Gittins always has asymptotically optimal tail. The story for light-tailed job sizes is less clear-cut: Gittins’s tail can be optimal, pessimal, or in between. To remedy this, we show that a modification of Gittins avoids pessimal tail behavior, while achieving near-optimal mean response time. 

   more » « less
2. The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions

   https://doi.org/10.1145/3428328  

   Scully, Ziv; Grosof, Isaac; Harchol-Balter, Mor (November 2020, Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   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
3. Optimistic Gittins Indices

   https://doi.org/10.1287/opre.2021.2207  

   Farias, Vivek F; Gutin, Eli (November 2022, Operations Research)

   We propose a tightening sequence of optimistic approximations to the Gittins index in “Optimistic Gittins Indices.” We show that the use of these approximations in concert with the use of an increasing discount factor appears to offer a compelling alternative to state-of-the-art index schemes proposed for the Bayesian multiarmed bandit problem. We prove that the use of these optimistic indices constitutes a regret optimal algorithm. Perhaps more interestingly, the use of even the loosest of these approximations appears to offer substantial performance improvements over state-of-the-art alternatives while incurring little to no additional computational overhead relative to the simplest of these alternatives. 

   more » « less
4. A new fossil Acmopyle with accessory transfusion tissue and potential reproductive buds: Direct evidence for ever‐wet rainforests in Eocene Patagonia

   https://doi.org/10.1002/ajb2.16221  

   Andruchow‐Colombo, Ana; Rossetto‐Harris, Gabriella; Brodribb, Timothy J; Gandolfo, María A; Wilf, Peter (August 2023, American Journal of Botany)

   Abstract PremiseAcmopyle(Podocarpaceae) comprises two extant species from Oceania that are physiologically restricted to ever‐wet rainforests, a confirmed fossil record based on leaf adpressions and cuticles in Australia since the Paleocene, and a few uncertain reports from New Zealand, Antarctica, and South America. We investigated fossil specimens withAcmopyleaffinities from the early Eocene Laguna del Hunco site in Patagonia, Argentina. MethodsWe studied 42 adpression leafy‐shoot fossils and included them in a total evidence phylogenetic analysis. ResultsAcmopyle grayaesp. nov. is based on heterophyllous leafy shoots with three distinct leaf types. Among these, bilaterally flattened leaves uniquely preserve subparallel, linear features that we interpret as accessory transfusion tissue (ATT, an extra‐venous water‐conducting tissue). Some apical morphologies ofA. grayaeshoots are compatible with the early stages of ovuliferous cone development. Our phylogenetic analysis recovers the new species in a polytomy with the two extantAcmopylespecies. We report several types of insect‐herbivory damage. We also transferAcmopyle engelhardtifrom the middle Eocene Río Pichileufú flora toDacrycarpus engelhardticomb. nov. ConclusionsWe confirm the biogeographically significant presence of the endangered West Pacific genusAcmopylein Eocene Patagonia.Acmopyleis one of the most drought‐intolerant genera in Podocarpaceae, possibly due to the high collapse risk of the ATT, and thus the new fossil species provides physiological evidence for the presence of an ever‐wet rainforest environment at Laguna del Hunco during the Early Eocene Climatic Optimum. 

   more » « less
5. Eco‐phylogenetic study of Trebouxia in southern Africa reveals interbiome connectivity and potential endemism in a green algal lichen photobiont

   https://doi.org/10.1002/ajb2.16441  

   Medeiros, Ian D; Ibáñez, Alicia; Arnold, A Elizabeth; Hedderson, Terry A; Miadlikowska, Jolanta; Flakus, Adam; Carbone, Ignazio; LaGreca, Scott; Magain, Nicolas; Mazur, Edyta; et al (December 2024, American Journal of Botany)

   Abstract PremiseSouthern Africa is a biodiversity hotspot rich in endemic plants and lichen‐forming fungi. However, species‐level data about lichen photobionts in this region are minimal. We focused onTrebouxia(Chlorophyta), the most common lichen photobiont, to understand how southern African species fit into the global biodiversity of this genus and are distributed across biomes and mycobiont partners. MethodsWe sequencedTrebouxianuclear ribosomal ITS andrbcLof 139 lichen thalli from diverse biomes in South Africa and Namibia. GlobalTrebouxiaphylogenies incorporating these new data were inferred with a maximum likelihood approach.Trebouxiabiodiversity, biogeography, and mycobiont–photobiont associations were assessed in phylogenetic and ecological network frameworks. ResultsAn estimated 43 putativeTrebouxiaspecies were found across the region, including seven potentially endemic species. Only five clades represent formally described species:T. arboricolas.l. (A13),T. cf.cretacea(A01),T. incrustata(A06),T. lynniae(A39), andT. maresiae(A46). Potential endemic species were not significantly associated with the Greater Cape Floristic Region or desert.Trebouxiaspecies occurred frequently across multiple biomes. Annual precipitation, but not precipitation seasonality, was significant in explaining variation inTrebouxiacommunities. Consistent with other studies of lichen photobionts, theTrebouxia–mycobiont network had an anti‐nested structure. ConclusionsDepending on the metric used, ca. 20–30% of globalTrebouxiabiodiversity occurs in southern Africa, including many species yet to be described. With a classification scheme forTrebouxianow well established, tree‐based approaches are preferable over “barcode gap” methods for delimiting new species. 

   more » « less