Search for: All records

In optimal experimental design, the objective is to select a limited set of experiments that maximizes information about unknown model parameters based on factor levels. This work addresses the generalized D-optimal design problem, allowing for nonlinear relationships in factor levels. We develop scalable algorithms suitable for cases where the number of candidate experiments grows exponentially with the factor dimension, focusing on both first- and second-order models under design constraints. Particularly, our approach integrates convex relaxation with pricing-based local search techniques, which can provide upper bounds and performance guarantees. Unlike traditional local search methods, such as the ``Fedorov exchange" and its variants, our method effectively accommodates arbitrary side constraints in the design space. Furthermore, it yields both a feasible solution and an upper bound on the optimal value derived from the convex relaxation. Numerical results highlight the efficiency and scalability of our algorithms, demonstrating superior performance compared to the state-of-the-art commercial software, \texttt{JMP}. 

The multiple traveling salesman problem (mTSP) is an important variant of metric TSP where a set of k salespeople together visit a set of n cities while minimizing the total cost of the k routes under a given cost metric. The mTSP problem has applications to many real-life problems such as vehicle routing. Rothkopf [14] introduced another variant of TSP called many-visits TSP (MV-TSP) where a request r(v) is given for each city v and a single salesperson needs to visit each city r(v) times and return to his starting point. We note that in MV-TSP the cost of loops is positive, so a TSP solution cannot be trivially extended (without an increase in cost) to a MV-TSP solution by consecutively visiting each vertex to satisfy the visit requirements. A combination of mTSP and MV-TSP, called many-visits multiple TSP (MV-mTSP) was studied by Berczi, Mnich, and Vincze [3] where the authors give approximation algorithms for various variants of MV-mTSP. In this work, we show a simple linear programming (LP) based reduction that converts a mTSP LP-based algorithm to an LP-based algorithm for MV-mTSP with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the MV-mTSP. Our reduction shows that the addition of visit requests r(v) to mTSP does not make the problem harder to approximate even when r(v) is exponential in the number of vertices. To apply our reduction, we either use existing LP-based algorithms for mTSP variants or show that several existing combinatorial algorithms for mTSP variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms while achieving improved guarantees. 

We present the analysis of the luminous Type II Supernova (SN) 2021tsz, which exploded in a low-luminosity galaxy. It reached a peak magnitude of −18.88 ± 0.13 mag in therband and exhibited an initial rapid decline of 4.05 ± 0.14 mag (100 d)⁻¹from peak luminosity till ∼30 d. The photospheric phase is short, with the SN displaying bluer colours and a weak Hαabsorption component–features consistent with other luminous, short-photospheric phase Type II SNe. A distinct transition from the photospheric to the radioactive tail phase in theVband–as is common in hydrogen-rich Type II SNe–is not visible in SN 2021tsz, although a modest ∼1 mag drop is apparent in the redder filters. Hydrodynamic modelling suggests the luminosity is powered by ejecta-circumstellar material (CSM) interaction during the early phases (< 30 days). Interaction with 0.6 M_⊙of dense CSM extending to 3100 R_⊙reproduces the observed luminosity, with an explosion energy of 1.3 × 10⁵¹erg. The modelling indicates a pre-SN mass of 9 M_⊙, which includes a hydrogen envelope of 4 M_⊙, and a radius of ∼1000 R_⊙. Spectral energy distribution analysis and strong-line diagnostics revealed that the host galaxy of SN 2021tsz is a low-metallicity, dwarf galaxy. The low-metallicity environment and the derived high mass loss from the hydrodynamical modelling strongly support a binary progenitor system for SN 2021tsz. 

Abstract Model-observation comparisons of type-I X-ray bursts (XRBs) can reveal the properties of accreting neutron star systems, including the neutron star compactness. XRBs are powered by nuclear burning, and a handful of reactions have been shown to impact the model results. Reactions in the NiCu cycles, featuring a competition between⁵⁹Cu(p,γ)⁶⁰Zn and⁵⁹Cu(p,α)⁵⁶Ni, have been shown to be among the most important reactions as they are a critical checkpoint inrp-process flow and significantly impact the light curves and burst ashes. We report a direct measurement of⁵⁹Cu(p,α)⁵⁶Ni, bringing stringent constraints on this reaction rate. New results rule out a strong NiCu cycle in XRBs, with a negligible degree of recycling, ≤5% up to 1.5 GK. The new reaction rate, when varied within new uncertainty limits, shows no impact on one-zone XRB model light curves tailored for clocked-bursterGS1826–24, hence removing an important nuclear physics uncertainty in the model-observation comparison. 

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i in A has a valuation v_ij ≥ 0 for each item j in G. In addition, every agent i has a non-negative weight w_i such that the weights collectively sum up to 1. The goal is to find an assignment of items to players that maximizes the weighted geometric mean of the valuation received by the players. When all the weights are equal, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present an approximation algorithm whose approximation depends on the KL-divergence between the weight distribution and the uniform distribution. We generalize the convex programming relaxations for the symmetric variant of Nash Social Welfare presented in [CDG+17, AGSS17] to two different mathematical programs. The first program is convex and is necessary for computational efficiency, while the second program is a non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation. 

We consider the Max-3-Section problem, where we are given an undirected graph G = (V, E) equipped with non-negative edge weights w : E → R+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result. 

We present a comprehensive photometric and spectroscopic study of the Type IIP supernova (SN) 2018is. TheVband luminosity and the expansion velocity at 50 days post-explosion are −15.1 ± 0.2 mag (corrected for A_V= 1.34 mag) and 1400 km s⁻¹, classifying it as a low-luminosity SN II. The recombination phase in theVband is shorter, lasting around 110 days, and exhibits a steeper decline (1.0 mag per 100 days) compared to most other low-luminosity SNe II. Additionally, the optical and near-infrared spectra display hydrogen emission lines that are strikingly narrow, even for this class. The Fe IIand Sc IIline velocities are at the lower end of the typical range for low-luminosity SNe II. Semi-analytical modelling of the bolometric light curve suggests an ejecta mass of ∼8 M_⊙, corresponding to a pre-supernova mass of ∼9.5 M_⊙, and an explosion energy of ∼0.40 × 10⁵¹erg. Hydrodynamical modelling further indicates that the progenitor had a zero-age main sequence mass of 9 M_⊙, coupled with a low explosion energy of 0.19 × 10⁵¹erg. The nebular spectrum reveals weak [O I]λλ6300,6364 lines, consistent with a moderate-mass progenitor, while features typical of Fe core-collapse events, such as He I, [C I], and Fe I, are indiscernible. However, the redder colours and low ratio of Ni to Fe abundance do not support an electron-capture scenario either. As a low-luminosity SN II with an atypically steep decline during the photospheric phase and remarkably narrow emission lines, SN 2018is contributes to the diversity observed within this population.