Search

We introduce a new approach for deterministic sensitivity analysis of Markov reward processes, commonly used in cost-effectiveness analyses, via reformulation into a polynomial system. Our approach leverages cylindrical algebraic decomposition (CAD), a technique arising from algebraic geometry that provides an exact description of all solutions to a polynomial system. While it is typically intractable to build a CAD for systems with more than a few variables, we show that a special class of polynomial systems, which includes the polynomials arising from Markov reward processes, can be analyzed much more tractably. We establish several theoretical results about such systems and develop a specialized algorithm to construct their CAD, which allows us to perform exact, multi-way sensitivity analysis for common health economic analyses. We develop an open-source software package that implements our algorithm. Finally, we apply it to two case studies, one with synthetic data and one that re-analyzes a previous cost-effectiveness analysis from the literature, demonstrating advantages of our approach over standard techniques. Our software and code are available at: \url{https://github.com/mmaaz-git/markovag}., Comment: 46 pages

Bubble-particle collisions in turbulence are key to the froth flotation process that is employed industrially on a vast scale to separate hydrophobic from hydrophilic materials. In our previous study (Chan et al., J. Fluid Mech., vol. 959, 2023, A6), we elucidated the collision mechanisms and critically reviewed the collision models in the no-gravity limit. In reality, gravity may play a role since ultimately separation is achieved through buoyancy induced rising of the bubbles. This effect has been included in several collision models, which have remained without a proper validation thus far due to a scarcity of available data. We therefore conduct direct numerical simulations of bubble and particles in homogeneous isotropic turbulence with various Stokes, Froude, and Reynolds numbers using the point-particle approximation. Generally, we find that turbulence enhances the collision rate compared to the pure relative settling case by increasing the collision velocity. Surprisingly, however, we observe that for certain parameters the collision rate is lower with turbulence compared to without. This is due to turbulence-induced bubble-particle spatial segregation, which is most prevalent at weak relative gravity and decreases as gravitational effects become more dominant, and reduced bubble slip velocity in turbulence. The existing bubble-particle collision models only qualitatively capture the trends in our numerical data. To improve on this, we extend the model by Dodin & Elperin (Phys. Fluids, vol. 14, no. 8, 2002, pp.2921-2924) to the bubble-particle case and found excellent quantitative agreement for small Stokes numbers when segregation is accounted for.

We propose a robust optimization approach for constructing confidence bands for stochastic processes using a finite number of simulated sample paths. Our approach can be used to quantify uncertainty in realizations of stochastic processes or validate stochastic simulation models by checking whether historical paths from the actual system fall within the constructed confidence band. Unlike existing approaches in the literature, our methodology is widely applicable and directly addresses optimization bias within the constraints, producing tight confidence bands with accurate coverage probabilities. It is tractable, being only slightly more complex than the state-of-the-art baseline approach, and easy to use, as it employs standard techniques. Additionally, our approach is also applicable to continuous-time processes after appropriately discretizing time. In our first case study, we show that our approach achieves the desired coverage probabilities with an order-of-magnitude fewer sample paths than the state-of-the-art baseline approach. In our second case study, we illustrate how our approach can be used to validate stochastic simulation models.

We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following: * For $n$ axis-aligned boxes in any constant dimension $d$, we give an $O(\log \log n)$-approximation algorithm for MPS that runs in $O(n^{1+\delta})$ time for an arbitrarily small constant $\delta>0$. This significantly improves the previous $O(\log\log n)$-approximation algorithm by Agarwal, Har-Peled, Raychaudhury, and Sintos (SODA~2024), which ran in $O(n^{d/2}\mathop{\rm polylog} n)$ time. * Furthermore, we show that our algorithm can be made fully dynamic with $O(n^{\delta})$ amortized update time. Previously, Agarwal et al.~(SODA~2024) obtained dynamic results only in $\mathbb{R}^2$ and achieved only $O(\sqrt{n}\mathop{\rm polylog} n)$ amortized expected update time. * For $n$ axis-aligned rectangles in $\mathbb{R}^2$, we give an $O(1)$-approximation algorithm for MIS that runs in $O(n^{1+\delta})$ time. Our result significantly improves the running time of the celebrated algorithm by Mitchell (FOCS~2021) (which was about $O(n^{21})$), and answers one of his open questions. Our algorithm can also be made fully dynamic with $O(n^{\delta})$ amortized update time. * For $n$ (unweighted or weighted) fat objects in any constant dimension, we give a dynamic $O(1)$-approximation algorithm for MIS with $O(n^{\delta})$ amortized update time. * For disks in $\mathbb{R}^2$ or hypercubes in any constant dimension, we give the first fully dynamic $(1+\varepsilon)$-approximation algorithms for MVC and MCM with $O(\mathop{\rm polylog}n)$ amortized update time., Comment: This paper includes the results on vertex cover and matching from our previous arXiv submission (arXiv:2402.07441), along with new results on piercing and independent sets. Abstract shortened to meet arXiv limit

We consider the problem of load balancing in parallel queues by transferring customers between them at discrete points in time. Holding costs accrue as customers wait in the queue, while transfer decisions incur both fixed (setup) and variable costs proportional to the number and direction of transfers. Our work is primarily motivated by inter-facility patient transfers between hospitals during a surge in demand for hospitalization (e.g., during a pandemic). By analyzing an associated fluid control problem, we show that under fairly general assumptions including time-varying arrivals and convex increasing holding costs, the optimal policy in each period partitions the state-space into a well-defined $\textit{no-transfer region}$ and its complement, such that transferring is optimal if and only if the system is sufficiently imbalanced. In the absence of fixed transfer costs, an optimal policy moves the state to the no-transfer region's boundary; in contrast, with fixed costs, the state is moved to the no-transfer region's relative interior. We further leverage the fluid control problem to provide insights on the trade-off between holding and transfer costs, emphasizing the importance of preventing excessive idleness when transfers are not feasible in continuous-time. Using simulation experiments, we investigate the performance and robustness of the fluid policy for the stochastic system. In particular, our case study calibrated using data during the pandemic in the Greater Toronto Area demonstrates that transferring patients between hospitals could result in up to 27.7% reduction in total cost with relatively few transfers.

Adaptive robust optimization problems have received significant attention in recent years, but remain notoriously difficult to solve when recourse decisions are discrete in nature. In this paper, we propose new reformulation techniques for adaptive robust binary optimization (ARBO) problems with objective uncertainty. Without loss of generality, we focus on ARBO problems with "selective adaptability", a term we coin to describe a common class of linking constraints between first-stage and second-stage solutions. Our main contribution revolves around a collection of exact and approximate network flow reformulations for the ARBO problem, which we develop by building upon ideas from the decision diagram literature. Our proposed models can generate feasible solutions, primal bounds and dual bounds, while their size and approximation quality can be precisely controlled through user-specified parameters. Furthermore, and in contrast with existing solution methods, these models are easy to implement and can be solved directly with standard off-the-shelf solvers. Through an extensive set of computational experiments, we show that our models can generate high-quality solutions and dual bounds in significantly less time than popular benchmark methods, often by orders of magnitude.

We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotation (if it exists), or more generally, find the largest copy of $P$ inside $Q$ under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required $\Omega(n^2)$ time, even in the simplest $k=3$ case. We present a significantly faster new algorithm for $k=3$ achieving $O(n$polylog $n)$ running time. Moreover, we extend the result for general $k$, achieving $O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ running time for any $\varepsilon>0$. Along the way, we also prove a new $O(k^{O(1)}n$polylog $n)$ bound on the number of similar copies of $P$ inside $Q$ that have 4 vertices of $P$ in contact with the boundary of $Q$ (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998)., Comment: To appear in SoCG 2024

Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1. Semialgebraic range stabbing. We present a data structure for $n$ semialgebraic ranges in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of ranges containing a query point in $O(n^{1/4+\varepsilon})$ time, for an arbitrarily small constant $\varepsilon>0$. 2. Ray shooting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in $O(n^{1/4+\varepsilon})$ time. 3. Intersection counting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in $O(n^{1/2+\varepsilon})$ time. In particular, this implies an $O(n^{3/2+\varepsilon})$-time algorithm for counting intersections between two sets of $n$ algebraic arcs in 2D., Comment: SOCG 2024

Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses all points in $X$. Here a point $x \in X$ is enclosed by $\mathcal{O}^*$ if it lies in a bounded connected component of $\mathbb{R}^2 \backslash (\bigcup_{O \in \mathcal{O}^*} O)$. We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in $O(1)$-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an $O(\alpha(n)\log n)$-approximation algorithm for segments, where $\alpha(n)$ is the inverse Ackermann function, and an $O(\log n)$-approximation algorithm for disks., Comment: In SoCG'24

In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects, e.g., disks, rectangles, hypercubes, etc., in $d$-dimensional Euclidean space. We consider the problems in fully dynamic settings, allowing insertions and deletions of objects. We develop a general framework for dynamic MVC in intersection graphs, achieving sublinear amortized update time for most natural families of geometric objects. In particular, we show that - - For a dynamic collection of disks in $\mathbb{R}^2$ or hypercubes in $\mathbb{R}^d$ (for constant $d$), it is possible to maintain a $(1+\varepsilon)$-approximate vertex cover in polylog amortized update time. These results also hold in the bipartite case. - For a dynamic collection of rectangles in $\mathbb{R}^2$, it is possible to maintain a $(\frac{3}{2}+\varepsilon)$-approximate vertex cover in polylog amortized update time. Along the way, we obtain the first near-linear time static algorithms for MVC in the above two cases with the same approximation factors. Next, we turn our attention to the MCM problem. Although our MVC algorithms automatically allow us to approximate the size of the MCM in bipartite geometric intersection graphs, they do not produce a matching. We give another general framework to maintain an approximate maximum matching, and further extend the approach to handle non-bipartite intersection graphs. In particular, we show that - - For a dynamic collection of (bichromatic or monochromatic) disks in $\mathbb{R}^2$ or hypercubes in $\mathbb{R}^d$ (for constant $d$), it is possible to maintain a $(1+\varepsilon)$-approximate matching in polylog amortized update time., Comment: 25 Pages

We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as "global" connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data structure by Afshani and Chan (ESA'06) achieved such bounds only in the special case of axis-aligned line segments or rectangles but did not work for arbitrary line segments or disks, whereas the data structures by Chan, P\u{a}tra\c{s}cu and Roditty (FOCS'08) worked for more general classes of geometric objects but required $n^{\Omega(1)}$ query time and could not handle global connectivity queries. Specifically, we obtain new data structures with $O(1)$ query time and amortized update time near $n^{4/5}$, $n^{7/8}$, and $n^{20/21}$ for axis-aligned line segments, disks, and arbitrary line segments respectively. Besides greatly reducing the query time, our data structures also improve the previous update times for axis-aligned line segments by Afshani and Chan (from near $n^{10/11}$ to $n^{4/5}$) and for disks by Chan, P\u{a}tra\c{s}cu, and Roditty (from near $n^{20/21}$ to $n^{7/8}$).

Inverse optimization has been increasingly used to estimate unknown parameters in an optimization model based on decision data. We show that such a point estimation is insufficient in a prescriptive setting where the estimated parameters are used to prescribe new decisions. The prescribed decisions may be low-quality and misaligned with human intuition and thus are unlikely to be adopted. To tackle this challenge, we propose conformal inverse optimization, which seeks to learn an uncertainty set for the unknown parameters and then solve a robust optimization model to prescribe new decisions. Under mild assumptions, we show that our method enjoys provable guarantees on solution quality, as evaluated using both the ground-truth parameters and the decision maker's perception of the unknown parameters. Our method demonstrates strong empirical performance compared to classic inverse optimization.

We present the first optimal randomized algorithm for constructing the order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running time is $O(n\log n + nk)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA'22) in combination with Ramos's cutting construction, to reduce the problem to verifying an order-$k$ Voronoi diagram, and (ii) solve the verification problem by a new divide-and-conquer algorithm using planar-graph separators. We also describe a deterministic algorithm for constructing the $k$-level of $n$ lines in two dimensions in $O(n\log n + nk^{1/3})$ time, and constructing the $k$-level of $n$ planes in three dimensions in $O(n\log n + nk^{3/2})$ time. These time bounds (ignoring the $n\log n$ term) match the current best upper bounds on the combinatorial complexity of the $k$-level. Previously, the same time bound in two dimensions was obtained by Chan (1999) but with randomization., Comment: To appear in SODA 2024. 16 pages, 1 figure

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift $i$, under the standard Word-RAM model with $\Theta(\log n)$-bit words. - We provide an $O(n\sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O(n\sqrt{m}(\log m\log\log m)^{1/4})$ running time. Our randomized algorithm extends to the $k$-bounded setting, with running time $O\big(n+\frac{nk}{\sqrt{m}}\big)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uzna\'{n}ski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. - For the $(1+\epsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\tilde{O}(\epsilon^{-0.93}n)$ time Monte Carlo randomized algorithm, beating the previous $\tilde{O}(\epsilon^{-1}n)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with $3$SUM, and uses a combination of Fredman's trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of $3$SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of $3$SUM., Comment: Appeared in FOCS 2023. Abstract shortened to fit arXiv requirements. v2: added reference and discussion related to Lemma 2.2 and Appendix B

In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cycles was considered by Jin and Xu [STOC 2023], who used it as an intermediate problem to show $3$SUM hardness of All-Edges Sparse Triangle with few $4$-cycles (independently obtained by Abboud, Bringmann and Fischer [STOC 2023]), which is further used to show $3$SUM hardness of a variety of problems, including $4$-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths and All-Nodes Shortest Cycles. We provide a simple reduction from Exact Triangle to Exact Triangle with few zero-weight $4$-cycles. Our new reduction not only simplifies Jin and Xu's previous reduction, but also strengthens the conditional lower bounds from being under the $3$SUM hypothesis to the even more believable Exact Triangle hypothesis. As a result, all conditional lower bounds shown by Jin and Xu [STOC 2023] and by Abboud, Bringmann and Fischer [STOC 2023] using All-Edges Sparse Triangle with few $4$-cycles as an intermediate problem now also hold under the Exact Triangle hypothesis. We also provide two alternative proofs of the conditional lower bound of the All-Edges Sparse Triangle problem under the Exact Triangle hypothesis, which was originally proved by Vassilevska Williams and Xu [FOCS 2020]. Both of our new reductions are simpler, and one of them is also deterministic -- all previous reductions from Exact Triangle or 3SUM to All-Edges Sparse Triangle (including P\u{a}tra\c{s}cu's seminal work [STOC 2010]) were randomized., Comment: To appear in SOSA 2024

For decades, National Football League (NFL) coaches' observed fourth down decisions have been largely inconsistent with prescriptions based on statistical models. In this paper, we develop a framework to explain this discrepancy using an inverse optimization approach. We model the fourth down decision and the subsequent sequence of plays in a game as a Markov decision process (MDP), the dynamics of which we estimate from NFL play-by-play data from the 2014 through 2022 seasons. We assume that coaches' observed decisions are optimal but that the risk preferences governing their decisions are unknown. This yields an inverse decision problem for which the optimality criterion, or risk measure, of the MDP is the estimand. Using the quantile function to parameterize risk, we estimate which quantile-optimal policy yields the coaches' observed decisions as minimally suboptimal. In general, we find that coaches' fourth-down behavior is consistent with optimizing low quantiles of the next-state value distribution, which corresponds to conservative risk preferences. We also find that coaches exhibit higher risk tolerances when making decisions in the opponent's half of the field as opposed to their own half, and that league average fourth down risk tolerances have increased over time., Comment: 22 pages, 12 figures

Cycling stress assessment, which quantifies cyclists' perceived stress imposed by the built environment and motor traffics, increasingly informs cycling infrastructure planning and cycling route recommendation. However, currently calculating cycling stress is slow and data-intensive, which hinders its broader application. In this paper, We propose a deep learning framework to support accurate, fast, and large-scale cycling stress assessments for urban road networks based on street-view images. Our framework features i) a contrastive learning approach that leverages the ordinal relationship among cycling stress labels, and ii) a post-processing technique that enforces spatial smoothness into our predictions. On a dataset of 39,153 road segments collected in Toronto, Canada, our results demonstrate the effectiveness of our deep learning framework and the value of using image data for cycling stress assessment in the absence of high-quality road geometry and motor traffic data.

Measuring soccer shooting skill is a challenging analytics problem due to the scarcity and highly contextual nature of scoring events. The introduction of more advanced data surrounding soccer shots has given rise to model-based metrics which better cope with these challenges. Specifically, metrics such as expected goals added, goals above expectation, and post-shot expected goals all use advanced data to offer an improvement over the classical conversion rate. However, all metrics developed to date assign a value of zero to off-target shots, which account for almost two-thirds of all shots, since these shots have no probability of scoring. We posit that there is non-negligible shooting skill signal contained in the trajectories of off-target shots and propose two shooting skill metrics that incorporate the signal contained in off-target shots. Specifically, we develop a player-specific generative model for shot trajectories based on a mixture of truncated bivariate Gaussian distributions. We use this generative model to compute metrics that allow us to attach non-zero value to off-target shots. We demonstrate that our proposed metrics are more stable than current state-of-the-art metrics and have increased predictive power.

In recent years, there has been tremendous progress in the development of quantum computing hardware, algorithms and services leading to the expectation that in the near future quantum computers will be capable of performing simulations for natural science applications, operations research, and machine learning at scales mostly inaccessible to classical computers. Whereas the impact of quantum computing has already started to be recognized in fields such as cryptanalysis, natural science simulations, and optimization among others, very little is known about the full potential of quantum computing simulations and machine learning in the realm of healthcare and life science (HCLS). Herein, we discuss the transformational changes we expect from the use of quantum computation for HCLS research, more specifically in the field of cell-centric therapeutics. Moreover, we identify and elaborate open problems in cell engineering, tissue modeling, perturbation modeling, and bio-topology while discussing candidate quantum algorithms for research on these topics and their potential advantages over classical computational approaches., Comment: 6 figures

We study the time complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We obtain a plethora of new results: - We give the first subquadratic algorithm for rectilinear discrete 3-center in 2D, running in $\widetilde{O}(n^{3/2})$ time. - We prove a lower bound of $\Omega(n^{4/3-\delta})$ for rectilinear discrete 3-center in 4D, for any constant $\delta>0$, under a standard hypothesis about triangle detection in sparse graphs. - Given $n$ points and $n$ weighted axis-aligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimum-weight cover of the points by 3 unit squares, running in $\widetilde{O}(n^{8/5})$ time. We also prove a lower bound of $\Omega(n^{3/2-\delta})$ for the same problem in 2D, under the well-known APSP Hypothesis. For arbitrary axis-aligned rectangles in 2D, our upper bound is $\widetilde{O}(n^{7/4})$. - We prove a lower bound of $\Omega(n^{2-\delta})$ for Euclidean discrete 2-center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of $\widetilde{O}(n^\omega)$, if the matrix multiplication exponent $\omega$ is equal to 2. - We similarly prove an $\Omega(n^{k-\delta})$ lower bound for Euclidean discrete $k$-center in $O(k)$ dimensions for any constant $k\ge 3$, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if $\omega=2$. - We also prove an $\Omega(n^{2-\delta})$ lower bound for the problem of finding 2 boxes to cover the largest number of points, given $n$ points and $n$ boxes in 12D. This matches the straightforward near-quadratic upper bound., Comment: Accepted to ICALP'23

In SoCG 2022, Conroy and T\'oth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an $O(n\log n)$-size 3-hop spanner for $n$ disks (or fat convex objects) in the plane, and an $O(n\log^2 n)$-size 3-hop spanner for $n$ axis-aligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allowing larger constant stretch? and (ii) can near-linear size be achieved for more general classes of intersection graphs? We address both questions simultaneously, by presenting new constructions of constant-hop spanners that have almost linear size and that hold for a much larger class of intersection graphs. More precisely, we prove the existence of an $O(1)$-hop spanner for arbitrary string graphs with $O(n\alpha_k(n))$ size for any constant $k$, where $\alpha_k(n)$ denotes the $k$-th function in the inverse Ackermann hierarchy. We similarly prove the existence of an $O(1)$-hop spanner for intersection graphs of $d$-dimensional fat objects with $O(n\alpha_k(n))$ size for any constant $k$ and $d$. We also improve on some of Conroy and T\'oth's specific previous results, in either the number of hops or the size: we describe an $O(n\log n)$-size 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an $O(n\log n)$-size 3-hop spanner for axis-aligned rectangles in the plane. Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings.

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou\v{s}ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights in $\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $\omega=2$), we show a variety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower bound for unweighted directed APSP and an $n^{2.2-o(1)}$ lower bound for computing the Minimum Witness Product between two $n \times n$ Boolean matrices, even if $\omega=2$, improving upon their trivial $n^2$ lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when $\omega = 2$), if unweighted directed APSP requires $n^{2.5-o(1)}$ time, then Minimum Witness Product requires $n^{7/3-o(1)}$ time. - We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. - We obtain new algorithms using new variants of the Balog-Szemer\'edi-Gowers theorem from additive combinatorics. For example, we get an $O(n^{3.83})$ time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook $\widetilde{O}(n^{4})$ time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in $\{1, 2, \ldots, n\}^d$., Comment: To appear at STOC'23

We present a (combinatorial) algorithm with running time close to $O(n^d)$ for computing the minimum directed $L_\infty$ Hausdorff distance between two sets of $n$ points under translations in any constant dimension $d$. This substantially improves the best previous time bound near $O(n^{5d/4})$ by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan's algorithm [FOCS'13] for Klee's measure problem. To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to $\Omega(n^d)$ for combinatorial algorithms, under the Combinatorial $k$-Clique Hypothesis., Comment: To appear in SoCG 2023

Purpose: To develop a machine learning-based, 3D dose prediction methodology for Gamma Knife (GK) radiosurgery. The methodology accounts for cases involving targets of any number, size, and shape. Methods: Data from 322 GK treatment plans was modified by isolating and cropping the contoured MRI and clinical dose distributions based on tumor location, then scaling the resulting tumor spaces to a standard size. An accompanying 3D tensor was created for each instance to account for tumor size. The modified dataset for 272 patients was used to train both a generative adversarial network (GAN-GK) and a 3D U-Net model (U-Net-GK). Unmodified data was used to train equivalent baseline models. All models were used to predict the dose distribution of 50 out-of-sample patients. Prediction accuracy was evaluated using gamma, with criteria of 4%/2mm, 3%/3mm, 3%/1mm and 1%/1mm. Prediction quality was assessed using coverage, selectivity, and conformity indices. Results: The predictions resulting from GAN-GK and U-Net-GK were similar to their clinical counterparts, with average gamma (4%/2mm) passing rates of 84.9 and 83.1, respectively. In contrast, the gamma passing rate of baseline models were significantly worse than their respective GK-specific models (p < 0.001) at all criterion levels. The quality of GK-specific predictions was also similar to that of clinical plans. Conclusion: Deep learning models can use GK-specific data modification to predict 3D dose distributions for GKRS plans with a large range in size, shape, or number of targets. Standard deep learning models applied to unmodified GK data generated poorer predictions., Comment: Submitted to Physica Medica

We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example: * For the intersection graph of $n$ line segments in the plane, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time, a size-3 independent set in $O(n^{1.652})$ time, a 4-clique in near-$O(n^{24/13})$ time, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.565k+O(1)})$ time for any constant $k$; we can also compute the girth in near-$O(n^{3/2})$ time. * For the intersection graph of $n$ axis-aligned boxes in a constant dimension $d$, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time for any $d$, a 4-clique (or any 4-vertex induced subgraph) in $O(n^{1.715})$ time for any $d$, a size-4 independent set in near-$O(n^{3/2})$ time for any $d$, a size-5 independent set in near-$O(n^{4/3})$ time for $d=2$, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.429k+O(1)})$ time for any $d$ and any constant $k$. * For the intersection graph of $n$ fat objects in any constant dimension $d$, we give an algorithm to find any $k$-vertex (non-induced) subgraph in $O(n\log n)$ time for any constant $k$, generalizing a result by Kaplan, Klost, Mulzer, Roddity, Seiferth, and Sharir (1999) for 3-cycles in 2D disk graphs. A variety of techniques is used, including geometric range searching, biclique covers, "high-low" tricks, graph degeneracy and separators, and shifted quadtrees. We also prove a near-$\Omega(n^{4/3})$ conditional lower bound for finding a size-4 independent set for boxes., Comment: To appear in SODA 2023

In this paper, we examine how soccer players can use their spatial relationships to control parts of the field and safely move play up the field via chains of ``safe configurations,'' i.e. configurations of players on a team ensuring the possessor of the ball has a collection of open passing options all connected by open passing lanes. An underlying philosophy behind our work is that it is most difficult to disrupt an attacking team's progression forward (with the ball) when this attacking team has multiple ``good'' options of how to proceed at each moment in time. We provide some evidence of this. Our main construction is a directed weighted graph where the nodes encode the configurations of players, the directed edges encode transformations between these configurations, and the weights encode the relative frequencies of the transformations. We conclude with a few applications and proposed further investigations. We believe that our work can serve as a launching platform for significant further investigation into how teams can ``safely progress'' the ball up the field, strategy development, and sophisticated decision making metrics. For coaches and players, we aim to streamline the process of moving safely up the field. In particular, we aim to construct a framework for creating new successful patterns of movement and aim that our framework allows for the development of new strategy. At the same time, our work could help identify configurations on the field which often result in turnovers or that allow for a lot of strategic flexibility (also impeding defensive containment of the attacking team). *Because the contributions of the female authors to this paper were by no means less than those of the male authors, we have chosen to reverse convention and to list the authors in reverse alphabetical order to ensure that the female authors were not listed only after the male authors., Comment: correction to bug in code (leading to new figures and example) and to a few references

We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following: $\bullet$ For a set of $n$ points in a constant dimension $d$, we give data structures with $O(n^d)$ (or slightly better) space that can answer simplex range counting queries in optimal $O(\log n)$ time and simplex range reporting queries in optimal $O(\log n + k)$ time, where $k$ denotes the output size. For semigroup range searching, we obtain $O(\log n)$ query time with $O(n^d\mathop{\rm polylog}n)$ space. Previous data structures with similar space bounds by Matou\v{s}ek from nearly three decades ago had $O(\log^{d+1}n)$ or $O(\log^{d+1}n + k)$ query time. $\bullet$ For a set of $n$ simplices in a constant dimension $d$, we give data structures with $O(n)$ space that can answer stabbing counting queries (counting the number of simplices containing a query point) in $O(n^{1-1/d})$ time, and stabbing reporting queries in $O(n^{1-1/d}+k)$ time. Previous data structures had extra $\log^d n$ factors in space and query time. $\bullet$ For a set of $n$ (possibly intersecting) line segments in 2D, we give a data structure with $O(n)$ space that can answer ray shooting queries in $O(\sqrt{n})$ time. This improves Wang's recent data structure [SoCG'20] with $O(n\log n)$ space and $O(\sqrt{n}\log n)$ query time., Comment: Updated abstract metadata formatting. Accepted in SODA'23

Motivated by a cycling infrastructure planning application, we present a machine learning approach to solving bilevel programs with a large number of independent followers, which as a special case includes two-stage stochastic programming. We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. Unlike existing approaches, we embed machine learning model training into the optimization problem, which allows us to employ follower features that cannot be represented using leader decisions. We prove bounds on the optimality gap of the generated leader decision as measured by the original objective that considers the full follower set. We develop follower sampling algorithms to tighten the bounds and a representation learning approach to learn follower features, which are used as inputs to our machine learning model. Through numerical studies, we show that our approach generates leader decisions of higher quality compared to baselines. Finally, we perform a real-world case study in Toronto, Canada, where we solve a cycling network design problem with over one million followers. Compared to the current practice, our approach improves a transportation metric by 19.2% and can lead to a potential cost saving of $18M.

Bubble-particle collisions in turbulence are central to a variety of processes such as froth flotation. Despite their importance, details of the collision process have not received much attention yet. This is compounded by the sometimes counter-intuitive behaviour of bubbles and particles in turbulence, as exemplified by the fact that they segregate in space. Although bubble-particle relative behaviour is fundamentally different from that of identical particles, the existing theoretical models are nearly all extensions of theories for particle-particle collisions in turbulence. The adequacy of these theories has yet to be assessed as appropriate data remain scarce to date. In this investigation, we study the geometric collision rate by means of direct numerical simulations of bubble-particle collisions in homogeneous isotropic turbulence using the point-particle approach over a range of the relevant parameters, including the Stokes and Reynolds numbers. We analyse the spatial distribution of bubble and particles, and quantify to what extent their segregation reduces the collision rate. This effect is countered by increased approach velocities for bubble-particle compared to monodisperse pairs, which we relate to the difference in how bubbles and particles respond to fluid accelerations. We found that in the investigated parameter range, these collision statistics are not altered significantly by the inclusion of a lift force or different drag parametrisations, or when assuming infinite particle density. Furthermore, we critically examine existing models and discuss inconsistencies therein that contribute to the discrepancy., Comment: 29 pages, 18 figures to be published in Journal of Fluid Mechanics

The wide use of surgical masks has been proven effective for mitigating the spread of respiration diseases, such as COVID-19, alongside social distance control, vaccines, and other efforts. With the newly reported variants, such as Delta and Omicron, a higher spread rate had been found compared to the initial strains. People might get infected even by inhaling fewer loading of viruses. More frequent sterilization of surgical masks is needed to protect the wearers. However, it is challenging to sterilize the commodity surgical masks with a fast and effective method. Herein, we reported the sterilization of the SARS-CoV-2 viruses within an ultra-short time, while retaining the mask performance. Silver thin film is coated on commercial polyimide film by physical vapor deposition and patterned by laser scribing to form a Joule heating electrode. Another layer of the gold thin film was coated onto the opposite side of the device to promote the uniformity of the Joule heating through nano-heat transfer regulation. As a result, the surgical mask can be heated to inactivation temperature within a short time and with high uniformity. By Joule-heating the surgical mask with the temperature at 90 {\deg}C for 3 minutes, the inactivation of the SARS-CoV-2 showed an efficacy of 99.89%. Normal commodity surgical masks can be sterilized faster, more frequently, and efficiently against SARS-CoV-2 viruses and the new invariants.

This paper presents a landmark study of equity, diversity and inclusion (EDI) in the field of sports analytics. We developed a survey that examined personal and job-related demographics, as well as individual perceptions and experiences about EDI in the workplace. We sent the survey to individuals in the five major North American professional leagues, representatives from the Olympic and Paralympic Committees in Canada and the U.S., the NCAA Division I programs, companies in sports tech/analytics, and university research groups. Our findings indicate the presence of a clear dominant group in sports analytics identifying as: young (72.0%), White (69.5%), heterosexual (89.7%) and male (82.0%). Within professional sports, males in management positions earned roughly 30,000 USD (27%) more on average compared to females. A smaller but equally alarming pay gap of 17,000 USD (14%) was found between White and non-White management personnel. Of concern, females were nearly five times as likely to experience discrimination and twice as likely to have considered leaving their job due to isolation or feeling unwelcome. While they had similar levels of agreement regarding fair processes for rewards and compensation, females "strongly agreed" less often than males regarding equitable support, equitable workload, having a voice, and being taken seriously. Over one third (36.3%) of females indicated that they "strongly agreed" that they must work harder than others to be valued equally, compared to 9.8% of males. We conclude the paper with concrete recommendations that could be considered to create a more equitable, diverse and inclusive environment for individuals working within the sports analytics sector.