Search

We present an approximation algorithm for the Prize-collecting Ordered Traveling Salesman Problem (PCOTSP), which simultaneously generalizes the Prize-collecting TSP and the Ordered TSP. The Prize-collecting TSP is well-studied and has a long history, with the current best approximation factor slightly below $1.6$, shown by Blauth, Klein and N\"agele [IPCO 2024]. The best approximation ratio for Ordered TSP is $\frac{3}{2}+\frac{1}{e}$, presented by B\"{o}hm, Friggstad, M\"{o}mke, Spoerhase [SODA 2025] and Armbruster, Mnich, N\"{a}gele [Approx 2024]. The former also present a factor 2.2131 approximation algorithm for Multi-Path-TSP. By carefully tuning the techniques of the latest results on the aforementioned problems and leveraging the unique properties of our problem, we present a 2.097-approximation algorithm for PCOTSP. A key idea in our result is to first sample a set of trees, and then probabilistically pick up some vertices, while using the pruning ideas of Blauth, Klein, N\"{a}gele [IPCO 2024] on other vertices to get cheaper parity correction; the sampling probability and the penalty paid by the LP playing a crucial part in both cases. A straightforward adaptation of the aforementioned pruning ideas would only give minuscule improvements over standard parity correction methods. Instead, we use the specific characteristics of our problem together with properties gained from running a simple combinatorial algorithm to bring the approximation factor below 2.1. Our techniques extend to Prize-collecting Multi-Path TSP, building on results from B\"{o}hm, Friggstad, M\"{o}mke, Spoerhase [SODA 2025], leading to a 2.41-approximation.

In a recent paper, Alimi & Koskas highlighted in $w$CDM models derived from general relativity (GR) (with Dark Energy Universe numerical simulation data), a cosmological invariance of the distribution of dark-matter (DM) halo shapes when expressed in terms of the nonlinear fluctuations of the cosmic matter field. This paper shows that this invariance persists when tested on numerical simulations performed with a different N-body solver, and that it is also robust to adding massive neutrinos to the cold DM component. However, this discovery raises crucial questions about the validity of this invariance in MG models. Thus, we examined whether the invariance observed by Alimi & Koskas remains robust in the case of Hu & Sawicki model using DUSTGRAIN-pathfinder numerical simulations. By comparing the results of advanced numerical simulations in these different theoretical frameworks, we found significant deviations from the invariance observed in the framework of $w$CDM models of GR. These deviations suggest that the gravitation's nature significantly influences the DM halos' shape. We then interpreted this departure from the GR models' invariance as a manifestation of the scalar-field screening effect corresponding to such $f(R)$-type theories. This one modifies the sphericization process of DM halos during their formation, precisely because the critical mass at which this scalar field becomes non-negligible is the mass at which the deviation appears. To this extent, the departure from cosmological invariance in DM halos' shape is a cosmological probe of the nature of gravity, and the mass scale at which it appears can be used to estimate the $f_{R0}$ parameter of such theories., Comment: 10 pages, 12 figures, accepted for publication in A&A

We focus on the complex relationship between the shape of dark matter halos and the cosmological models underlying their formation. We used three realistic cosmological models from the Dark Energy Universe Simulation suite. They have significantly distinct cosmological parameters ($\Omega_m$, $\sigma_8$, and $w$) but quasi-indistinguishable cosmic matter fields beyond the scale of DM halos. Firstly, we developed a robust method to measure the FoF halos shape, while avoiding numerical artifacts on shape measurements. These artifacts are generally induced by the presence of substructures (resolution-dependent) or by any spherical a priori in contradiction with the halos triaxiality. We obtain a marked dependence of the halos shape, both on their mass and on the cosmological model. However, when re-expressing the halos shape parameters in terms of the non-linear fluctuations of the cosmic matter field, the cosmological dependence disappears. This new fundamental cosmological invariance is a direct consequence of the matter field non-linear dynamics: as the universe evolves, the non-linear fluctuations of the cosmic field increase, driving the halos towards sphericity. The deviation from sphericity, measured by the prolaticity, triaxiality, and ellipticity of the dark matter halos, is therefore entirely encapsulated in the non-linear power spectrum. From this fundamental invariant relation, we can reconstruct with remarkable accuracy the non-linear variance of the cosmic matter field and, consequently, the non-linear power spectrum. We also re-find the $\sigma_8$ amplitude of the cosmological model. Our results highlight, not only the nuanced relationship between dark matter halo formation and the underlying cosmology, but also the potential of dark matter halo shape analysis as a powerful tool for probing the non-linear dynamics of the cosmic matter field., Comment: 22 pages, 27 figures; added reference, multiple text corrections (results unchanged), added Appendix B

Biometric recognition is the process of verifying or classifying human characteristics in images or videos. It is a complex task that requires machine learning algorithms, including convolutional neural networks (CNNs) and Siamese networks. Besides, there are several limitations to consider when using these algorithms for image verification and classification tasks. In fact, training may be computationally intensive, requiring specialized hardware and significant computational resources to train and deploy. Moreover, it necessitates a large amount of labeled data, which can be time-consuming and costly to obtain. The main advantage of the proposed TinySiamese compared to the standard Siamese is that it does not require the whole CNN for training. In fact, using a pre-trained CNN as a feature extractor and the TinySiamese to learn the extracted features gave almost the same performance and efficiency as the standard Siamese for biometric verification. In this way, the TinySiamese solves the problems of memory and computational time with a small number of layers which did not exceed 7. It can be run under low-power machines which possess a normal GPU and cannot allocate a large RAM space. Using TinySiamese with only 8 GO of memory, the matching time decreased by 76.78% on the B2F (Biometric images of Fingerprints and Faces), FVC2000, FVC2002 and FVC2004 while the training time for 10 epochs went down by approximately 93.14% on the B2F, FVC2002, THDD-part1 and CASIA-B datasets. The accuracy of the fingerprint, gait (NM-angle 180 degree) and face verification tasks was better than the accuracy of a standard Siamese by 0.87%, 20.24% and 3.85% respectively. TinySiamese achieved comparable accuracy with related works for the fingerprint and gait classification tasks.

As emphasized in a recent review article [Chem. Rev. 122, 14180 (2022)], organic solar cell (OSC) photoconversion efficiency has been rapidly evolving with results increasingly comparable to those of traditional inorganic solar cells. Historically, OSC performance improvement focused first on the morphology of P3HT:PC61BM solar cells then went through different stages to shift lately interest towards nonfullerene acceptors (NFAs) as a replacement of PC61BM acceptor (ACC) molecule. Here, we use density-functional theory (DFT) and time-dependent (TD) DFT to investigate four novel NFAs of A-D-A (acceptor-donor-acceptor) form derived from the recently synthesized IDIC-4Cl [Dyes and Pigments 166, 196 (2019)]. Our level of theory is carefully evaluted for IDIC-4Cl and then applied to the four novel NFAs in order to understand how chemical modifications lead to physical changes in cyclic voltammetry (CV) frontier molecular orbital (FMO) energies and absorption spectra in solution.Finally we design and apply a new type of Scharber plot for NFAs based upon some simple but we think reasonable assumptions. Unlike the original Scharber plots where a larger DON band gap favors a larger PCE, our modified Scharber plot reflects the fact that a smaller ACC band gap may favor PCE by filling in gaps in the DON acceptor spectrum. We predict that only the candidate molecule with the least good acceptor A, with the highest frontier molecular orbital energies, and one of the larger CV lowest unoccupied molecular orbital (LUMO) highest unoccupied molecular orbital (HOMO) gaps, will yield a PM6:ACC PCE exceeding that of the parent IDIC-4Cl ACC. This candidate also shows the largest oscillator strength for the primary 1 (HOMO,LUMO) charge-transfer transition and the largest degree of delocalization of charge transfer of any of the ACC molecules investigated here.