We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu. In three passes, we are able to achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely—we give a (2/3 − ε)- approximation algorithm that uses 2/(3ε) passes for triangle-free graphs and 4/(3ε) passes for general graphs. Our algorithms are simple and combinatorial, use O(n log n) space, and (can be implemented to) have O(1) update time per edge. For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes: * Ahn and Guha give a (2/3−ε)-approximation algorithm that uses O(log(1/ε)/ε2) passes, whereas our (2/3 − ε)-approximation algorithm uses 4/(3ε) passes; * they also give a (1 − ε)-approximation algorithm that uses O(log n · poly(1/ε)) passes, where n is the number of vertices of the input graph; although our algorithm is (2/3−ε)-approximation, our number of passes do not depend on n. Earlier multi-pass algorithms either have a large constant inside big-O notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below 2/3.
more »
« less
Benchmark Angle-Differential Cross-Section Ratios for Excitation of the 4p5s Configuration in Krypton
Benchmark intensity ratio measurements of the energy loss lines of krypton for excitation of the 4p61S0→4p55s[3/2]2, 4p55s[3/2]1, 4p55s′[1/2]0, and 4p55s′[1/2]1 transitions are reported, these being the lowest electronic excitations for krypton. The importance of these ratios as stringent tests of theoretical electron scattering models for the noble gases is discussed, as well as the role of spin-exchange and direct processes regarding the angular dependence of these ratios. The experimental data are compared with predictions from fully-relativistic B-spline R-matrix (close-coupling) calculations.
more »
« less
- PAR ID:
- 10317810
- Date Published:
- Journal Name:
- Atoms
- Volume:
- 9
- Issue:
- 3
- ISSN:
- 2218-2004
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present new HCN and HCO+(J= 3–2) images of the nearby star-forming galaxies (SFGs) NGC 3351, NGC 3627, and NGC 4321. The observations, obtained with the Morita ALMA Compact Array, have a spatial resolution of ∼290–440 pc and resolve the innerRgal ≲ 0.6–1 kpc of the targets, as well as the southern bar end of NGC 3627. We complement this data set with publicly available images of lower excitation lines of HCN, HCO+, and CO and analyse the behaviour of a representative set of line ratios: HCN(3–2)/HCN(1–0), HCN(3–2)/HCO+(3–2), HCN(1–0)/CO(2–1), and HCN(3–2)/CO(2–1). Most of these ratios peak at the galaxy centres and decrease outwards. We compare the HCN and HCO+observations with a grid of one-phase, non-local thermodynamic equilibrium (non-LTE) radiative transfer models and find them compatible with models that predict subthermally excited and optically thick lines. We study the systematic variations of the line ratios across the targets as a function of the stellar surface density (Σstar), the intensity-weighted CO(2–1) (⟨ICO⟩), and the star formation rate surface density (ΣSFR). We find no apparent correlation with ΣSFR, but positive correlations with the other two parameters, which are stronger in the case of ⟨ICO⟩. The HCN/CO–⟨ICO⟩ relations show ≲0.3 dex galaxy-to-galaxy offsets, with HCN(3–2)/CO(2–1)–⟨ICO⟩ being ∼2 times steeper than HCN(1–0)/CO(2–1). In contrast, the HCN(3–2)/HCN(1–0)–⟨ICO⟩ relation exhibits a tighter alignment between galaxies. We conclude that the overall behaviour of the line ratios cannot be ascribed to variations in a single excitation parameter (e.g., density or temperature).more » « less
-
Abstract The CO(1–0) line has been carefully calibrated as a tracer of molecular gas mass. However, recent studies often favor higherJtransitions of the CO molecule, which are brighter and accessible for redshift ranges where CO(1–0) is not. These lines are not perfect analogs for CO(1–0), owing to their more stringent excitation conditions, and must be calibrated for use as molecular gas tracers. Here, we introduce the Arizona Molecular ISM Survey with the SMT, a multi-CO line survey ofz∼ 0 galaxies conducted to calibrate the CO(2–1) and CO(3–2) lines. The final survey includes CO(2–1) spectra of 176 galaxies and CO(3–2) spectra for a subset of 45. We supplement these with archival CO(1–0) spectra from xCOLD GASS for all sources and additional CO(1–0) observations with the Kitt Peak 12 m Telescope. Targets were selected to be representative of the 109M⊙≤M*≤ 1011.5M⊙galaxy population. Our project emphasized careful characterization of statistical and systematic uncertainties to enable studies of trends in CO line ratios. We show that optical and CO disk sizes are on average equal, for both the CO(1–0) and CO(2–1) line. We measure the distribution of CO line luminosity ratios, finding medians (16th–84th percentile) of 0.71 (0.51–0.96) for the CO(2–1)-to-CO(1–0) ratio, 0.39 (0.24–0.53) for the CO(3–2)-to-CO(1–0) ratio, and 0.53 (0.41–0.74) for the CO(3–2)-to-CO(2–1) ratio. A companion paper presents our study of CO(2–1)'s applicability as a molecular gas mass tracer and search for trends in the CO(2–1)-to-CO(1–0) ratio. Our catalog of CO line luminosities is publicly available.more » « less
-
Abstract We measure the low- J CO line ratios R 21 ≡ CO (2–1)/CO (1–0), R 32 ≡ CO (3–2)/CO (2–1), and R 31 ≡CO (3–2)/CO (1–0) using whole-disk CO maps of nearby galaxies. We draw CO (2–1) from PHANGS-ALMA, HERACLES, and follow-up IRAM surveys; CO (1–0) from COMING and the Nobeyama CO Atlas of Nearby Spiral Galaxies; and CO (3–2) from the James Clerk Maxwell Telescope Nearby Galaxy Legacy Survey and Atacama Pathfinder Experiment Large APEX Sub-Millimetre Array mapping. All together, this yields 76, 47, and 29 maps of R 21 , R 32 , and R 31 at 20″ ∼ 1.3 kpc resolution, covering 43, 34, and 20 galaxies. Disk galaxies with high stellar mass, log ( M ⋆ / M ⊙ ) = 10.25 – 11 , and star formation rate (SFR) = 1–5 M ⊙ yr −1 , dominate the sample. We find galaxy-integrated mean values and a 16%–84% range of R 21 = 0.65 (0.50–0.83), R 32 = 0.50 (0.23–0.59), and R 31 = 0.31 (0.20–0.42). We identify weak trends relating galaxy-integrated line ratios to properties expected to correlate with excitation, including SFR/ M ⋆ and SFR/ L CO . Within galaxies, we measure central enhancements with respect to the galaxy-averaged value of ∼ 0.18 − 0.14 + 0.09 dex for R 21 , 0.27 − 0.15 + 0.13 dex for R 31 , and 0.08 − 0.09 + 0.11 dex for R 32 . All three line ratios anticorrelate with galactocentric radius and positively correlate with the local SFR surface density and specific SFR, and we provide approximate fits to these relations. The observed ratios can be reasonably reproduced by models with low temperature, moderate opacity, and moderate densities, in good agreement with expectations for the cold interstellar medium. Because the line ratios are expected to anticorrelate with the CO (1–0)-to-H 2 conversion factor, α CO 1 − 0 , these results have general implications for the interpretation of CO emission from galaxies.more » « less
-
We unravel, for the very first time, the formation pathways of hydroxyacetone (CH 3 COCH 2 OH), methyl acetate (CH 3 COOCH 3 ), and 3-hydroxypropanal (HCOCH 2 CH 2 OH), as well as their enol tautomers within mixed ices of methanol (CH 3 OH) and acetaldehyde (CH 3 CHO) analogous to interstellar ices in the ISM exposed to ionizing radiation at ultralow temperatures of 5 K. Exploiting photoionization reflectron time-of-flight mass spectrometry (PI-ReToF-MS) and isotopically labeled ices, the reaction products were selectively photoionized allowing for isomer discrimination during the temperature-programmed desorption phase. Based on the distinct mass-to-charge ratios and ionization energies of the identified species, we reveal the formation pathways of hydroxyacetone (CH 3 COCH 2 OH), methyl acetate (CH 3 COOCH 3 ), and 3-hydroxypropanal (HCOCH 2 CH 2 OH) via radical–radical recombination reactions and of their enol tautomers (prop-1-ene-1,2-diol (CH 3 C(OH)CHOH), prop-2-ene-1,2-diol (CH 2 C(OH)CH 2 OH), 1-methoxyethen-1-ol (CH 3 OC(OH)CH 2 ) and prop-1-ene-1,3-diol (HOCH 2 CHCHOH)) via keto-enol tautomerization. To the best of our knowledge, 1-methoxyethen-1-ol (CH 3 OC(OH)CH 2 ) and prop-1-ene-1,3-diol (HOCH 2 CHCHOH) are experimentally identified for the first time. Our findings help to constrain the formation mechanism of hydroxyacetone and methyl acetate detected within star-forming regions and suggest that the hitherto astronomically unobserved isomer 3-hydroxypropanal and its enol tautomers represent promising candidates for future astronomical searches. These enol tautomers may contribute to the molecular synthesis of biologically relevant molecules in deep space due to their nucleophilic character and high reactivity.more » « less