26838 research outputs found
Sort by
Resource allocation based on past incident patterns
Full text linkWe formulate and solve two resource allocation problems motivated by a preparedness question of emergency response services. First, we consider the assignment of vehicles to stations, and, in a second step, assign crews to vehicles. In both cases, we work in a minimax framework and define the objective function for a spatial catchment area as the total risk in this area per resource unit allocated to it. The solutions are explicit and can be calculated in practice by a greedy algorithm that successively allocates a resource unit to an area having maximal relative risk, with suitable tie breaker rules. The approach is illustrated on a data set of incidents reported to the Twente Fire Brigade
An overview of convergence rates for sum of squares hierarchies in polynomial optimization
Full text linkIn this chapter we consider polynomial optimization problems, asking to minimize a polynomial function over a compact semialgebraic set, defined by polynomial inequalities. This models a great variety of (in general, nonlinear nonconvex) optimization problems. Various hierarchies of (lower and upper) bounds have been introduced, having the remarkable property that they converge asymptotically to the global minimum. These bounds exploit algebraic representations of positive polynomials in terms of sums of squares and can be computed using semidefinite optimization. Our focus in this chapter lies in the performance analysis of these hierarchies of bounds, namely, in how far the bounds are from the global minimum as the degrees of the sums of squares they involve tend to infinity. We present the main state-of-the-art results and offer a gentle introductory overview over the various techniques that have been recently developed to establish them, stemming from the theory of orthogonal polynomials, approximation theory, Fourier analysis, and more
Solving the UVN-flash problem in TVN-space
Full text linkIn this paper, we investigate the phase equilibrium problem for multicomponent mixtures under specified internal energy (), volume (), and mole numbers (, commonly known as the UVN-flash problem. While conventional phase equilibrium calculations typically use pressure–temperature-mole number () specifications, the UVN formulation is essential for dynamic simulations of closed systems and energy balance computations. Existing approaches, including those based on iterative pressure-temperature updates and direct entropy maximization, can suffer from computational inefficiencies due to inner Newton iterations needed to solve for temperature at specified internal energy and volume . In this work, we present a reformulation of the UVN-flash problem that eliminates the need for the inner Newton iterations, addressing a computational bottleneck. We begin with stability analysis and discuss a strategy to generate the initial guess for the UVN-flash from the stability analysis results. We then reformulate the UVN-flash problem in TVN-space as constrained entropy maximization. We provide a detailed derivation of Michelsen’s Q-function using the method of Lagrange multipliers, illustrating its direct application in solving the UVN-flash problem. Furthermore, we discuss the numerical methods used, including gradient and Hessian computations. The reformulation is validated against benchmark cases, demonstrating improved efficiency
Comparing the reliability of individual differences for various measurement models in conflict tasks
No full textThere is a growing realization that experimental tasks that produce reliable effects in group comparisons can simultaneously provide unreliable assessments of individual differences. Proposed solutions to this “reliability paradox” range from collecting more test trials to modifying the tasks and/or the way in which effects are measured from these tasks. Here, we systematically compare two proposed modeling solutions in a cognitive conflict task. Using the ratio of individual variability of the conflict effect (i.e., signal) and the trial-by-trial variation in the data (i.e., noise) obtained from Bayesian hierarchical modeling, we examine whether improving statistical modeling may improve the reliability of individual differences assessment in four Stroop datasets. The proposed improvements are (1) increasing the descriptive adequacy of the statistical models from which conflict effects are derived, and (2) using psychologically motivated measures from cognitive measurement models. Our results show that the type of model does not have a consistent effect on the signal-to-noise ratio: the proposed solutions improved reliability in only one of the four datasets. We provide analytical and simulation-based approaches to compute the signal-to-noise ratio for a range of models of varying sophistication and discuss their potential to aid in developing and comparing new measurement solutions to the reliability paradox
Path decompositions of oriented graphs
No full textWe consider the problem of decomposing the edges of a digraph into as few paths as possible. A natural lower bound for the number of paths in any path decomposition of a digraph D is 12∑v∈V(D)|d+(v)−d−(v)|; any digraph that achieves this bound is called consistent. Alspach et al. 1976 conjectured in 1976 that every tournament of even order is consistent and this was recently verified for large tournaments by Girão et al. 2023. A more general conjecture of Pullman (Reid and Wayland, 1987) states that for odd d, every orientation of a d-regular graph is consistent. We prove that the conjecture holds for random d-regular graphs with high probability i.e. for fixed odd d and as n→∞ the conjecture holds for almost all d-regular graphs. Along the way, we verify Pullman’s conjecture for graphs whose girth is sufficiently large (as a function of the degree)
Reduced subgrid scale terms in three-dimensional turbulence
Full text linkLarge eddy simulation (LES) has become a central technique for simulating turbulent flows in engineering and applied sciences, offering a compromise between accuracy and computational cost by resolving large-scale motions and modeling the effects of smaller, unresolved scales through a subgrid scale (SGS) model. The fidelity and robustness of LES depends critically on the SGS model, particularly in coarse simulations where much of the turbulence spectrum remains unresolved.
In this work, we extend the tau-orthogonal (TO) method, a data-driven SGS modeling framework, to three-dimensional turbulent flows. The method reformulates the high-dimensional SGS closure problem as a low-dimensional prediction task focused on spatially-integrated, scale-aware quantities of interest (QoIs). We extend the model to incorporate QoI-state dependence and temporal correlations by combining regularized least-squares regression with a multivariate Gaussian residual model. This yields a simple yet effective stochastic time-series prediction model, with orders-of-magnitude fewer parameters than typical deep learning approaches which try to directly learn the high-dimensional SGS closure.
We demonstrate the effectiveness of the new TO model in three-dimensional forced isotropic turbulence, turbulent channel flow and on a Taylor-Green vortex. The model achieves accurate long-term QoI distributions, robust performance across hyperparameter settings, and good reproduction of key flow features such as kinetic energy spectra and coherent structures, despite being trained solely on QoI trajectories. Comparisons against classical SGS models, including Smagorinsky and WALE formulations, highlight the new model's balance of accuracy and computational efficiency
Approximation via duality in offline, online and strategic settings
Full text linkThe main questions studied in this thesis can be broadly stated as follows: given an NP-hard combinatorial optimization problem and a suboptimal solution to this problem – obtained, for instance, by an efficient approximation algorithm – how close can this solution get to the optimal one? The quality of a solution is measured by the worst-case ratio, over all input instances, between the cost of the suboptimal solution and that of the optimal one.
The aim of this thesis is to develop new techniques for proving tight bounds on this question for three fundamental classes of combinatorial optimization problems: covering, matching, and scheduling. Moreover, this question is studied in three different, yet related, contexts. These include the classical offline setting , where the entire input to a problem is known in advance; the online setting , where the input is revealed over time and algorithms must make irrevocable decisions; and a game-theoretic setting , where solutions arise as Nash equilibria. A unifying theme of this thesis is the use of convex programming relaxations, such as linear programming and semidefinite programming. These relaxations admit a rich duality theory, which is often exploited in order to construct carefully chosen dual solutions yielding tight performance guarantees
Asymptotic tensor rank is characterized by polynomials
Full text linkAsymptotic tensor rank, originally developed to characterize the complexity of matrix multiplication, is a parameter that plays a fundamental role in problems in mathematics, computer science and quantum information. This parameter is notoriously difficult to determine; indeed, determining its value for the 2 × 2 matrix multiplication tensor would determine the matrix multiplication exponent, a long-standing open problem.
Strassen's asymptotic rank conjecture, on the other hand, makes the bold statement that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Recent works have proved strong consequences of Strassen's asymptotic rank conjecture in computational complexity theory. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank; for instance whether it is computable.
We prove that asymptotic tensor rank is "computable from above", that is, for any real number there is an (efficient) algorithm that determines, given a tensor , if the asymptotic tensor rank of is at most . The algorithm has a simple structure; it consists of evaluating a finite list of polynomials on the tensor. Indeed, we prove that the sublevel sets of asymptotic rank are Zariski-closed (just like matrix rank). While we do not exhibit these polynomials explicitly, their mere existence has strong implications on the structure of asymptotic rank.
As one such implication, we find that the values that asymptotic tensor rank takes, on all tensors, is a well-ordered set. In other words, any non-increasing sequence of asymptotic ranks stabilizes ("discreteness from above"). In particular, for the matrix multiplication exponent (which is the base-2 logarithm of an asymptotic rank) there is no sequence of exponents of bilinear maps that approximates it arbitrarily closely from above without being eventually constant. In other words, any such upper bound on the matrix multiplication exponent that is close enough, will "snap" to it. Previously such discreteness results were only known for finite fields or for other tensor parameters (e.g., asymptotic slice rank). We obtain them for infinite fields like the complex numbers.
We prove our result more generally for a large class of functions on tensors, and in particular obtain similar properties for all functions in Strassen's asymptotic spectrum of tensors. We prove a variety of related structural results on the way. For instance, we prove that for any converging sequence of asymptotic ranks, the limit is also an asymptotic rank for some tensor. We leave open whether asymptotic rank is also discrete from below (which would be implied by Strassen's asymptotic rank conjecture)
Refined modelling of the primal attack, and variants against Module-Learning with Errors
No full textLearning to judge: LLMs designing and applying evaluation rubrics
No full textLarge language models (LLMs) are increasingly used as evaluators for natural language generation, applying human-defined rubrics to assess system outputs. However, human rubrics are often static and misaligned with how models internally represent language quality. We introduce GER-Eval (Generating Evaluation Rubrics for Evaluation) to investigate whether LLMs can design and apply their own evaluation rubrics. We evaluate the semantic coherence and scoring reliability of LLM-defined criteria and their alignment with human criteria. LLMs reliably generate interpretable and task-aware evaluation dimensions and apply them within models, but their scoring reliability degrades in factual and knowledge-intensive settings. Closed-source models such as GPT4o achieve higher agreement and cross-model generalization than open-weight models such as Llama. Our findings position evaluation as a learned linguistic capability of LLMs, consistent within models but fragmented across them, and call for new methods that jointly model human and LLM evaluative language to improve reliability and interpretability