Search

In this paper, we present an experimental analysis of a fast heuristic algorithm that was designed to generate a fast, collision-free schedule for a set of robots on a path graph. The experiments confirm the algorithm's effectiveness in producing collision-free schedules as well as achieving the optimal solution when all tasks assigned to the robots are of equal duration. Additionally, we provide an integer linear programming formulation that guarantees an optimal solution for this scheduling problem on any input graph, at the expense of significantly greater computational resources. We prove the correctness of our integer linear program. By comparing the solutions of these two algorithms, including the time required by the schedule itself, and the run time of each algorithm, we show that the heuristic algorithm is optimal or near optimal in nearly all cases, with a far faster run time than the integer linear program.

We characterize mixed-level orthogonal arrays it terms of algebraic designs in a special multigraph. We prove a mixed-level analog of the Bierbrauer--Friedman (BF) bound for pure-level orthogonal arrays and show that arrays attaining it are radius-$1$ completely regular codes (equivalently, intriguing sets, equitable $2$-partitions, perfect $2$-colorings) in the corresponding multigraph. For the case when the numbers of levels are powers of the same prime number, we characterize, in terms of multispreads, additive mixed-level orthogonal arrays attaining the BF bound. For pure-level orthogonal arrays, we consider versions of the BF bound obtained by replacing the Hamming graph by its polynomial generalization and show that in some cases this gives a new bound. Keywords: orthogonal array, algebraic $t$-design, mixed orthogonal array, completely-regular code, equitable partition, intriguing set, Hamming graph, Bierbrauer-Friedman bound, additive code.

We consider various definitions of degrees of discrete functions and establish relations between the number of relevant (essential) variables and degrees of two- and three-valued functions. Keywords: relevant variable, sensitivity, degree of Boolean function.

We describe the Ruijsenaars' action-angle duality in classical many-body integrable systems through the spectral duality transformation relating the classical spin chains and Gaudin models. For this purpose, the Lax matrices of many-body systems are represented in the multi-pole (Gaudin-like) form by introducing a fictitious spectral parameter. This form of Lax matrices is also interpreted as classical-classical version of quantum-classical duality., Comment: 24 pages, reference added

A multidimensional nonnegative matrix is called polystochastic if the sum of its entries over each line is equal to $1$. The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. We prove that if $d$ is even, then the permanent of a $d$-dimensional polystochastic matrix of order $4$ is positive, and for odd $d$, we give a complete characterization of $d$-dimensional polystochastic matrices with zero permanent., Comment: 17 pages

A multidimensional nonnegative matrix is called polystochastic if the sum of entries in each line is equal to $1$. The set of all polystochastic matrices of order $n$ and dimension $d$ is a convex polytope $\Omega_n^d$. In the present paper, we compare known bounds on the number of vertices of the polytope $\Omega_n^d$ and prove that the number of vertices of $\Omega_3^d$ is doubly exponential on $d$., Comment: 8 pages, Section 2 is transferred from arXiv:2311.06905

Real-world recommender systems often need to balance multiple objectives when deciding which recommendations to present to users. These include behavioural signals (e.g. clicks, shares, dwell time), as well as broader objectives (e.g. diversity, fairness). Scalarisation methods are commonly used to handle this balancing task, where a weighted average of per-objective reward signals determines the final score used for ranking. Naturally, how these weights are computed exactly, is key to success for any online platform. We frame this as a decision-making task, where the scalarisation weights are actions taken to maximise an overall North Star reward (e.g. long-term user retention or growth). We extend existing policy learning methods to the continuous multivariate action domain, proposing to maximise a pessimistic lower bound on the North Star reward that the learnt policy will yield. Typical lower bounds based on normal approximations suffer from insufficient coverage, and we propose an efficient and effective policy-dependent correction for this. We provide guidance to design stochastic data collection policies, as well as highly sensitive reward signals. Empirical observations from simulations, offline and online experiments highlight the efficacy of our deployed approach., Comment: Accepted as a full paper in the 2024 ACM Conference on Recommender Systems (RecSys '24)

It is proved that 1) the indicator function of some onefold or multifold independent set in a regular graph is a perfect coloring if and only if the set attain the Delsarte--Hoffman bound; 2) each transversal in a uniform regular hypergraph is an independent set attaining the Delsarte--Hoffman bound in the vertex adjacency multigraph of this hypergraph; 3) combinatorial designs with parameters $t$-$(v,k,\lambda)$ and similar $q$-designs, difference sets, Hadamard matrices, and bent functions are equivalent to perfect colorings of special graphs and multigraphs, in particular, it is true in the cases of the Johnson graphs $J(n,k)$ for $(k-1)$-$(v,k,\lambda)$ designs and the Grassmann graphs $J_2(n,2)$ for bent functions. Keywords: perfect coloring, equitable partition, transversal of hypergraph, combinatorial design, $q$-design, difference set, bent function, Johnson graph, Grassmann graph, Delsarte--Hoffman bound, Comment: This is improved version of the paper published in Siberian Mathematical Journal. We fix some misprints and a gap in the proof of Theorem 2

Existence of strongly bound water molecules on silicate surfaces, above the desorption temperature of water ice, has been first predicted by computational studies and recently demonstrated by laboratory experiments. Such trapped water may be present in various astrophysical environments and there is now evidence for its presence in the diffuse interstellar medium and in extraterrestrial particles. We present here new results of a laboratory study of the phenomenon of trapping (strong bonding) of water molecules by silicates. We show that the efficiency of trapping is strongly dependent on the properties and composition of the surface. Our results point out that the presence of trapped water should be due to the hydrophilic properties of the silicate surface and that the nature of trapping is physical (physisorption rather than chemisorption). We demonstrate that water can be trapped on silicates up to the temperatures of about 470 K, which speaks for the presence of wet silicate grains in the terrestrial planet formation zone in planet-forming disks. Studying the thermal and UV stability of trapped water, we conclude that the detection of trapped water in the diffuse ISM speaks for its efficient continuous formation. We discuss our results as relevant to fundamental scientific questions, such as the oxygen depletion problem, the origin of water on Earth, and the formation of rocky planets., Comment: Accepted for publication in ApJ

Robots are becoming an increasingly common part of scientific work within laboratory environments. In this paper, we investigate the problem of designing \emph{schedules} for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex at any given timestep. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that this problem is NP-complete for many simple classes of graphs, the problem of determining the fastest schedule, defined by the number of time steps required for a robot to visit every vertex in the schedule and complete every task assigned in its assigned schedule. Explicitly, we provide this result for complete graphs, bipartite graphs, star graphs, and planar graphs. Finally, we provide positive results for line graphs, showing that we can find an optimal set of schedules for $k$ robots completing $m$ tasks of equal length of a path of length $n$ in $O(kmn)$ time, and a $k$-approximation when the length of the tasks is unbounded.

The problem of ponderomotive separation of ions with different charge-to-mass ratios under the influence of Alfven waves, which permanently exist in the magnetosphere in the form of geomagnetic pulsations, is posed. Formulas are derived for partial ponderomotive forces acting on light and heavy (metal) ions. In the quasi-hydrodynamic approximation, it was found that the Clarke number, which characterizes the metallicity of the plasma, is maximum at the minimum of the magnetic field on the field line along which the Alfv\'en wave propagates. Key words: ponderomotive forces, Alfv\'en waves, heavy ions, Clarke number., Comment: 10 pages

Denote by Q_d the d-dimensional hypercube. Addressing a recent question we estimate the number of ways the vertex set of Q_d can be partitioned into vertex disjoint smaller cubes. Among other results, we prove that the asymptotic order of this function is not much larger than the number of perfect matchings of Q_d. We also describe several new (and old) questions., Comment: Proofs slightly shortened and referee comments addressed