Search

Background: No previous study has comprehensively reviewed the application of machine learning algorithms in mood disorders populations. Herein, we qualitatively and quantitatively evaluate previous studies of machine learning-devised models that predict therapeutic outcomes in mood disorders populations., Methods: We searched Ovid MEDLINE/PubMed from inception to February 8, 2018 for relevant studies that included adults with bipolar or unipolar depression; assessed therapeutic outcomes with a pharmacological, neuromodulatory, or manual-based psychotherapeutic intervention for depression; applied a machine learning algorithm; and reported predictors of therapeutic response. A random-effects meta-analysis of proportions and meta-regression analyses were conducted., Results: We identified 639 records: 75 full-text publications were assessed for eligibility; 26 studies (n=17,499) and 20 studies (n=6325) were included in qualitative and quantitative review, respectively. Classification algorithms were able to predict therapeutic outcomes with an overall accuracy of 0.82 (95% confidence interval [CI] of [0.77, 0.87]). Pooled estimates of classification accuracy were significantly greater (p < 0.01) in models informed by multiple data types (e.g., composite of phenomenological patient features and neuroimaging or peripheral gene expression data; pooled proportion [95% CI] = 0.93[0.86, 0.97]) when compared to models with lower-dimension data types (pooledproportion=0.68[0.62,0.74]to0.85[0.81,0.88])., Limitations: Most studies were retrospective; differences in machine learning algorithms and their implementation (e.g., cross-validation, hyperparameter tuning); cannot infer importance of individual variables fed into learning algorithm., Conclusions: Machine learning algorithms provide a powerful conceptual and analytic framework capable of integrating multiple data types and sources. An integrative approach may more effectively model neurobiological components as functional modules of pathophysiology embedded within the complex, social dynamics that influence the phenomenology of mental disorders., (Copyright © 2018. Published by Elsevier B.V.)

Combining adaptive and robust optimization in radiation therapy has the potential to mitigate the negative effects of both intrafraction and interfraction uncertainty over a fractionated treatment course. A previously developed adaptive and robust radiation therapy (ARRT) method for lung cancer was demonstrated to be effective when the sequence of breathing patterns was well-behaved. In this paper, we examine the applicability of the ARRT method to less well-behaved breathing patterns. We develop a novel method to generate sequences of probability mass functions that represent different types of drift in the underlying breathing pattern. Computational results derived from applying the ARRT method to these sequences demonstrate that the ARRT method is effective for a much broader class of breathing patterns than previously demonstrated.

The purpose of this work was to determine whether 2 different types of linear accelerators manufacturers with similar MLC leaf widths deliver equivalent IMRT distributions for head and neck radiotherapy patients. In this study, plans delivered with Siemens linacs were re-optimized with an Elekta linac and vice versa. To test for significance, paired t-tests were computed to examine differences in target and normal tissue doses and monitor units. Dose distributions, dose-volume histograms, and dose to targets and normal tissues were found to be equivalent irrespective of the linac type. However, approximately 15% more monitor units were delivered when planned on the Elekta machine (p < 0.002). Both linear accelerators provide plans of comparable dosimetric quality; however, Elekta machines deliver slightly more monitor units than Siemens machines. This increase is likely due differences in geometric properties of the machine head designs, as modeled in the treatment planning system., (Copyright © 2011 American Association of Medical Dosimetrists. Published by Elsevier Inc. All rights reserved.)

Treatment plans optimized for intensity modulated proton therapy (IMPT) may be sensitive to range variations. The dose distribution may deteriorate substantially when the actual range of a pencil beam does not match the assumed range. We present two treatment planning concepts for IMPT which incorporate range uncertainties into the optimization. The first method is a probabilistic approach. The range of a pencil beam is assumed to be a random variable, which makes the delivered dose and the value of the objective function a random variable too. We then propose to optimize the expectation value of the objective function. The second approach is a robust formulation that applies methods developed in the field of robust linear programming. This approach optimizes the worst case dose distribution that may occur, assuming that the ranges of the pencil beams may vary within some interval. Both methods yield treatment plans that are considerably less sensitive to range variations compared to conventional treatment plans optimized without accounting for range uncertainties. In addition, both approaches--although conceptually different--yield very similar results on a qualitative level.

Managing uncertainty is a major challenge in radiation therapy treatment planning, including uncertainty induced by intrafraction motion, which is particularly important for tumours in the thorax and abdomen. Common methods to account for motion are to introduce a margin or to convolve the static dose distribution with a motion probability density function. Unlike previous work in this area, our development does not assume that the patient breathes according to a fixed distribution, nor is the patient required to breathe the same way throughout the treatment. Despite this generality, we create a robust optimization framework starting from the convolution method that is robust to fluctuations in breathing motion, yet spares healthy tissue better than a margin solution. We describe how to generate the data for our model using breathing motion data and we test our model on a computer phantom using data from real patients. In our numerical results, the robust solution delivers approximately 38% less dose to the healthy tissue than the margin solution, while providing the same level of protection against breathing uncertainty.

We consider adaptive robust methods for lung cancer that are also dose-reactive, wherein the treatment is modified after each treatment session to account for the dose delivered in prior treatment sessions. Such methods are of interest because they potentially allow for errors in the delivered dose to be corrected as the treatment progresses, thereby ensuring that the tumor receives a sufficient dose at the end of the treatment. We show through a computational study with real lung cancer patient data that while dose reaction is beneficial with respect to the final dose distribution, it may lead to exaggerated daily underdose and overdose relative to non-reactive methods that grows as the treatment progresses. However, by combining dose reaction with a mechanism for updating an estimate of the uncertainty, the magnitude of this growth can be mitigated substantially. The key finding of this paper is that reacting to dose errors - an adaptation strategy that is both simple and intuitively appealing - may backfire and lead to treatments that are clinically unacceptable.

We revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst n given points in d dimensions. Previously, the best algorithms known have running time O (n log 2 n) for d = 2 (Aggarwal and Suri 1987) and near n d for d ≥ 3 . We describe faster algorithms with the following running times (where ε > 0 is an arbitrarily small constant and O ~ hides polylogarithmic factors): n 2 O (log ∗ n) log n for d = 2 , O (n 2.5 + ε) for d = 3 , and O ~ (n (5 d + 2) / 6) for any constant d ≥ 4 . To obtain the higher-dimensional result, we adapt and extend previous techniques for Klee's measure problem to optimize certain objective functions over the complement of a union of orthants. [ABSTRACT FROM AUTHOR]

Inverse optimization—determining parameters of an optimization problem that render a given solution optimal—has received increasing attention in recent years. Although significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision making. In this paper, we present a new set of theoretical insights and algorithms for the general class of inverse mixed integer linear optimization problems. Specifically, a general characterization of optimality conditions is established and leveraged to design new cutting plane solution algorithms. Through an extensive set of computational experiments, we show that our methods provide substantial improvements over existing methods in solving the largest and most difficult instances to date. [ABSTRACT FROM AUTHOR]

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry Δ are solvable in time g(d,Δ)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual treedepth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*, Δ) poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width. [ABSTRACT FROM AUTHOR]

Given a set of n integer-valued coin types and a target value t , the well-known change-making problem asks for the minimum number of coins that sum to t , assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j , for every j = 0 , ... , t. We obtain a number of new results on these problems, including (i) an algorithm for the all-targets problem with running time O ˜ (t 4 / 3) (improving a previous O ˜ (t 3 / 2) -time algorithm), (ii) a very simple O ˜ (u 2 + t) -time algorithm for the all-targets problem, where u denotes the maximum coin value, and (iii) an algorithm for the original (single-target) problem with running time O ˜ (u) (improving a previous O ˜ (t) -time algorithm by Chan and He (SOSA'20)). We also describe applications to the (single-capacity) unbounded knapsack problem and the minimum word break problem. [ABSTRACT FROM AUTHOR]

Given a set of n points in the plane, and a parameter k , we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing k points. We present the first near quadratic time algorithm for this problem, improving over the previous near- O (n 5 / 2) -time algorithm by Kaplan et al. (25th European Symposium on Algorithms. Leibniz Int Proc Inform, vol. 87, # 52. Leibniz-Zent Inform, Wadern, 2017). We provide an almost matching conditional lower bound, under the assumption that (min , +) -convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for both perimeter and area) that can make the time bound sensitive to k , giving near O (n k) time. We also present a near linear time (1 + ε) -approximation algorithm to the minimum area of the optimal rectangle containing k points. In addition, we study related problems including the 3-sided, arbitrarily oriented, weighted, and subset sum versions of the problem. [ABSTRACT FROM AUTHOR]

We show how to solve all-pairs shortest paths on n nodes in deterministic n³/2Ω(√log n) time, and how to count the pairs of orthogonal vectors among n 0-1 vectors in d = c logn dimensions in deterministic n2−1/O (log c ) time. These running times essentially match the best known randomized algorithms of Williams [46] and Abboud, Williams, and Yu [8], respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k-satisfiability (k-SAT) assignments on n variable formulas in 2n−n/O (k) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam [24]. A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials. [ABSTRACT FROM AUTHOR]

For any constant d and parameter ε ∈(0, 1/2], we show the existence of (roughly) 1/ εd orderings on the unit cube [0, 1)d such that for any two points p, q ∈ [0, 1)d close together under the Euclidean metric, there is a linear ordering in which all points between p and q in the ordering are ``close"" to p or q. More precisely, the only points that could lie between p and q in the ordering are points with Euclidean distance at most ε ||p - q|| from either p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in lowdimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search. [ABSTRACT FROM AUTHOR]

We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O(log³ n) expected amortized time, deletions take O(log6 n) expected amortized time, and extreme-point queries take O(log² n) worst-case time. This is the first method that guarantees polylogarithmic update and query cost for arbitrary sequences of insertions and deletions, and improves the previous O(nϵ)-time method by Agarwal and Matoušek a decade ago. As a consequence, we obtain similar results for nearest neighbor queries in two dimensions and improved results for numerous fundamental geometric problems (such as levels in three dimensions and dynamic Euclidean minimum spanning trees in the plane). [ABSTRACT FROM AUTHOR]

Given a set of n moving points in R d , where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O ˜ ( n 5 / 3 ) -time algorithm 1 to compute a ( 1 + ϵ ) -factor approximation to the minimum closest pair distance over time, for any constant ϵ > 0 and any constant dimension d . This addresses an open problem posed by Gupta, Janardan, and Smid [1] . More generally, we consider a data structure version of the problem: for any linearly moving query point q , we want a ( 1 + ϵ ) -factor approximation to the minimum nearest neighbor distance to q over time. We present a data structure that requires O ˜ ( n 5 / 3 ) space and O ˜ ( n 2 / 3 ) query time, O ˜ ( n 5 ) space and polylogarithmic query time, or O ˜ ( n ) space and O ˜ ( n 4 / 5 ) query time, for any constant ϵ > 0 and any constant dimension d . 1 The notation O ˜ is used to hide polylogarithmic factors. That is, O ˜ ( f ( n ) ) = O ( f ( n ) log c ⁡ n ) , where c is a constant. [ABSTRACT FROM AUTHOR]

Chazelle [SIAM J Comput 21(4):671-696, 1992] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same. [ABSTRACT FROM AUTHOR]

Starting with Munro and Paterson (1980) [13] , the selection or median-finding problem has been extensively studied in the read-only memory model and in streaming models. Munro and Paterson's deterministic algorithm and its subsequent refinements require at least polylogarithmic or logarithmic space, whereas the algorithms by Munro and Raman (1996) [14] and Raman and Ramnath (1999) [15] can be made to use just O ( 1 ) storage cells but take O ( n 1 + ε ) time for an arbitrarily small constant ε > 0 . In this paper, we initiate the first study on this problem when the input is a sequence of integers. We show that faster selection algorithms in read-only memory are possible if the input is a sequence of integers. For example, one of our algorithms uses O ( 1 ) storage cells and takes O ( n lg ⁡ U ) 1 time where U is the universe size. Another algorithm uses O ( 1 ) storage cells and takes O ( n lg ⁡ n lg ⁡ lg ⁡ U ) time. A combination of the two yields an algorithm that uses O ( 1 ) words of space and takes O ( n lg 1 + ϵ ⁡ n ) time, a bound independent of U . We also describe an O ( n ) -time algorithm for finding an approximate median using O ( lg ε ⁡ U ) storage cells. All our algorithms are simple and deterministic. Interestingly, one of our algorithms is inspired by ‘centroids’ of binary trees and finds an approximate median by repeatedly invoking a textbook algorithm for the ‘majority’ problem. This technique could be of independent interest. [ABSTRACT FROM AUTHOR]

Many standard problems in computational geometry have been solved asymptotically optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this paper, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, including Some of the results can be adapted to solve nonorthogonal problems, such as 2D convex hulls and general line segment intersection. Our algorithms and data structures use a variety of techniques, including Seidel and Adamy's planar point location method, weighted binary search, and height-optimal BSP trees. [ABSTRACT FROM AUTHOR]

A mode of a multiset S is an element a∈ S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1: n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices ( i, j) for which a mode of A[ i: j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pp. 517-526, ), requires $\varTheta (\sqrt{n}\log\log n)$ query time in the worst case. We improve their result and present an O( n)-space data structure that supports range mode queries in $O(\sqrt{n/\log n})$ worst-case time. In the external memory model, we give a linear-space data structure that requires $O(\sqrt{n/B})$ I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below $\sqrt{n}$ cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two $\sqrt{n} \times \sqrt{n}$ matrices reduces to n range mode queries in an array of size O( n). Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O( n) time), for orthogonal range mode in d dimensions (queries in near O( n) time) and for half-space range mode in d dimensions (queries in $O(n^{1-1/d^{2}})$ time). Finally, we complement our dynamic data structure with a reduction from the multiphase problem, again supporting that we cannot hope for much more efficient data structures. [ABSTRACT FROM AUTHOR]

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the ℓ norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p even, and p=∞. For p even, we reduce the problem to standard convolution, while for p=∞ and p=1, we reduce the problem to (min,+) convolution and $(\operatorname {median},+)$ convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X+ Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X+ Y matrix. All of our algorithms run in o( n) time, whereas the obvious algorithms for these problems run in Θ( n) time. [ABSTRACT FROM AUTHOR]

Abstract: At SODAʼ10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses space, and was shown to have approximation factor at most . We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an -space data structure that can maintain a 1.22-approximate minimum enclosing ball in expected amortized time per insertion/deletion. [Copyright &y& Elsevier]

Abstract: We study several geometric set cover and set packing problems involving configurations of points and geometric objects in Euclidean space. We show that it is APX-hard to compute a minimum cover of a set of points in the plane by a family of axis-aligned fat rectangles, even when each rectangle is an ϵ-perturbed copy of a single unit square. We extend this result to several other classes of objects including almost-circular ellipses, axis-aligned slabs, downward shadows of line segments, downward shadows of graphs of cubic functions, fat semi-infinite wedges, 3-dimensional unit balls, and axis-aligned cubes, as well as some related hitting set problems. We also prove the APX-hardness of a related family of discrete set packing problems. Our hardness results are all proven by encoding a highly structured minimum vertex cover problem which we believe may be of independent interest. In contrast, we give a polynomial-time dynamic programming algorithm for geometric set cover where the objects are pseudodisks containing the origin or are downward shadows of pairwise 2-intersecting x-monotone curves. Our algorithm extends to the weighted case where a minimum-cost cover is required. We give similar algorithms for several related hitting set and discrete packing problems. [Copyright &y& Elsevier]

We show that finding the simplices containing a fixed given point among those defined on a set of n points can be done in O(n + k) time for the two-dimensional case, and in O(n2 + k) time for the three-dimensional case, where k is the number of these simplices. As a byproduct, we give an alternative (to the algorithm in Ref. 4) O(n log r) algorithm that finds the red-blue boundary for n bichromatic points on the line, where r is the size of this boundary. Another byproduct is an O(n2 + t) algorithm that finds the intersections of line segments having two red endpoints with those having two blue endpoints defined on a set of n bichromatic points in the plane, where t is the number of these intersections. [ABSTRACT FROM AUTHOR]

In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line ℓ such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line ℓ is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of ℓ is fixed, we give an O(n2log2 n)-time algorithm. When ℓ is an arbitrary line, we give a randomized algorithm with expected running time O(n4log2 n). Then we present (1+ε)-approximation algorithms for these three problems. When we denote T(k, ε) = (k/ε2+(k/ε) log k) log(1/ε), these algorithms run in O(n log k + T(k, ε)) time, O(n log k + T(k, ε)/ε) time, and O(n log k + T(k, ε)/ε2) time, respectively. For k = O(n1/3/log n), we also give randomized algorithms with expected running times O(n + (k/ε2) log(1/ε)), O(n+(k/ε3) log(1/ε)), and O(n + (k/ε4) log(1/ε)), respectively. [ABSTRACT FROM AUTHOR]

Abstract: We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in expected time using only extra space; this improves the previous bound by Brönnimann, Chan, and Chen (2004) . The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with expected running time for output size K, improving the previous bound by Vahrenhold (2007) . As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, Mølhave, and Zeh (2008) . Our results are all obtained by standard random sampling techniques, with some interesting twists. [Copyright &y& Elsevier]

We study a bichromatic version of the well-known k-set problem: given two sets R and B of points of total size n and an integer k, how many subsets of the form (R ∩h)∪(B \h) can have size exactly k over all halfspaces h? In the dual, the problem is asymptotically equivalent to determining the worst-case combinatorial complexity of the k-level in an arrangement of n halfspaces. Disproving an earlier conjecture by Linhart [1993], we present the first nontrivial upper bound for all k ⪡ n in two dimensions: O(nk1/3 +n5/6-ϵk2/3+2ϵ +k²) for any fixed ϵ > 0. In three dimensions, we obtain the bound O(nk3/2 +n0.5034k2.4932 +k³). Incidentally, this also implies a new upper bound for the original k-set problem in four dimensions: O(n²k3/2 + n1.5034k2.4932 + nk³), which improves the best previous result for all k ⪡ n0.923. Extensions to other cases, such as arrangements of disks, are also discussed. [ABSTRACT FROM AUTHOR]

Abstract: Given n axis-parallel boxes in a fixed dimension , how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee''s measure problem, can be solved in time by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time , where denotes the iterated logarithm. For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near , ignoring factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple. [Copyright &y& Elsevier]

We establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω(n log logS n) expected time in the RAM model (or more generally in the comparison branching program model), if we have S bits of extra space besides the read-only input array. This bound is tight for all S ⪢ log n, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman [1996], and also complements recent lower bounds that are restricted to sequential access, as in the multipass streaming model [Chakrabarti et al. 2008b]. We also prove that any comparison-based, deterministic, multipass streaming algorithm for finding the median requires Ω(n log*(n/s) + n logs n) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s ⪢ log2 n. We get deterministic lower bounds for I/O-efficient algorithms as well. The proofs in this article are self-contained and do not rely on communication complexity techniques. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n3 log3 log n/ log2 n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-ω)/(2d+4)), where ω < 2.376; in two dimensions, this is O(n2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n3-(3-ω)/4) = O(n2.844) time) for APSP in real- vertex-weighted graphs, as well as an improved result (near O(n(3+ω)/2) = O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions. [ABSTRACT FROM AUTHOR]

We give a dynamic data structure that can maintain an ε-coreset of n points, with respect to the extent measure, in O(log n) time per update for any constant ε>0 and any constant dimension. The previous method by Agarwal, Har-Peled, and Varadarajan requires polylogarithmic update time. For points with integer coordinates bounded by U, we alternatively get O(log log U) time. Numerous applications follow, for example, on dynamically approximating the width, smallest enclosing cylinder, minimum bounding box, or minimum-width annulus. We can also use the same approach to maintain approximate k-centers in time O(log n) (or O(log log U) if the spread is bounded by U) for any constant k and any constant dimension. For the smallest enclosing cylinder problem, we also show that a constant-factor approximation can be maintained in O(1) randomized amortized time on the word RAM. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n³ log³ log n/ log² n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-ω)/(2d+4)), where logω < 2.376; in two dimensions, this is O(n2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n3-(3-logω)/4) = O(n2.844) time) for APSP in real- vertex-weighted graphs, as well as an improved result (near O(n(3+logω)/2) = O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs. [ABSTRACT FROM AUTHOR]

Given a planar subdivision whose coordinates are integers bounded by U ⩽ 2w, we present a linear-space data structure that can answer point-location queries in O(min{lg n/ lg lg n, √lg U/ lg lgU}) time on the unit-cost random access machine (RAM) with word size w. This is the first result to beat the standard Θ(lg n) bound for infinite precision models. As a consequence, we obtain the first o(n lg n) (randomized) algorithms for many fundamental problems in computational geometry for arbitrary integer input on the word RAM, including: constructing the convex hull of a three-dimensional (3D) point set, computing the Voronoi diagram or the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. Higher-dimensional extensions and applications are also discussed. Though computational geometry with bounded precision input has been investigated for a long time, improvements have been limited largely to problems of an orthogonal flavor. Our results surpass this long-standing limitation, answering, for example, a question of Willard (SODA'92). [ABSTRACT FROM AUTHOR]

We improve the previous results by Aronov and Har-Peled (SODA’05) and Kaplan and Sharir (SODA’06) and present a randomized data structure of O( n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions. [ABSTRACT FROM AUTHOR]

Abstract: We speed up previous -factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width enclosing annulus, minimum-width enclosing cylindrical shell, etc. Linear time bounds were known before; we further improve the dependence of the “constants” in terms of ε. We next consider the data-stream model and present new -factor approximation algorithms that need only constant space for all of the above problems in any fixed dimension. Previously, such a result was known only for diameter. Both sets of results are obtained using the core-set framework recently proposed by Agarwal, Har-Peled, and Varadarajan. [Copyright &y& Elsevier]

We study the problem of maintaining a (1 + ∊)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, we give a simple algorithm that only needs to store $O({\frac{1}{\epsilon}}\,{\rm log}\,R)$ points at any time, where the parameter R denotes the "spread" of the point set. This bound is optimal and improves Feigenbaum, Kannan, and Zhang's recent solution by two logarithmic factors. We then extend our one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, we also observe a constant-factor approximation algorithm that requires sublinear space. Related optimization problems, such as the width, are also considered in the two-dimensional case. [ABSTRACT FROM AUTHOR]

Abstract: We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as in-place stable partition, i.e., if there were a truly simple solution then in-place stable partition would also have a truly simple solution, and vice versa. Nevertheless, we present a simple self-contained solution that uses space, and indicate how to improve it to space with the same techniques used for stable partition. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, the problem admits a very simple solution which does not call for stable partitioning at all. [Copyright &y& Elsevier]

Abstract: In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex are as evenly distributed to the left and right of as possible. This problem, which has applications in graph drawing for example, is shown to be -hard, and remains -hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs, trees, and graphs with maximum degree three. For undirected graphs, we obtain a 13/8-approximation algorithm. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be -hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size. [Copyright &y& Elsevier]

We study (l+ε)-factor approximation algorithms for several well-known optimization problems on a given n-point set: (a) diameter, (b) width, (c) smallest enclosing cylinder, and (d) minimum-width annulus. Among our results are new simple algorithms for (a) and (c) with an improved dependence of the running time on ε, as well as the first lineartime approximation algorithm for (d) in any fixed dimension. All four problems can be solved within a time bound of the form O(n + ε[sup -c]) or O(n log(1/ε) + ε[sup -c]). [ABSTRACT FROM AUTHOR]

Given an n-point set, the problems of enumerating the k closest pairs and selecting the k-th smallest distance are revisited. For the enumeration problem, we give simpler randomized and deterministic algorithms with O(n log n + k) running time in any fixed-dimensional Euclidean space. For the selection problem, we give a randomized algorithm with running time O(n log n+n[sup 2/3]k[sup 1/3] log[sup 5/3] n) in the Euclidean plane. We also describe output-sensitive results for half-space range counting that are of use in more general distance selection problems. None of our algorithms requires parametric search. [ABSTRACT FROM AUTHOR]

Noun phrases are commonly used for generating index terms for information retrieval systems. Therefore, -we need an effective noun phrase extraction method. In this paper, we propose an approach to extract maximal noun phrases from Chinese text. Although previous studies have been proposed to extract noun phrases, most of them are only applicable to Western languages. To the best of our knowledge, very few has handled Chinese text. Many existing approaches for Western languages made use of statistical methods. However, due to the complicated structure of maximal Chinese noun phrase, pure statistical approaches are not effective. We attempt to improve the performance of a statistical method by integrating it with the transformation-based error-driven learning (TEL) technique. Our methodology includes two modules. The first module applies a statistical method to extract Chinese noun phrases. The performance of this approach, in terms of precision and recall, is investigated. The second module applies the TEL algorithm to further refine the output of the first module. The TEL algorithm automatically learns a set of transformation rules to fix the errors that are obtained through comparing the output of the first module with the correctly annotated corpus. The learned rules can be applied to sentences in any corpus one by one to correct the errors. The TEL algorithm is shown to be effective in improving the precision. [ABSTRACT FROM AUTHOR]

Given n points in three dimensions, we show how to answer halfspace range reporting queries in O(log n + k) expected time for an output size k. Our data structure can be preprocessed in optimal O(n log n) expected time. We apply this result to obtain the first optimal randomized algorithm for the construction of the (≤k)-level in an arrangement of n planes in three dimensions. The algorithm runs in O(n log n+nk[SUP2]) expected time. Our techniques are based on random sampling. Applications in two dimensions include an improved data structure for "k nearest neighbors" queries and an algorithm that constructs the order-k Voronoi diagram in O(n log n+nk log k) expected time. [ABSTRACT FROM AUTHOR]

The article focuses on waste in health care spending in the U.S. have reached a threshold of one trillion dollars equivalent to the gross domestic product of the 17th largest economy in the world. Topics inlcude the major contributors to wasteful spending span failures of care delivery, and redundancies, determining the factors that drive wasteful spending is a complex problem, and the decisions made by health authorities and legislators at the regional or national systems-level.

Hearing loss is the leading human sensory system loss, and one of the leading causes for years lived with disability with significant effects on quality of life, social isolation, and overall health. Coupled with a forecast of increased hearing loss burden worldwide, national and international health organizations have urgently recommended that access to hearing evaluation be expanded to meet demand. The objective of this study was to develop 'AutoAudio' – a novel deep learning proof-of-concept model that accurately and quickly interprets diagnostic audiograms. Adult audiogram reports representing normal, conductive, mixed and sensorineural morphologies were used to train different neural network architectures. Image augmentation techniques were used to increase the training image set size. Classification accuracy on a separate test set was used to assess model performance. The architecture with the highest out-of-training set accuracy was ResNet-101 at 97.5%. Neural network training time varied between 2 to 7 h depending on the depth of the neural network architecture. Each neural network architecture produced misclassifications that arose from failures of the model to correctly label the audiogram with the appropriate hearing loss type. The most commonly misclassified hearing loss type were mixed losses. Re-engineering the process of hearing testing with a machine learning innovation may help enhance access to the growing worldwide population that is expected to require audiologist services. Our results suggest that deep learning may be a transformative technology that enables automatic and accurate audiogram interpretation. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editors discuss various articles within the issue on topics including counting of minimum cuts in weighted directed graphs with a quadratic time algorithm, an algorithm to design motorcycle graphs and a novel output-sensitive algorithm for Voronoi diagrams.