Search

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s \geq 1, both problems are polynomial-time solvable for sP3-free graphs and (sP1 + P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1 + P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., Theoret. Comput. Sci., 705 (2018), pp. 75--83], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica, 82 (2020), pp. 2841--2866] and P5-free graphs [Abrishami et al., Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 1948--1964]. Together, the new results also show that both problems exhibit the same behavior on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1 + P5)-free graph G a largest induced subgraph whose blocks belong to some finite class \scrC of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs. [ABSTRACT FROM AUTHOR]

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(√ k) instead of O(k) (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number k = |T| of terminals is regarded as the parameter. We show that Subset TSP can be solved in time 2O(√k log k) · nO(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014, SIAM, Philadelphia, 2014, pp. 1812-1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. [ABSTRACT FROM AUTHOR]

We introduce a new algorithm, improved from the Armijo line search one [M.V. Solodov and B.F. Svaiter, A new projection method for monotone variational inequality problems, SIAM J. Control Optim. 37 (1999), pp. 765–776]. Our algorithm converges under the same assumption but does not use the line search procedure in its steps. Our numerical experiments show that the new algorithm is more effective than some existing ones. [ABSTRACT FROM AUTHOR]

Based on the spectral divide‐and‐conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325–A1349, 2013], we propose a new algorithm for computing all the eigenvalues and eigenvectors of a symmetric banded matrix with small bandwidth, with the eigenvectors given implicitly as a product of orthonormal matrices stored in the so‐called hierarchically off‐diagonal low‐rank (HODLR) format. For this purpose, we combine our previous work on the fast computation of spectral projectors in the HODLR format, with a novel technique for extracting a basis for the range of such a HODLR matrix. Preliminary numerical experiments demonstrate that our algorithm exhibits quasi‐linear complexity for matrices that can be efficiently represented in the HODLR format throughout the divide‐and‐conquer algorithm, and allows for conveniently dealing with such large‐scale matrices. [ABSTRACT FROM AUTHOR]

The l parameterized generalized eigenvalue problems for the nonsquare matrix pencils, proposed by Chu and Golub [SIAM J. Matrix Anal. Appl., 28(2006), pp. 770‐787], can be formulated as an optimization problem on a corresponding complex product Stiefel manifold. Some early proposed algorithms are based on the first‐order information of the objective function, and fast convergence could not be expected. In this article, we turn the generic Riemannian trust‐region method of Absil et al. into a practical algorithm for solving the underlying problem, which enjoys the global convergence and local superlinear convergence rate. Numerical experiments are provided to illustrate the efficiency of the proposed method. Detailed comparisons with some existing results (l = 1 and l = n) are given first. For the case l = n, the algorithm can yield exactly the same optimal solution as Ito and Murota's algorithm, which is essentially a direct method to solve the problem. The algorithm runs faster than Boutry et al.'s algorithm for the case l = 1. Further comparisons with some early proposed gradient‐based algorithms, and some latest infeasible methods for solving manifold optimization problems are also provided to show the merits of the proposed approach. [ABSTRACT FROM AUTHOR]

Despite many applications of computer vision for agricultural harvesting robots that focus on fruit detection, some agricultural applications are not well-developed, especially for natural rubber latex production. Tapping is a method to harvest rubber latex from the natural rubber trees (Hevea brasiliensis) which involves operating at night in Southern Thailand. This article presents a near range machine vision for the rubber tapping automation that detects the tapping line in the near-range images. Our acquisition tool integrates an RGB-D camera with assisting lights for capturing images under low light conditions. Our tapping line detection algorithm extracts the tapping path shadow regions by the image differencing with connected component labeling algorithm of two grayscale images from different lighting directions. We adopted the sub-array searching technique to detect the tapping line that agreed to the downward tapping system. Detection accuracy archived the highest at 90.1% using the intersection over union ratio of 0.5 evaluation criteria between the pre-defined ground truth and the detected bounding boxes. Distance errors of the detected tapping lines are also measured using the average discrete Hausdorff Distance. Our algorithm produces an error distance of 13 pixels or 5.5-7.8 millimeters by the camera working-geometry. Our techniques feasibly support the generation of a 3D tapping path in further development. [ABSTRACT FROM AUTHOR]

We extend the Mobile Server problem introduced in Feldkord and Meyer auf der Heide (TOPC 6(3), 14:1–14:17 2019) to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. To reduce communication costs, the positions of the servers can be adapted by a limited distance ms per round for each server. The costs are measured similarly to the classical Page Migration problem: i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D. We show that, in our model, no online algorithm can have a constant competitive ratio: i.e., one which is independent of the input length n, even if an augmented moving distance of (1 + δ)ms is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests: i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant mc. We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, ms and mc). On the positive side, we present a deterministic online algorithm with bounded competitiveness when an augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between mc and ms, the inverse of the augmentation factor 1/δ and the competitive ratio of the simulated k-Page Migration algorithm. We also show how to directly adapt the Double Coverage algorithm (Chrobak et al. SIAM J. Discrete Math. 4(2), 172–181 11) for the k-Server problem to receive an algorithm with improved competitiveness on the line. [ABSTRACT FROM AUTHOR]

Computing a flow system a number of times with different samples of flow parameters is a common practice in many uncertainty quantification applications, which can be prohibitively expensive for complex nonlinear flow problems. This report presents two second order, stabilized, scalar auxiliary variable (SAV) ensemble algorithms for fast computation of the Navier--Stokes flow ensembles: Stab-SAV-CN and Stab-SAV-BDF2. The proposed ensemble algorithms are based on the ensemble timestepping idea which makes use of a quantity called the ensemble mean to construct a common coefficient matrix for all realizations at the same time step after spatial discretization, in which case efficient block solvers, e.g., block GMRES, can be used to significantly reduce both storage and computational time. The adoption of a recently developed SAV approach that treats the nonlinear term explicitly results in a constant shared coefficient matrix among all realizations at different time steps, which further cuts down the computational cost, yielding an extremely efficient ensemble algorithm for simulating nonlinear flow ensembles with provable long time stability without any time step conditions. The SAV approach for the Navier--Stokes equations for a single realization was proved to be unconditionally stable in [L. Lin, Z. Yang, and S. Dong, J. Comput. Phys., 388 (2019), pp 1-22; X. Li and J. Shen, SIAM J. Numer. Anal., 58 (2020), pp. 2465-2491]. However we found the SAV approach has very low accuracy that compromises its stability in our initial numerical investigations for several commonly tested benchmark flow problems. In this report, we propose to use the stabilization in Stab-SAV-BDF2 to address this issue. We prove that both of our ensemble algorithms are long time stable under one parameter fluctuation condition, without any time step constraints. For a single realization, both algorithms are unconditionally stable and have better accuracy than the SAV methods studied in [L. Lin, Z. Yang, and S. Dong, J. Comput. Phys., 388 (2019), pp 1-22; X. Li and J. Shen, SIAM J. Numer. Anal., 58 (2020), pp. 2465-2491] for our test problems. Extensive numerical experiments are performed to show the efficiency of the proposed ensemble algorithms and the effectiveness of the stabilization for increasing accuracy and stability. [ABSTRACT FROM AUTHOR]

We present a deterministic (1+o(1))-approximation O(n1/2+o(1) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(√n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є-1logє-1)-approximation factor of Lenzen and Patt-Shamir's Õ(n1/2+є+D)-time algorithm [STOC 2013, pp. 381-390] within the same running time. (Throughout, we use Õ(.) to hide polylogarithmic factors in n.) Our running time matches the known time lower bound of Ω(√n/log n + D) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40-57]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the "hitting set argument" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (no(1), o(1))-hop set of size n1+o(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434-446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375-382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153-162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation no(1)-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation no(1)-pass n1+o(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565-573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]. [ABSTRACT FROM AUTHOR]

This work is concerned with approximating a trivariate function defined on a tensorproduct domain via function evaluations. Combining tensorized Chebyshev interpolation with a Tucker decomposition of low multilinear rank yields function approximations that can be computed and stored very efficiently. The existing Chebfun3 algorithm [B. Hashemi and L. N. Trefethen, SIAM J. Sci. Comput., 39 (2017), pp. C341--C363] uses a similar format, but the construction of the approximation proceeds indirectly, via a so-called slice-Tucker decomposition. As a consequence, Chebfun3 sometimes unnecessarily uses many function evaluations and does not fully benefit from the potential of the Tucker decomposition to reduce, sometimes dramatically, the computational cost. We propose a novel algorithm Chebfun3F that utilizes univariate fibers instead of bivariate slices to construct the Tucker decomposition. Chebfun3F reduces the cost for the approximation in terms of the number of function evaluations for nearly all functions considered, typically by 75\% and sometimes by over 98\%. [ABSTRACT FROM AUTHOR]

Generally, transportation costs account for approximately half of the total operation expenses of a logistics firm. Therefore, any effort to optimize the planning of vehicle routing would be substantially beneficial to the company. This study focuses on a postman delivery routing problem of the Chiang Rai post office, located in the Chiang Rai province of Thailand. In this study, two metaheuristic methods—particle swarm optimization (PSO) and differential evolution (DE)—were applied with particular solution representation to find delivery routings with minimum travel distances. The performances of PSO and DE were compared along with those from current practices. The results showed that PSO and DE clearly outperformed the actual routing of the current practices in all the operational days examined. Moreover, DE performances were notably superior to those of PSO. [ABSTRACT FROM AUTHOR]

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ(nb²) time so that one can compute any additively weighted Voronoi diagram for these sites in Õ (b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ(n5/3) time. This improves the recent breakthrough result of Cabello [SODA 2017, SIAM, Philadelphia, 2017, pp. 2143{2152], both by improving the running time (from Õ(n11/6)), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex v, both the farthest vertex from v (i.e., the eccentricity of v), and the sum of distances from v to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest. [ABSTRACT FROM AUTHOR]

We present recent results on the existence of a continuous time limit for Ensemble Kalman Filter algorithms. In the setting of continuous signal and observation processes, we apply the original Ensemble Kalman Filter algorithm proposed by Burgers, van Leeuwen, and Evensen [Monthly Weather Review 126 (1998), pp. 1719-1724] as well as a recent variant of de Wiljes, Reich, and Stannat [SIAM J. Appl. Dyn. Syst. 17 (2018), no. 2, pp. 1152-1181] to the respective discretizations and show that in the limit of decreasing stepsize the filter equations converge to an ensemble of interacting (stochastic) differential equations in the ensemble-mean-square sense. Our analysis also allows for the derivation of convergence rates with respect to the stepsize. An application of our analysis is the rigorous derivation of continuous-time ensemble filtering algorithms consistent with discrete-time approximation schemes. Conversely, the continuous time limit allows for a better qualitative and quantitative analysis of the discrete-time counterparts using the rich theory of dynamical systems in continuous time. [ABSTRACT FROM AUTHOR]

We study the convergence issue for the gradient algorithm (employing general step sizes) for optimization problems on general Riemannian manifolds (without curvature constraints). Under the assumption of the local convexity/quasi-convexity (resp., weak sharp minima), local/global convergence (resp., linear convergence) results are established. As an application, the linear convergence properties of the gradient algorithm employing the constant step sizes and the Armijo step sizes for finding the Riemannian Lp (p ∈ [1, + ∞)) centers of mass are explored, respectively, which in particular extend and/or improve the corresponding results in [B. Afsari, R. Tron, and R. Vidal, SIAM J. Control Optim., 51 (2013), pp. 2230-2260; G. C. Bento et al., J. Optim. Theory Appl., 183 (2019), pp. 977-992]. [ABSTRACT FROM AUTHOR]

In recent years there has been an emerging interest in PDE-like ows defined on finite graphs, with applications in clustering and image segmentation. In particular for image segmentation and semisupervised learning Bertozzi and Flenner [Multiscale Model. Simul., 10 (2012), pp. 1090{1118] developed an algorithm based on the Allen{Cahn (AC) gradient ow of a graph Ginzburg{Landau functional, and Merkurjev, Kostic, and Bertozzi [SIAM J. Imaging Sci., 6 (2013), pp. 1903{1930] devised a variant algorithm based instead on graph Merriman{Bence{Osher (MBO) dynamics. This work offers rigorous justification for this use of the MBO scheme in place of AC ow. First, we choose the double-obstacle potential for the Ginzburg{Landau functional and derive wellposedness and regularity results for the resulting graph AC ow. Next, we exhibit a \semidiscrete" time-discretization scheme for AC ow of which the MBO scheme is a special case. We investigate the long-time behavior of this scheme and prove its convergence to the AC trajectory as the time-step vanishes. Finally, following a question raised by Van Gennip, Guillen, Osting, and Bertozzi [Milan J. Math., 82 (2014), pp. 3{65], we exhibit results toward proving a link between double-obstacle AC ow and mean curvature ow on graphs. We show some promising -convergence results and translate to the graph setting two comparison principles used by Chen and Elliott [Proc. Math. Phys. Sci., 444 (1994), pp. 429{445] to prove the analogous link in the continuum. [ABSTRACT FROM AUTHOR]

Algencan is a well established safeguarded Augmented Lagrangian algorithm introduced in [R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2008), pp. 1286–1309]. Complexity results that report its worst-case behaviour in terms of iterations and evaluations of functions and derivatives that are necessary to obtain suitable stopping criteria are presented in this work. In addition, its computational performance considering all problems from the CUTEst collection is presented, which shows that it is a useful tool for solving large-scale constrained optimization problems. [ABSTRACT FROM AUTHOR]

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by Spielman and Teng [J. ACM, 51 (2004), pp. 385--463] who developed the notion of smoothed analysis. Starting from an arbitrary linear program (LP) with d variables and n constraints, Spielman and Teng analyzed the expected runtime over random perturbations of the LP, known as the smoothed LP, where variance \sigma 2 Gaussian noise is added to the LP data. In particular, they gave a two-stage shadow vertex simplex algorithm which uses an expected \widetilde O(d55n86\sigma 30 + d70n86) number of simplex pivots to solve the smoothed LP. Their analysis and runtime was substantially improved by Deshpande and Spielman [FOCS '05, 2005, pp. 349--356] and later Vershynin [SIAM J. Comput., 39 (2009), pp. 646--678]. The fastest current algorithm, due to Vershynin, solves the smoothed LP using an expected O \bigl(log2 n \cdot log log n \cdot (d3\sigma 4+d5 log2 n+d9 log4 d) \bigr) number of pivots, improving the dependence on n from polynomial to polylogarithmic. While the original proof of Spielman and Teng has now been substantially simplified, the resulting analyses are still quite long and complex and the parameter dependencies far from optimal. In this work, we make substantial progress on this front, providing an improved and simpler analysis of shadow simplex methods, where our algorithm requires an expected O(d2 \surd log n \sigma 2 + d3 log3/2 n) number of simplex pivots. We obtain our results via an improved shadow bound, key to earlier analyses as well, combined with improvements on algorithmic techniques of Vershynin. As an added bonus, our analysis is completely modular and applies to a range of perturbations, which, aside from Gaussians, also includes Laplace perturbations. [ABSTRACT FROM AUTHOR]

We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures [B. Allen and I. Munro, J. ACM, 25 (1978), pp. 526{535; D. D. Sleator and R. E. Tarjan, J. ACM, 32 (1985), pp. 652{686; M. L. Fredman et al., Algorithmica, 1 (1986), pp. 111{129; R. Wilber, SIAM J. Comput., 18 (1989), pp. 56{67; M. L. Fredman, in WAE 1999, Springer, Berlin, 1999, pp. 244{258; J. Iacono and O. Ozkan, in ICALP 2014, Springer, Berlin, 2014, pp. 637{649]. Roughly speaking, we map an arbitrary heap algorithm within a natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e., the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures. There is a rich theory of dynamic optimality for BSTs (i.e., the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature (e.g., [S. Pettie, in FOCS 2005, IEEE, Washington, DC, 2005, pp. 174{183; S. Pettie, in SODA 2008, ACM, New York, SIAM, Philadelphia, 2008, pp. 1115{1124]). Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps. On the algorithmic side, we obtain a new, simple, and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal [J. M. Lucas, Canonical Forms for Competitive Binary Search Tree Algorithms, Tech. rep. DCS-TR-250, Rutgers University, New Brunswick, NJ, 1988; J. Munro, in Algorithms|ESA 2000, Lecture Notes in Comput. Sci. 1879, Springer, Berlin, Heidelberg, 2000, pp. 338{345; E. D. Demaine et al., in SODA 2009, AMC, New York, SIAM, Philadelphia, 2009, pp. 496{505]. Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms. As corollaries of results known for Greedy, we obtain instance-specific upper bounds for the smooth heap, with applications in adaptive sorting. Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g., it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a \power-of-two-choices" type of heuristic. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for packing integer programs (PIPs) of the form max { ⟨ c , x ⟩ : A x ≤ b , x ∈ { 0 , 1 } n } where A, b and c are nonnegative. We let W = min i , j b i / A i , j denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533–565, 2012) obtained an Ω (1 Δ 0 1 / ⌊ W ⌋ ) -approximation ratio where Δ 0 is the maximum number of nonzeroes in any column of A (in other words the ℓ 0 -column sparsity of A). They raised the question of obtaining approximation ratios based on the ℓ 1 -column sparsity of A (denoted by Δ 1 ) which can be much smaller than Δ 0 . Motivated by recent work on covering integer programs (Chekuri and Quanrud, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1596–1615. SIAM, 2019; Chen et al., in: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1984–2003. SIAM, 2016) we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. (Theory Comput 8(24):533–565, 2012) (but with a twist), yield approximation ratios for PIPs based on Δ 1 . First, following an integrality gap example from (Theory Comput 8(24):533–565, 2012), we observe that the case of W = 1 is as hard as maximum independent set even when Δ 1 ≤ 2 . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width W = 1 + ϵ where ϵ ∈ (0 , 1 ] , we obtain an Ω (ϵ 2 / Δ 1) -approximation. In the large width regime, when W ≥ 2 , we obtain an Ω ((1 1 + Δ 1 / W) 1 / (W - 1)) -approximation. We also obtain a (1 - ϵ) -approximation when W = Ω (log (Δ 1 / ϵ) ϵ 2) . Viewing the rounding algorithms as contention resolution schemes, we obtain approximation algorithms in the more general setting when the objective is a non-negative submodular function. [ABSTRACT FROM AUTHOR]

We study Leja sequences on the unit disc and resulting mapped sequences to conventional domain, ellipses and real intervals, for the problem of relaxation of Richardson iteration. Using simple considerations, we establish upper and lower estimates for the growth of associated Newton polynomials and the so-called residual polynomials. These results broaden the understanding of such sequences and add to results established in Calvetti et al. (Numer. Math. 67(1), 21–40, 1994), Calvetti and Reichel (Numerical Algorithms 11(1-4), 79–98, 1996; J. Comput. Appl. Math. 71(2), 267–286 1996), Fischer and Reichel (Numer. Math. 54(2), 225–242, 1989), Nachtigal et al. (SIAM Journal on Matrix Analysis and Applications 13(3), 796–825, 1992), Reichel (SIAM J. Numer. Anal. 25(6), 1359–1368, 1988), Tal-Ezer (J. Sci. Comput. 4(1), 25–60, 1989). We also propose adaptive strategies for the selection of relaxation parameters that build on fast strategies (Balgama et al., Electron. Trans. Numer. Anal. 7, 124–140, 1998; Reichel, Linear Algebra and its Applications 154-156(C), 389–414, 1991) which are known to be suitable for the problem. In particular a Leja ordering is enforced on the mapped sequences. New strategies for conveniently confining the spectrums of certain matrices arising in PDEs discretization is described and demonstrate the flexibility of the Richardson iteration. [ABSTRACT FROM AUTHOR]

We present a uniqueness result in dimensions 3 for the inverse fixed angle scattering problem associated to the Schrödinger operator - Δ + q {-\Delta+q} , where q is a small real-valued potential with compact support in the Sobolev space W β , 2 {W^{\beta,2}} , with β > 0. {\beta>0.} This result improves the known result [P. Stefanov, Generic uniqueness for two inverse problems in potential scattering, Comm. Partial Differential Equations 17 1992, 55–68], in the sense that almost no regularity is required for the potential. The uniqueness result still holds in dimension 4, but for more regular potentials in W β , 2 {W^{\beta,2}} , with β > 2 / 3 {\beta>2/3}. The proof is a consequence of the reconstruction method presented in our previous work, [J. A. Barceló, C. Castro, T. Luque and M. C. Vilela, A new convergent algorithm to approximate potentials from fixed angle scattering data, SIAM J. Appl. Math. 78 2018, 2714–2736]. [ABSTRACT FROM AUTHOR]

Objectives: This study examined levels of perceived stress (PS), postoperative delirium (POD) and associated factors among Thai elderly patients undergoing elective noncardiac surgery. Background and aims: Preoperative PS and change after operation have not been widely studied. Moreover, psychological factors associated with PS and POD has been poorly investigated. Materials and Methods: In total, 429 elderly patients were recruited at a university hospital. The preoperative evaluation included sociodemographic data, health behaviors at risk, Perceived Stress Scale (PSS-10), Neuroticism Inventory (NI), Mental State Examination T10 (MSET10), Montreal Cognitive Assessment (MoCA) and Geriatric Depression Scale (GDS-15). Three-day postoperative evaluation included PSS-10 and Confusion Assessment Method Algorithm (CAM) or CAM-ICU for Delirium. Multiple regression and logistic regression analysis were performed to determine potential predictors. Results: Females were 58.97%, and the mean age was 69.93 ± 6.87 years. Mean pre- and postoperative PS were 12.77 ± 5.41 and 13.39 ± 5.26, respectively (P < 0.05). Multiple regression revealed that neuroticism, depression, and BMI predicted PS significantly. None of the independent variables was found to predict postoperative PS except for preoperative PS (p <.001). POD at the recovery room was predicted by preoperative PS (odds ratio = 1.181, 95% CI = 1.019–1.369), whereas overall POD was predicted by MoCA (odds ratio =.864, 95% CI =.771 -.968). Conclusion: Preoperative PS was significant in that it was associated with postoperative PS and POD. A careful assessment of preoperative PS as well as providing brief interventions for patients with high levels of this condition may reduce the risk of POD. [ABSTRACT FROM AUTHOR]

The purpose of this note is to correct the statement of Theorem 1.1 in [J. A. Barceló et al., SIAM J. Appl. Math., 78 (2018), pp. 2714--2736] which consider any dimension d ≥ 2, since the proof given fails in dimension d = 2. The gap in the proof is in Lemma 2.5 of [J. A. Barceló et al., SIAM J. Appl. Math., 78 (2018), pp. 2714--2736] where an estimate for the resolvent of the Laplace operator (Δ + k²)-1 in Rd is stated for k small and any dimension d ≥ 2. However, this estimate is only true for d ≥ 3. [ABSTRACT FROM AUTHOR]

Live shrimp movements pose a potential route for site‐to‐site transmission of acute hepatopancreatic necrosis disease (AHPND) and other shrimp diseases. We present the first application of network theory to study shrimp epizootiology, providing quantitative information about the live shrimp movement network of Thailand (LSMN), and supporting practical and policy implementations of disease surveillance and control measures. We examined the LSMN over a 13‐month period from March 2013 to March 2014, with data obtained from the Thailand Department of Fisheries. The LSMN had a mixture of characteristics both limiting and facilitating disease spread. Importantly, the LSMN exhibited power‐law distributions of in and out degrees with exponents of 2.87 and 2.17, respectively. This characteristic indicates that the LSMN behaves like a scale‐free network and suggests that an effective strategy to control disease spread in the Thai shrimp farming sector can be achieved by removing a small number of targeted inter‐site connections (arcs between nodes). Specifically, a disease‐control algorithm based on betweenness centrality (defined as the number of shortest paths between node pairs that traverse a given arc) is proposed here to prioritize targets for disease surveillance and control measures. [ABSTRACT FROM AUTHOR]

New block modified Gram--Schmidt (BMGS) methods for the Q-R factorization of a full column rank matrix X × Rm×n, m× n, are considered. Such methods factor X into Q × Rm×n and an upper triangular R × Rm×n such that X = QR, where, in exact arithmetic, Q is left orthogonal (i.e., QT Q = In). Gram--Schmidt-based algorithms play an important role in the implementation of Krylov space methods, such as GMRES, Arnoldi, and Lanczos. For these applications, the left orthogonal factor Q is needed and the matrix is produced either one column at a time or one block of columns at a time. For block implementations of Krylov methods, a block of columns of X is introduced at each step, and a new block of columns of Q must then be produced. That is a task for which BMGS methods are ideally suited. However, for these Krylov methods to converge properly, the BMGS algorithms need to have numerical behavior that is similar to that of modified Gram--Schmidt. To design such BMGS algorithms, we build upon the block Householder representation of Schreiber and Van Loan [SIAM J. Sci. Stat. Comput., 10 (1989), pp. 53--57] and an observation by Charles Sheffield analyzed by Paige [SIAM J. Matrix Anal. Appl., 31 (2009), pp. 565--583] about the relationship between modified Gram--Schmidt and Householder Q-R factorization. Our new BMGS algorithms exploit the Sheffield framework so that they share a similar relationship to Householder Q-R and thus have error analysis properties similar to modified Gram--Schmidt. The last BMGS algorithm developed is based entirely upon matrix multiplications and the "tall, skinny" Q-R (TSQR) factorization--two operations that have been studied extensively for cache-based architectures and distributed architectures. It is shown that if the TSQR part of the BMGS algorithm satisfies error analysis properties connected to the Sheffield structure, then so does the entire BMGS algorithm. Thus new criteria for when a BMGS algorithm has error analysis properties similar to those of MGS are proposed. [ABSTRACT FROM AUTHOR]

A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is, constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is β-Hӧlder continuous. It features a very flexible adaptive mechanism for determining the inexactness which is allowed, at each iteration, when computing objective function values and derivatives. The complexity analysis covers arbitrary optimality order and arbitrary degree of available approximate derivatives. It extends results of Cartis, Gould, and Toint [SIAM J. Optim., to appear] on the evaluation complexity to the inexact case: if a qth-order minimizer is sought using approximations to the first p derivatives, it is proved that a suitable approximate minimizer within ⲉ is computed by the proposed algorithm in at most O (ⲉ−p+β/p−q+β) iterations and at most O(|log(ⲉ)|ⲉ−p+β/p−q+β) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(|log(ⲉ)|+ⲉ−p+β/p−q+β) evaluations. While the proposed framework remains so far conceptual for high degrees and orders, it is shown to yield simple and computationally realistic inexact methods when specialized to the unconstrained and bound-constrained first-and second-order cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive sample-size rules for subsampling methods typical of machine learning. [ABSTRACT FROM AUTHOR]

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]

We prove that a cyclic coordinate fixed point algorithm for nonexpansive mappings when the underlying Hilbert space is decomposed into a Cartesian product of finitely many block spaces is weakly convergent to a fixed point of the mapping under investigation. Our result relaxes a condition imposed on the stepsizes of Theorem 3.4 of Chow, et al [Chow, Y. T., Wu, T. and Yin, W., Cyclic coordinate-update algorithms for fixed-point problems: analysis and applcations, SIAM J. Sci. Comput., 39 (2017), No. 4, A1280-A1300]. [ABSTRACT FROM AUTHOR]

We extend the proof in [M. Crouzeix and C. Palencia, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 649-655] to show that other regions in the complex plane are K-spectral sets. In particular, we show that various annular regions are (1 + √2)-spectral sets and that a more general convex region with a circular hole or cutout is a (3 + 2 √3)-spectral set. We demonstrate how these results can be used to give bounds on the convergence rate of the GMRES algorithm for solving linear systems and on that of rational Krylov subspace methods for approximating f(A)b, where A is a square matrix, b is a given vector, and f is a function that can be uniformly approximated on such a region by rational functions with poles outside the region. [ABSTRACT FROM AUTHOR]

We consider some non-smooth functions and investigate the numerical behavior of the Piecewise Linear Hompotopy (PLH) method ([Bozântan, A., An implementation of the piecewise-linear homotopy algorithm for the computation of fixed points, Creat. Math. Inform., 19 (2010), No. 2, 140-148] and [Bozântan, A. and Berinde, V., Applications of the PL homotopy algorithm for the computation of fixed points to unconstrained optimization problems, Creat. Math. Inform., 22 (2013), No. 1, 41-46]). We compare the PLH method with the BFGS with inexact line search, a quasi-Newton method, having some results reported in [Lewis, A. S. and Overton, M. L., Nonsmooth optimization via BFGS, submitted to SIAM J. Optimiz, (2009)]. For most of the considered cases, the characteristics of the PLH method are quite similar to the BFGS method, that is, the PLH method converges to local minimum values and the convergence rate seems to be linear with respect to the number of function evaluations, but we also identify some issues with the PLH method. [ABSTRACT FROM AUTHOR]

In this work, we develop geometric multigrid algorithms for the immersed finite element methods for elliptic problems with interface (Chou et al. Adv. Comput. Math. 33, 149–168 2010; Kwak and Lee, Int. J. Pure Appl. Math. 104, 471–494 2015; Li et al. Numer. Math. 96, 61–98 2003, 2004; Lin et al. SIAM J. Numer. Anal. 53, 1121–1144 2015). We need to design the transfer operators between levels carefully, since the residuals of finer grid problems do not satisfy the flux condition once projected onto coarser grids. Hence, we have to modify the projected residuals so that the flux conditions are satisfied. Similarly, the correction has to be modified after prolongation. Two algorithms are suggested: one for finite element spaces having vertex degrees of freedom and the other for edge average degrees of freedom. For the second case, we use the idea of conforming subspace correction used for P1 nonconforming case (Lee 1993). Numerical experiments show the optimal scalability in terms of number of arithmetic operations, i.e., O (N) for V -cycle and CG algorithms preconditioned with V -cycle. In V -cycle, we used only one Gauss-Seidel smoothing. The CPU times are also reported. [ABSTRACT FROM AUTHOR]

In the Steiner point removal problem, we are given a weighted graph G = (V,E) and a set of terminals K ⊏ V of size k. The objective is to find a minor M of G with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer, and Nguyen [SIAM J. Comput., 44 (2015), pp. 975--995] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most O(log5 κ). Cheung [Proceedings of the 29th Annual ACM/SIAM Symposium on Discrete Algorithms, 2018, pp. 1353--1360] improved the analysis of the same algorithm, bounding the distortion by O(log² κ). We devise a novel and simpler algorithm (called the Relaxed-Voronoi algorithm) which incurs distortion O(log κ). This algorithm can be implemented in almost linear time (O(| E| log | V |)). [ABSTRACT FROM AUTHOR]

Random and systematic errors affect navigation satellite observations on both pseudo-range and carrier phase. These errors are originated at satellites, propagation path and receivers. This study focuses on the GNSS receiver internal delay determination resulting from the receiver's electronics circuit. The characterisation of the delay in the GNSS geodetic receivers is essential to enhance the accuracy for the time transfer and time comparisons as part of GNSS integrity chain determinations. The purpose of GNSS receiver internal delay at the National Institute of Metrology (Thailand), NIMT, is to estimate the characteristics and performances of the GNSS geodetic receiver used for international time comparisons. The experiments are simultaneously observed GNSS satellites by a GPS and a GNSS receivers and two separate antennas with short baseline (around 6 metres), where both receivers are connected to the identical external caesium frequency standard maintained as time and frequency standard of Thailand. The GPS receiver is well-defined for its receiver internal delay on the pseudo-range observation of C1, through comparisons using an internationally recognised method, while the geodetic GNSS receiver is to be defined on its receiver internal delay. These experiment observations started from 26 December 2017 to 17 January 2018 at NIMT, Pathumthani, Thailand. The determined unknowns are receiver position, receiver clock offset, tropospheric delay through the geodetic technique of static Precise Point Positioning observations with Bernese GNSS software version 5.2. Later the receiver internal delay of NIMT is computed and analysed. The receiver internal delay on GPS C1 code is successfully characterised, resulted as 346.0 nanoseconds as of this experiment. [ABSTRACT FROM AUTHOR]

Study design:A cross-sectional study.Objectives:To study prevalence of pressure ulcers (PrUs), quality of life (QoL) and effect of wheelchair cushions used by Thai wheelchair users with chronic spinal cord injury (SCI).Setting:Maharaj Hospital, Chiang Mai, Thailand.Methods:Thai chronic SCI wheelchair users, aged over 18 years and non-ambulatory with ASIA impairment scale A, B or C were recruited. They completed the PrUs questionnaire and rated the EuroQoL-5D and their health status with a visual analog scale (VAS). Demographic data of each participant were extracted from medical records. The EQ-5D health states were transformed to utility scores by using the Thai algorithm and the prevalence of PrUs was reported. The EQ-5D, the utility scores and the health status VAS were compared between those with and without current PrUs and between those participants using foam and air-filled cushions.Results:Of 129 participants, 26.4% had current PrUs at the time of the study, 27.9% had healed PrUs and 45.7% never had PrUs. The median VAS score for health status was 70 (Q1=50, Q3=80). Based on the EQ-5D, only one dimension (anxiety/depression) was significantly different between those with and those without current PrUs (P=0.015). Those using an air-filled cushions had a mean utility score four times higher than of those using a foam cushion (0.131 vs 0.032, P=0.089) but not statistically significant.Conclusions:PrUs are still prevalent among Thai wheelchair users with chronic SCI. Anxiety/depression is associated with current ulcers. [ABSTRACT FROM AUTHOR]

Background/Aims Biomarkers associated with treatment-effect heterogeneity can be used to make treatment recommendations that optimize individual clinical outcomes. To accomplish this, statistical methods are needed to generate marker-based treatment-selection rules that can most effectively reduce the population burden due to disease and treatment. Compared to the standard approach of risk modeling to derive treatment-selection rules, a more robust approach is to directly minimize an unbiased estimate of total disease and treatment burden among a pre-specified class of rules. This problem is one of minimizing a weighted sum of 0–1 loss function, which is computationally challenging to solve due to the nonsmoothness of 0–1 loss. Huang and Fong, among others, proposed a method that uses the Ramp loss to approximate the 0–1 loss and solves the minimization problem through repetitive constrained optimizations. The algorithm was shown to have comparable or better performance than other comparative estimators in various settings. Our aim in this article is to further extend the algorithm to allow for variable selection in the presence of a large number of candidate markers. Methods We develop an alternative method to derive marker combinations to minimize the weighted sum of Ramp loss in Huang and Fong, based on data from randomized trials. The new algorithm estimates treatment-selection rules by repetitively minimizing a smooth and differentiable objective function. Through the use of an L1 penalty, we expand the method to allow for feature selection and develop an algorithm based on the coordinate descent method to build the treatment-selection rule. Results Through extensive simulation studies, we compared performance of the proposed estimator to four existing approaches: (1) a logistic regression risk modeling approach, and three other “direct optimizing” approaches including (2) the estimator in Huang and Fong, (3) the weighted support vector machine, and (4) the weighted logistic regression. The proposed estimator performs comparably to that of Huang and Fong, and comparably or better than other estimators. Allowing for variable selection using the proposed estimator in the presence of a large number of markers further improves treatment-selection performance. The proposed estimator is also advantageous for selecting variables relevant to treatment selection compared to L1 penalized logistic regression and weighted logistic regression. We illustrate the application of the proposed methods in host-genetics data from an HIV vaccine trial. Conclusion The proposed estimator is appealing considering its effectiveness and conceptual simplicity. It has significant potential to contribute to the selection and combination of biomarkers for treatment selection in clinical practice. [ABSTRACT FROM AUTHOR]

The present study was taken up with the objective of developing a methodology for estimation of actual evapotranspiration (AET) using only satellite data. Accordingly, an algorithm based on the popular Priestley–Taylor method was developed. While previous studies have assumed a triangular relationship between land surface temperature (LST) and fraction of vegetation (FV) to calculate the Priestley–Taylor parameter (φ), a trapezoidal relationship was adopted in the present study to enable applications in forested regions in the humid tropics. The developed algorithm was applied to the humid tropical Mae Klong region, Thailand, and latent heat flux (λET) estimates were validated with measurements made at a flux tower located at the centre of the region. Moderate Resolution Imaging Spectroradiometer (MODIS) remote sensing satellite data products corresponding to the study area were used to derive various inputs required by the algorithm. Comparison of estimated and measured fluxes on five cloud-free days in 2003 yielded root mean square error (RMSE) of 64.73 W m−2which reduced to 18.65 W m−2when one day was treated as an outlier. The methodology developed in this study derived inputs only from satellite imagery and provided reasonably accurate estimates of latent heat flux at a humid tropical location. [ABSTRACT FROM AUTHOR]

Objective: The aim of the study reported here was to validate the risk-scoring algorithm for prognostication of scrub typhus severity. Methods: The risk-scoring algorithm for prognostication of scrub typhus severity developed earlier from two general hospitals in Thailand was validated using an independent dataset of scrub typhus patients in one of the hospitals from a few years later. The predictive performances of the two datasets were compared by analysis of the area under the receiver-operating characteristic curve (AuROC). Classification of patients into non-severe, severe, and fatal cases was also compared. Results: The proportions of non-severe, severe, and fatal patients by operational definition were similar between the development and validation datasets. Patient, clinical, and laboratory profiles were also similar. Scores were similar in both datasets, both in terms of discriminating non-severe from severe and fatal patients (AuROC =88.74% versus 91.48%, P=0.324), and in discriminating fatal from severe and non-severe patients (AuROC =88.66% versus 91.22%, P=0.407). Over- and under-estimations were similar and were clinically acceptable. Conclusion: The previously developed risk-scoring algorithm for prognostication of scrub typhus severity performed similarly with the validation data and the first dataset. The scoring algorithm may help in the prognostication of patients according to their severity in routine clinical practice. Clinicians may use this scoring system to help make decisions about more intensive investigations and appropriate treatments. [ABSTRACT FROM AUTHOR]

Purpose: To develop a simple risk-scoring system to forecast scrub typhus severity. Patients and methods: Seven years' retrospective data of patients diagnosed with scrub typhus from two university-affiliated hospitals in the north of Thailand were analyzed. Patients were categorized into three severity groups: nonsevere, severe, and dead. Predictors for severity were analyzed under multivariable ordinal continuation ratio logistic regression. Significant coefficients were transformed into item score and summed to total scores. Results: Predictors of scrub typhus severity were age >15 years, (odds ratio [OR] =4.09), pulse rate >100/minute (OR 3.19), crepitation (OR 2.97), serum aspartate aminotransferase >160 IU/L (OR 2.89), serum albumin ⩽3.0 g/dL (OR 4.69), and serum creatinine >1.4 mg/dL (OR 8.19). The scores which ranged from 0 to 16, classified patients into three risk levels: non-severe (score ⩽5, n=278, 52.8%), severe (score 6-9, n=143, 27.2%), and fatal (score ⩾10, n=105, 20.0%). Exact severity classification was obtained in 68.3% of cases. Underestimations of 5.9% and overestimations of 25.8% were clinically acceptable. Conclusion: The derived scrub typhus severity score classified patients into their severity levels with high levels of prediction, with clinically acceptable under- and overestimations. This classification may assist clinicians in patient prognostication, investigation, and management. The scoring algorithm should be validated by independent data before adoption into routine clinical practice. [ABSTRACT FROM AUTHOR]

We give a #NC upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta and Ramachandran (SIAM J. Comput. 21:755-780, ). We also show that the problem is #NC hard. Our results show that the difference between #BWBP and #NC is captured exactly by the addition of a visible stack to a nondeterministic finite-state automaton. [ABSTRACT FROM AUTHOR]

Ontology plays an important role in knowledge representation, especially in the domain of information retrieval. However, building ontology remains a challenging problem because it is a time-consuming task for experts. To overcome these drawbacks, we propose a novel approach called the Automatic Thai Legal Ontology Building (ATOB) algorithm for automatic legal ontology building and to improve the court sentences retrieval process. The ATOB can automatically generate seed ontology and expand the ontology using Thai legal terminology, i.e. TLlexicon. The expansion process is terminated automatically by the threshold parameter. Moreover, the ATOB applies the concept of the ant colony algorithm to improve the court sentences retrieval process. We conclude that the effective ontology should be weight-embedded. The empirical results demonstrate that the performance of the ATOB algorithm is better than that of the traditional search method. The performance figures for the ATOB framework measured in terms of precision, recall, F-measure and diversity are 0.90, 0.91, 0.90 and 0.39, respectively. [ABSTRACT FROM PUBLISHER]

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, ) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, ) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, ) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, ), we obtain a randomized 2 r(1+ ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ ε)-algorithm for the off-line case with related machines. [ABSTRACT FROM AUTHOR]

Since antiquity names have been very important to people. Naming from the past to the present has been continuously developed and has evolved into a variety of patterns. Each pattern has its own rules depending on local belief and language that has been developed until the present. In many cultures naming is not only important because every individual needs to have a name but have helpful names or names with a good sound. The basic goal of naming in Thai society is to provide a good fortune and progress of living. Most Thai parents try to choose names they feel will bring good luck to their offspring and to the family. The choice of appropriate names is based on old rules of Thai astrology according to weekday of birth, and the rules of available letters can influence the destiny of the individuals as is described in Thai astrology, since it uses the day of birth as an input. Thais can change their own given names as often as they want in order to achieve a good fortune. The current web based systems for Thai names are static web pages and cannot deal with the problem of helping change a name to a good name with similar sound. In this research, a web-based system with a novel name matching algorithm for analysing Thai names is proposed, which takes into account the Thai astrology and uses a statistical ontology to check and evaluate how suitable names in the cultural environment with respect to sound and the persons' fortune are. The system and the algorithm have been implemented to assess Thai naming habits and the development in naming conventions over the past 20 years. The analysis concentrates on how which names have been adopted as "good names", how much they follow the rules according to Thai astrology and whether they contain letters out of the so-called misfortune attribute set or not. After a name has been found to be of low value to the individual or to contain letters from the misfortune attribute, the system of Thai astrology naming will help to change names. A new composite name matching technique called Metasound (a combination of the Soundex and Metaphone algorithms) has been implemented and is used for finding name variants (spelling and phonetic variations). Therefore, Metasound has been developed based on commonplace rules of Thai pronunciation for matching words that sound and are spelled alike. The algorithm reduces the Thai alphabet to eight consonant sounds:/ k/ or /kh//K,/b/ or /p/ B, /d/, /t/ or /th/ D, //./ NG, /n/ N, /m/ M, /j/ Y and /w/ W. With the help of this new algorithm it is possible to offer a web based service for changing a given name leading to a good fortune according to Thai belief and with a melodious sound. [ABSTRACT FROM AUTHOR]

Abstract  We show that the NP-hard optimization problems minimum and maximum weight exact satisfiability (XSAT) for a CNF formula C over n propositional variables equipped with arbitrary real-valued weights can be solved in O(||C||20.2441n ) time. To the best of our knowledge, the algorithms presented here are the first handling weighted XSAT optimization versions in non-trivial worst case time. We also investigate the corresponding weighted counting problems, namely we show that the number of all minimum, resp. maximum, weight exact satisfiability solutions of an arbitrarily weighted formula can be determined in O(n 2�||C||  20.40567n ) time. In recent years only the unweighted counterparts of these problems have been studied (Dahll�f and Jonsson, An algorithm for counting maximum weighted independent sets and its applications. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 292–298, 2002; Dahll�f et al., Theor Comp Sci 320: 373–394, 2004; Porschen, On some weighted satisfiability and graph problems. In: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005). Lecture Notes in Comp. Science, vol. 3381, pp. 278–287. Springer, 2005). [ABSTRACT FROM AUTHOR]

In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput., 23 (1994), pp. 864-894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14-23]. We present approximation algorithms for 0-EXTENSION. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71-101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput., 25 (1996), pp. 235-251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least c&radiclg k; for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations. [ABSTRACT FROM AUTHOR]