Queen Daniela of Sardinia is asleep at the center of a round room at the top of the tower in her castle. She is accompanied by her faithful servant, Eva. Suddenly, they are awakened by cries of "Fire". The room is pitch black and they are disoriented. There is exactly one exit from the room somewhere along its boundary. They must find it as quickly as possible in order to save the life of the queen. It is known that with two people searching while moving at maximum speed 1 anywhere in the room, the room can be evacuated (i.e., with both people exiting) in 1 + (2 pi)/3 + sqrt{3} ~~ 4.8264 time units and this is optimal [Czyzowicz et al., DISC'14], assuming that the first person to find the exit can directly guide the other person to the exit using her voice. Somewhat surprisingly, in this paper we show that if the goal is to save the queen (possibly leaving Eva behind to die in the fire) there is a slightly better strategy. We prove that this "priority" version of evacuation can be solved in time at most 4.81854. Furthermore, we show that any strategy for saving themore »
Priority Evacuation from a Disk Using Mobile Robots
We introduce and study a new search-type problem with ( 𝑛+1 )-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining n robots (servants) are there to facilitate the queen’s objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than 2+4(\sqrt{2}-1)\pi/n for 𝑛≥4 servants. We also demonstrate that for 𝑛≥4 servants the queen cannot be evacuated in time less than 2 + \pi/n + 2/n^2.
- Award ID(s):
- 1813940
- Publication Date:
- NSF-PAR ID:
- 10092714
- Journal Name:
- Lecture notes in computer science
- Volume:
- 11085
- Page Range or eLocation-ID:
- 392 - 407
- ISSN:
- 0302-9743
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Multiple silicon solar cell technologies have surpassed or are close to surpassing 26% efficiency. Dielectric and amorphous silicon-based passivation layers combined with minimal metal/silicon contact areas were responsible for reducing the surface saturation current density below 3 fA cm −2 . At open-circuit, in passivated contact solar cells, the recombination is mainly from fundamental mechanisms (Auger and radiative) representing over 3/4 of the total recombination. At the maximum power point, the fundamental recombination fraction can drop to half, as surface and bulk Shockley–Read–Hall step in. As a result, to further increase the performance at the operating point, it is paramount to reduce the bulk dependence and secure proper surface passivation. Bulk recombination can be mitigated either by reducing bulk defect density or by reducing the wafer thickness. We demonstrate that for commercially-viable solar-grade silicon, thinner wafers and surface saturation current densities below 1 fA cm −2 , are required to significantly increase the practical efficiency limit of solar cells up to 0.6% absolute. For a high-quality n-type bulk silicon minority-carrier lifetime of 10 ms, the optimum wafer thickness range is 40–60 μm, a very different value from 110 μm previously calculated assuming undoped substrates and solely Auger and radiative recombination.more »
-
Abstract We report on the internal distribution of star formation efficiency in IRAS 08339+6517 (hereafter IRAS08), using ∼200 pc resolution CO(2 − 1) observations from NOEMA. The molecular gas depletion time changes by 2 orders-of-magnitude from disk-like values in the outer parts to less than 10 8 yr inside the half-light radius. This translates to a star formation efficiency per freefall time that also changes by 2 orders-of-magnitude, reaching 50%–100%, different than local spiral galaxies and the typical assumption of constant, low star formation efficiencies. Our target is a compact, massive disk galaxy that has a star formation rate 10× above the z = 0 main sequence; Toomre Q ≈ 0.5−0.7 and high gas velocity dispersion ( σ mol ≈ 25 km s −1 ). We find that IRAS08 is similar to other rotating, starburst galaxies from the literature in the resolved Σ SFR ∝ Σ mol N relation. By combining resolved literature studies we find that the distance from the main sequence is a strong indicator of the Kennicutt-Schmidt power-law slope, with slopes of N ≈ 1.6 for starbursts from 100 to 10 4 M ⊙ pc −2 . Our target is consistent with a scenario in which violentmore »
-
We consider evacuation of a group of n ≥ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitivemore »
-
Recently, over 200 molecules have been detected in the interstellar medium (ISM), with about one third being complex organic molecules (COMs), molecules containing six or more atoms. Over the last few decades, astrophysical laboratory experiments have shown that several COMs are formed via interaction of ionizing radiation within ices deposited on interstellar dust particles at 10 K (H 2 O, CH 3 OH, CO, CO 2 , CH 4 , NH 3 ). However, there is still a lack of understanding of the chemical complexity that is available through individual ice constituents. The present research investigates experimentally the synthesis of carbon, hydrogen, and oxygen bearing COMs from interstellar ice analogues containing carbon monoxide (CO) and methane (CH 4 ), ethane (C 2 H 6 ), ethylene (C 2 H 4 ), or acetylene (C 2 H 2 ) exposed to ionizing radiation. Utilizing online and in situ techniques, such as infrared spectroscopy and tunable photoionization reflectron time-of-flight mass spectrometry (PI-ReTOF-MS), specific isomers produced could be characterized. A total of 12 chemically different groups were detected corresponding to C 2 H n O ( n = 2, 4, 6), C 3 H n O ( n = 2, 4, 6, 8),more »
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Publisher's Version of Record
- https://doi.org/978-3-030-01325-7_32
