Search

Recently, there has been a growing interest in efficient numerical algorithms based on tensor networks and low-rank techniques to approximate high-dimensional functions and solutions to high-dimensional PDEs. In this paper, we propose a new tensor rank reduction method based on coordinate transformations that can greatly increase the efficiency of high-dimensional tensor approximation algorithms. The idea is simple: given a multivariate function, determine a coordinate transformation so that the function in the new coordinate system has smaller tensor rank. We restrict our analysis to linear coordinate transformations, which gives rise to a new class of functions that we refer to as tensor ridge functions. Leveraging Riemannian gradient descent on matrix manifolds we develop an algorithm that determines a quasi-optimal linear coordinate transformation for tensor rank reduction. The results we present for rank reduction via linear coordinate transformations open the possibility for generalizations to larger classes of nonlinear transformations. • Riemannian optimization of tensor ridge functions. • Tensor rank reduction via coordinate flows. • PDEs in curvilinear coordinate systems. • Rank-adaptive tensor methods. [ABSTRACT FROM AUTHOR]

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q -MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q -MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q , and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees. [ABSTRACT FROM AUTHOR]

Abstract It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a (non-negatively) weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. In particular, this allows for an effective treatment of polynomials with rational coefficients. In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum of squares decomposition for univariate polynomials with rational coefficients. The first algorithm, due to the third author, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition, but its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition, and was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. Finally, we report on our implementations of both algorithms and compare them in practice on several application benchmarks. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better. [ABSTRACT FROM AUTHOR]

Highlights • Uncertainty propagation properties of a two-stage fast BSDA is observed. • Explicit closed-form approximation of uncertainties is derived analytically. • The explicit formulas facilitate a probabilistic characterization for different factors. • Strong correlation exists among the damping ratio, PSD of modal excitation and prediction error. • The nature of the excitation can affect the damping ratio significantly. Abstract This paper investigates the uncertainty propagation properties of a two-stage fast Bayesian spectral density approach (two-stage fast BSDA) with separated modes proposed previously by the authors Yan and Katafygiotis (2015a,b) [1,2], deriving explicit formulas for the dependence of the posterior coefficients of variation (c.o.v.) of the identified modal parameters in terms of different parameters influencing the identification. For this, an approximation analysis strategy proposed in Au (2014a,b) [3,4] is adopted. Although the explicit closed-form approximation expressions are relatively complex, the expressions for the approximate dependence of uncertainty are simple and informative. The analysis reveals a strong correlation among the prediction error, the damping ratio and the power spectral density (PSD) of the modal excitation. While similar correlation trends have been observed in the posterior uncertainty analysis of the fast Bayesian FFT (fast BFFT) approach Au (2014a) [3], the present method shows that the identification results are more sensitive to modeling error. Note that this is not a contradicting result, as the uncertainty propagation properties of different methods may generally differ. Note that fast BFFT is a more fundamental method, in the sense that it processes FFT data directly, while the two-stage fast BSDA uses spectral density data in a manner that allows for decoupling of the mode shape data. Validation studies using synthetic data and field data measured from a laboratory model provide a practical verification of the rationality and accuracy of the theoretical findings. [ABSTRACT FROM AUTHOR]

Abstract In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. Highlights • A thorough study of the approximation ratio for the natural algorithm First Fit. • A study of sum coloring of graphs, of vertices or edges. • A tight analysis of (k + 1)-claw free graphs, with new types of examples. • A tight analysis for important subclasses of via linear programs. • A tight analysis for edge coloring and a tight analysis for unit interval graphs. [ABSTRACT FROM AUTHOR]

Abstract An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing , that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. Highlights • HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3. • Polynomial-time HV-planarity testing for 2-connected series-parallel graphs. • Polynomial-time HV-planarity testing for partial 2-trees. [ABSTRACT FROM AUTHOR]

Abstract We consider the design of strategyproof cost-sharing mechanisms. We give two simple, but extremely versatile, black-box reductions , that in combination reduce the cost-sharing mechanism-design problem to the algorithmic problem of finding a min-cost solution for a set of players. Our first reduction shows that any truthful, α -approximation mechanism for the social-cost minimization (SCM) problem satisfying a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an O (α log ⁡ n) -approximation where the prices recover the cost incurred. Thus, we decouple the approximation and cost-recovery objectives. Our second reduction nicely complements the first one by showing that any LP-relative ρ -approximation for the problem of finding a min-cost solution for a set of players yields a truthful, no-bossy, (ρ + 1) -approximation for the SCM problem (and hence, a truthful (ρ + 1) log ⁡ n -approximation cost-sharing mechanism). These reductions yield the first, or improved, polytime cost-sharing mechanisms for a variety of problems. [ABSTRACT FROM AUTHOR]

Abstract Let R be a finite set of terminals in a convex metric space (M , d). We give approximation algorithms for problems of finding a minimum size set S ⊆ M of additional points such that the unit-disc graph G [ R ∪ S ] of R ∪ S satisfies some connectivity properties. Let Δ be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + ln ⁡ (Δ − 1) + ϵ , which in R 2 reduces to 1 + ln ⁡ 4 + ϵ < 2.3863 + ϵ ; this improves the ratios ⌊ (Δ + 1) / 2 ⌋ + 1 + ϵ of [19] and 2.5 + ϵ of [7] , respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Δ-approximation algorithm, improving the ratio 2 (Δ − 1) of [21]. We also simplify the Δ-approximation of [4] , when G [ R ∪ S ] should be 2-connected. Highlights • We consider connectivity problems on unit-disc graphs in a convex metric space. • Let Δ be the maximum number of independent points in a unit ball. • For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ + 1) / 2 to 1 + ln ⁡ (Δ − 1). • For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2 (Δ − 1) to Δ. [ABSTRACT FROM AUTHOR]

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSP ( Γ ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP ( Γ ) and show how this leads to efficient constant-factor approximation algorithms for several examples that cover all previously known cases that are NP-hard to solve to optimality but admit constant-factor approximation. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Thus, our results indicate where the boundary of constant-factor approximability for VCSPs lies. [ABSTRACT FROM AUTHOR]

Abstract We propose a novel weakly supervised localization method based on Fisher-embedding of low-level features (CNN, SIFT), and model sparsity at the component level. Fisher-embedding provides an interesting alternative to raw low-level features, since it allows fast and accurate scoring of image subwindows with a model trained on entire images. Model sparsity reduces overfitting and enables fast evaluation. We also propose two new techniques for improving performance when our method is combined with nonlinear normalizations of the aggregated Fisher representation of the image. These techniques are (i) intra-component metric normalization and (ii) first-order approximation to the score of a normalized image representation. We evaluate our weakly supervised localization method on real traffic scenes acquired from driver's perspective. The method dramatically improves the localization AP over the dense non-normalized Fisher vector baseline (16 percentage points for zebra crossings, 21 percentage points for traffic signs) and leads to a huge gain in execution speed (91 × for zebra crossings, 74 × for traffic signs). Graphical abstract Highlights • We propose weakly-supervised localization based on patch-level Fisher embedding. • A sliding window localization model is trained on entire images. • Component-level sparsity enables fast evaluation and reduces overfitting. • Approximated patch scoring allows the use of non-linear normalizations. • We present road-mapping experiments on two kinds of local features (SIFT, CNN). [ABSTRACT FROM AUTHOR]

This paper addresses the problem of trajectory planning of a mobile robot for pasture maintenance comprising mulching weeds, reseeding patches without vegetation and spreading cowpats. Based on the sensor-based acquired data (points of interest), the proposed approach is to first use an approximation algorithm for data clustering in the form of non-convex and convex hulls. These hulls are then delimited by stair-shaped limits with respect to the working width of the robot, and their centres of gravity calculated. To minimise the travelled distance between the centres of gravity of the defined areas, the Travelling Salesman Problem is addressed via an evolutionary algorithm. Finally, kinematic and dynamic properties of the robot are considered in order to generate the final trajectory. The capabilities of the proposed approaches are highlighted through the processing of several datasets. Graphical abstract (a)-Terestrial information about the field (b, c, d, e)-Sensor-based data about the field considering weed map, areas without vegetation and areas with cowpats (f)-Detail of the calculated path for the pasture robot based on convex hulls, centre of gravity, travelling salesman and evolutionary algorithm. Image 1 Highlights • Method development for selectively pasture maintenance with robotics. • Path planning for a mobile robot considering selectively pasture maintenance. • Data clustering based on approximation algorithm using non-convex and convex hulls. • Path optimization using evolutionary algorithm for Traveling Salesman Problem. • Trajectory calculation in respect of kinematic and dynamic properties of the robot. [ABSTRACT FROM AUTHOR]

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of study on this problem, focusing on exact and approximation algorithms. It is thus natural to consider whether these algorithms can be further improved in terms of running times. We provide strong lower bounds on the running times of exact and approximation schemes for the classical scheduling problem based on Exponential Time Hypothesis, showing that the best known approximation and exact algorithms are almost the best possible in terms of the running time. [ABSTRACT FROM AUTHOR]

In bin packing with cardinality constraints (BPCC), there is an upper bound k ≥ 2 on the number of items that can be packed into each bin, additionally to the standard constraint on the total size of items. We study the algorithm First Fit (FF), acting on a list of items, packing each item into the minimum indexed bin that contains at most k − 1 items and has sufficient space for the item. We present a complete analysis of its asymptotic approximation ratio for all values of k . Many years after FF for BPCC was introduced, its tight asymptotic approximation ratio is finally found. [ABSTRACT FROM AUTHOR]

Artificial neural networks (ANNs) have become a very powerful tool in the approximation of high-dimensional functions. Especially, deep ANNs, consisting of a large number of hidden layers, have been very successfully used in a series of practical relevant computational problems involving high-dimensional input data ranging from classification tasks in supervised learning to optimal decision problems in reinforcement learning. There are also a number of mathematical results in the scientific literature which study the approximation capacities of ANNs in the context of high-dimensional target functions. In particular, there are a series of mathematical results in the scientific literature which show that sufficiently deep ANNs have the capacity to overcome the curse of dimensionality in the approximation of certain target function classes in the sense that the number of parameters of the approximating ANNs grows at most polynomially in the dimension d ∈ N of the target functions under considerations. In the proofs of several of such high-dimensional approximation results it is crucial that the involved ANNs are sufficiently deep and consist a sufficiently large number of hidden layers which grows in the dimension of the considered target functions. It is the topic of this work to look a bit more detailed to the deepness of the involved ANNs in the approximation of high-dimensional target functions. In particular, the main result of this work proves that there exists a concretely specified sequence of functions which can be approximated without the curse of dimensionality by sufficiently deep ANNs but which cannot be approximated without the curse of dimensionality if the involved ANNs are shallow or not deep enough. [ABSTRACT FROM AUTHOR]

If a closed subset of a Riemann surface is a set of uniform meromorphic approximation, then its boundary is shown to be a set of tangential meromorphic approximation. [ABSTRACT FROM AUTHOR]

As of April 2018, UniProtKB has collected more than 115 million protein sequences. Less than 0.15% of these proteins, however, have been associated with experimental GO annotations. As such, the use of automatic protein function prediction (AFP) to reduce this huge gap becomes increasingly important. The previous studies conclude that sequence homology based methods are highly effective in AFP. In addition, mining motif, domain, and functional information from protein sequences has been found very helpful for AFP. Other than sequences, alternative information sources such as text, however, may be useful for AFP as well. Instead of using BOW (bag of words) representation in traditional text-based AFP, we propose a new method called DeepText2GO that relies on deep semantic text representation, together with different kinds of available protein information such as sequence homology, families, domains, and motifs, to improve large-scale AFP. Furthermore, DeepText2GO integrates text-based methods with sequence-based ones by means of a consensus approach. Extensive experiments on the benchmark dataset extracted from UniProt/SwissProt have demonstrated that DeepText2GO significantly outperformed both text-based and sequence-based methods, validating its superiority. [ABSTRACT FROM AUTHOR]

In this work, we consider the problem of computing triangular bases of integral closures of one-dimensional local rings. Let ( K , v ) be a discrete valued field with valuation ring O and let m be the maximal ideal. We take f ∈ O [ x ] , a monic irreducible polynomial of degree n and consider the extension L = K [ x ] / ( f ( x ) ) as well as O L the integral closure of O in L , which we suppose to be finitely generated as an O -module. The algorithm MaxMin, presented in this paper, computes triangular bases of fractional ideals of O L . The theoretical complexity is equivalent to current state of the art methods and in practice is almost always faster. It is also considerably faster than the routines found in standard computer algebra systems, excepting some cases involving very small field extensions. [ABSTRACT FROM AUTHOR]

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from π 2 6 − 1 36 + ϵ ≈ 1.617 to 11 7 ≈ 1.571 . Moreover, we show that the algorithm of Khuller et al. [11] for the strongly connected spanning subgraph problem, which achieves an approximation ratio of 1.617, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results by using interesting conditions for the existence of a second Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

We motivate and describe a new parameterized approximation paradigm which studies the interaction between approximation ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of an α - shrinking transformation , for α ≥ 1 . Applying such transformation to a parameterized problem instance decreases the parameter value, while preserving the approximation ratio of α (or α-fidelity ). Moving even beyond the approximation ratio, we call for a new type of approximative kernelization race . Our α -shrinking transformations can be used to obtain approximative kernels which are smaller than the best known for a given problem. The smaller “ α -fidelity” kernels allow us to obtain an exact solution for the reduced instance more efficiently, while obtaining an approximate solution for the original instance. We show that such fidelity preserving transformations exist for several fundamental problems, including Vertex Cover , d-Hitting Set , Connected Vertex Cover and Steiner Tree . [ABSTRACT FROM AUTHOR]

Given a uniformly continuous map f from a doubling metric space X to a normed linear space V , and given a subadditive function ω , we give a characterization of ω dominating the modulus of continuity of f in terms of Lipschitz approximation. As the main part of this characterization, we give a constructive method of approximating a uniformly continuous map from X to V by Lipschitz maps, the corresponding approximation operation is linear. [ABSTRACT FROM AUTHOR]

Randomized algorithms play a central role in low rank approximations of large matrices. In this paper, the scheme of the randomized SVD is extended to a randomized LU algorithm. Several error bounds are introduced, that are based on recent results from random matrix theory related to subgaussian matrices. The bounds also improve the existing bounds of already known randomized SVD algorithm. The algorithm is fully parallelized and thus can utilize efficiently GPUs without any CPU–GPU data transfer. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented. [ABSTRACT FROM AUTHOR]

We determine the classical exponents of approximation w 3 ( ζ ) , w 3 ⁎ ( ζ ) , λ 3 ( ζ ) and w ˆ 3 ( ζ ) , w ˆ 3 ⁎ ( ζ ) , λ ˆ 3 ( ζ ) associated to real numbers ζ whose continued fraction expansions are given by a Sturmian word. We more generally provide a description of the combined graph of the parametric successive minima functions defined by Schmidt and Summerer in dimension three for such Sturmian continued fractions. This both complements similar results due to Bugeaud and Laurent concerning the two-dimensional exponents and generalizes a recent result of the author. As a side result we obtain new information on the spectra of the above exponents. Moreover, we provide some information on the exponents λ n ( ζ ) for a Sturmian continued fraction ζ and arbitrary n . [ABSTRACT FROM AUTHOR]

In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set , Max Induced Path , Forest and Tree , for any r ( n ) , a simple, known scheme gives an approximation ratio of r in time roughly r n / r . We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a r -approximation in time 2 n / r . We match this with a similarly tight result. We also give a log ⁡ r -approximation for Min ATSP in time 2 n / r and an r -approximation for Max Grundy Coloring in time r n / r . Finally, we investigate the approximability of Min Set Cover , when measuring the running time as a function of the number of sets in the input. [ABSTRACT FROM AUTHOR]

A complete weighted graph G = ( V , E , w ) is called Δ β -metric, for some β ≥ 1 / 2 , if G satisfies the β -triangle inequality, i.e., w ( u , v ) ≤ β ⋅ ( w ( u , x ) + w ( x , v ) ) for all vertices u , v , x ∈ V . Given a Δ β -metric graph G = ( V , E , w ) and a center c ∈ V , and an integer p , the Δ β -Star p -Hub Center problem ( Δ β -S p HCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δ β -S p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate the Δ β -S p HCP to a ratio g ( β ) − ϵ is NP-hard and give r ( β ) -approximation algorithms for the same problem where g ( β ) and r ( β ) are functions of β . A subclass of metric graphs is identified that Δ β -S p HCP is polynomial-time solvable. Moreover, some r ( β ) -approximation algorithms given in this paper meet approximation lower bounds. [ABSTRACT FROM AUTHOR]

Improving denoising algorithms based on nonlocal self-similarity (NSS) to cope with increasing noise levels has become difficult. This is primarily because of difficulty in accurately grouping similar image patches solely on original spatial-domain of noisy images. To solve this problem, we propose to group similar patches on transform-domain learned from clean natural images. In this paper, we introduce a denoising algorithm comprising principal component dictionary (PCD)-based patch grouping and a low-rank approximation process. In the proposed algorithm, PCD learns from clean natural images and uses the knowledge gained to guide similar patches grouping results in noisy images. Patch grouping is directly implemented on PCD-based transform-domain. And, external knowledge and internal NSS prior are used jointly for image denoising. The results of experiments conducted indicate that the proposed denoising algorithm outperforms several state-of-the-art denoising algorithms, especially in heavy noise conditions. [ABSTRACT FROM AUTHOR]

We investigate the existence of approximation algorithms for maximization of submodular functions, that run in a fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function v : 2 X → R the goal is to select a subset S of K elements from X such that v ( S ) is maximized. We identify three properties of set functions, referred to as p -separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, p -separable functions, with low values of the parameter p . We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as p and K . [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a set of jobs, each one specified by its release date, its deadline and its processing volume, on a set of heterogeneous speed-scalable processors, where the energy-consumption rate is processor-dependent. Our objective is to minimize the total energy consumption when both the preemption and the migration of jobs are allowed. We propose a new algorithm based on a compact linear programming formulation. Our method approaches the value of the optimal solution within any desired accuracy for a large set of continuous power functions. Furthermore, we develop a faster combinatorial algorithm based on flows for standard power functions and jobs whose density is lower bounded by a small constant. Finally, we extend and analyze the AVerage Rate (AVR) online algorithm in the heterogeneous setting. [ABSTRACT FROM AUTHOR]

Let C be an open cone in a Banach space equipped with the Thompson metric with closure a normal cone. The main result gives sufficient conditions for Borel probability measures μ , ν on C with finite first moment for which μ ≤ ν in the stochastic order induced by the cone to be order approximated by sequences { μ n } , { ν n } of uniform finitely supported measures in the sense that μ n ≤ ν n for each n and μ n → μ , ν n → ν in the Wasserstein metric. This result is the crucial tool in developing a pathway for extending various inequalities on operator and matrix means, which include the harmonic, geometric, and arithmetic operator means on the cone of positive elements of a C ⁎ -algebra, to the space P 1 ( C ) of Borel measures of finite first moment on C . As an illustrative and important particular application, we obtain the monotonicity of the Karcher geometric mean on P 1 ( A + ) for the positive cone A + of a C ⁎ -algebra A . [ABSTRACT FROM AUTHOR]

The model checking problem of continuous-time Markov chains with respect to continuous-time stochastic logic was introduced and shown to be decidable by Aziz et al. [1,2] in 1996. Unfortunately, their proof is only constructive, but highly unpractical. Later in 2000, an efficient approximate algorithm was proposed by Baier et al. [3,5] for a sublogic with binary until. In this paper, we apply transcendental number theory and classical linear algebra to bridge the gap between the precise but unpractical algorithm, and the imprecise but efficient approximate algorithm. We prove that the approximate algorithm in [3,5] can be used as an off-the-shell tool for a precise model checking algorithm for binary until formulas. Further, we discuss extensions of our results to nested until and continuous-time Markov decision processes. [ABSTRACT FROM AUTHOR]

Given an edge-weighted connected graph G on n vertices and a positive integer k ≤ n , a subgraph of G on k vertices is called a k -subgraph in G . We design combinatorial approximation algorithms for finding a connected k -subgraph in G such that its weighted density is at least a factor Ω ( max ⁡ { 1 / k , k 2 / n 2 } ) of the maximum weighted density among all k -subgraph in G (which are not necessarily connected), where max ⁡ { 1 / k , k 2 / n 2 } ≥ n − 2 / 3 implies an O ( n 2 / 3 ) -approximation ratio. We obtain improved O ( n 2 / 5 ) -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k -subgraph problem on general graphs. We also give O ( n log ⁡ n ) -approximation for the problem on general weighted interval graphs. [ABSTRACT FROM AUTHOR]

For k ≥ 2 even, and α ≥ − ( 2 k + 1 ) ∕ 4 , we provide a uniform approximation of the ultraspherical polynomials P k ( α , α ) ( x ) in the oscillatory region with a very explicit error term. In fact, our result covers all α for which the expression “oscillatory region” makes sense. To that end, we construct the almost equioscillating function g ( x ) = c b ( x ) ( 1 − x 2 ) ( α + 1 ) ∕ 2 P k ( α , α ) ( x ) = cos B ( x ) + r ( x ) . Here the constant c = c ( k , α ) is defined by the normalization of P k ( α , α ) ( x ) , B ( x ) = ∫ 0 x b ( x ) d x , and the functions b ( x ) and B ( x ) , as well as bounds on the error term r ( x ) , are given by some rather simple elementary functions. [ABSTRACT FROM AUTHOR]

Among the vast literature concerning graph drawing and graph theory, linear layouts of graphs have been the subject of intense research over the years, both from a combinatorial and from an algorithmic perspective. In particular, upward book embeddings of directed acyclic graphs (DAGs) form a popular class of linear layouts with notable applications, and the upward book thickness of a DAG is the minimum number of pages required by any of its upward book embeddings. A long-standing conjecture by Heath, Pemmaraju, and Trenk (1999) states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are s t -outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP -hard for any fixed k ≥ 3. We show that the problem, for any k ≥ 5 , remains NP -hard for graphs whose domination number is O (k) , but it is fixed-parameter tractable (FPT) in the vertex cover number. [ABSTRACT FROM AUTHOR]

Controllability properties of a thermoelastic plate with a curved middle surface are studied. By the Riemannian geometry approach and the multiplier technique, we obtain simultaneously exact controllability of the displacement of the plate and approximate controllability of the temperature, through three boundary controls under verifiable assumptions on the geometry of the middle surface. [ABSTRACT FROM AUTHOR]

We study the multi-budgeted version of the metric Survivable Network Design Problem (SND) (Jain, 2001), also known as Steiner Network problem, where besides the usual connectivity requirements (i.e., lower bound on the number edge-disjoint paths) between pre-specified pairs of points, we are also asked to satisfy a set of extra linear constraints (the budgets). Based on combinatorial properties of extreme point solutions of the natural LP relaxation of the problem and using the iterative method, we design new approximation algorithms with the following performance guarantee: if any edge participates in at most f ∈ N budgets, then we show how we can device an ( f + 2 , f + 2 ) bi-criteria approximation algorithm in polynomial time i.e., return a solution with cost at most ( 2 + f ) times the optimal one with a potential budget overflow bounded from above by the same factor. In other words, the approximation and budget violation guarantee we achieve is a linear function of the maximum frequency among all the edges in the budgets, as opposed to a function of the number of budgets themselves and this constitutes a strict improvement over the previous approaches. Our approach is flexible enough and we demonstrate how it can be used to provide a ( 4 , 4 ) bi-criteria algorithm for the Minimum Weighted Bounded Degree version of the SND problem in which we have the standard SND connectivity constraints and, additionally, for every vertex v in the graph we have an upper bound on the sum of the weights of the edges incident to that edge in any feasible solution. These problems, besides their obvious theoretical interest, have numerous real life applications from Cloud Computing to Optical Networking systems. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a unit disk graph corresponding to a given set P of n points in R 2 . We propose a distributed approximation algorithm to find a minimum connected dominating set of G . The maintenance of the connected dominating set constructed is fully localized. Our algorithm produces a connected dominating set of size ( 104 o p t + 52 ) , where o p t is the size of a minimum connected dominating set. The time and message complexities of our algorithm are O ( Δ ) and O ( n ) respectively, where Δ and n are the maximum node degree and number of nodes in G respectively. Our distributed approximation algorithm outperforms existing algorithms in terms of its time and message complexities. We also propose a scheduling scheme that obtains O ( Δ ) conflict-free time slots to deal with interference. [ABSTRACT FROM AUTHOR]

Recent research in algorithmic robotics considers combinatorial filters , which concisely capture the discrete structure underlying many reasoning problems for robots. An important recent result is that the filter minimization problem —Given a filter, find the smallest equivalent filter—is NP-hard. This paper extends that result along several dimensions, including hardness proofs for some natural special cases and for approximation, and new results analyzing the only known algorithm for this problem. We show that this problem is not fixed-parameter tractable for any of the obvious parameters, but it is fixed-parameter tractable for a certain combination of new parameters. [ABSTRACT FROM AUTHOR]

The main result of this paper is a Hamiltonian formulation of the nonlinear governing equations for geophysical periodic stratified water flows in the equatorial f -plane approximation allowing for piecewise constant vorticity. [ABSTRACT FROM AUTHOR]

In this paper, we obtain preasymptotic and asymptotic behavior and strong equivalences of the approximation numbers of the embeddings from the anisotropic Sobolev spaces W 2 R ( T d ) to L 2 ( T d ) . We also get the preasymptotic behavior of the approximation numbers of the embeddings from the limit spaces W 2 ∞ ( T d ) of the anisotropic Sobolev spaces W 2 R ( T d ) to L 2 ( T d ) . We show that both the above embedding problems are intractable and do not suffer from the curse of dimensionality. [ABSTRACT FROM AUTHOR]

We study an inverse acoustic scattering problem in half-space with a probabilistic impedance boundary value condition. The Robin coefficient (surface impedance) is assumed to be a Gaussian random function with a pseudodifferential operator describing the covariance. We measure the amplitude of the backscattered field averaged over the frequency band and assume that the data is generated by a single realization of λ . Our main result is to show that under certain conditions the principal symbol of the covariance operator of λ is uniquely determined. Most importantly, no approximations are needed and we can solve the full non-linear inverse problem. We concentrate on anisotropic models for the principal symbol, which leads to the analysis of a novel anisotropic spherical Radon transform and its invertibility. [ABSTRACT FROM AUTHOR]

Deadlock detection in concurrent programs that create networks with arbitrary numbers of nodes is extremely complex and solutions either give imprecise answers or do not scale. To enable the analysis of such programs, (1) we define an algorithm for detecting deadlocks of a basic model featuring recursion and fresh name generation: the lam programs , and (2) we design a type system for value-passing CCS that returns lam programs. We show the soundness of the type system, and develop a type inference algorithm for it. The resulting algorithm is able to check deadlock-freedom of programs that cannot be handled by previous analyses, such as those that build unbounded networks. [ABSTRACT FROM AUTHOR]

The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3 k -vertex kernel, implying an O ⁎ ( 8 k ) -time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2 k vertices, and as a by-product, a deterministic algorithm running in time O ⁎ ( 4 k ) . We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1.5 for the problem. [ABSTRACT FROM AUTHOR]

State of the art Diffusion Weighted Magnetic Resonance Imaging (DW-MRI) protocols of white matter followed by advanced tractography techniques produce impressive reconstructions of White Matter (WM) pathways. These pathways often contain millions of trajectories (fibers). While for several applications the high number of fibers is essential, other applications (visualization, registration, some types of across-subject comparison) can achieve satisfying results using much smaller sets and may be overburdened by the computational load of the large fiber sets. In this paper we propose a novel, highly efficient algorithm for extracting a meaningful subset of fibers, which we term the Fiber-Density-Coreset (FDC). The reduced set is optimized to represent the main structures of the brain. FDC is based on an efficient geometric approximation paradigm named coresets, an optimization scheme showing much success in tasks requiring large computation time and/or memory. FDC was compared to two commonly used methods for selecting a reduced set of fibers: fiber-clustering and downsampling. The reduced sets were evaluated by several methods, including a novel structural comparison to the full sets called 3D indicator structure comparison (3D-ISC). The comparison was applied to High Angular Resolution Diffusion Imaging (HARDI) scans of 15 healthy individuals obtained from the Human Connectome Project. FDC produced the most satisfying subsets, consistently in all 15 subjects. It also displayed low memory usage and significantly lower running time than conventional fiber reduction schemes. [ABSTRACT FROM AUTHOR]

In this paper, we evaluate the performance of the multilevel Monte Carlo method (MLMC) for deterministic and uncertain hyperbolic systems, where randomness is introduced either in the modeling parameters or in the approximation algorithms. MLMC is a well known variance reduction method widely used to accelerate Monte Carlo (MC) sampling. However, we demonstrate in this paper that for hyperbolic systems, whether MLMC can achieve a real boost turns out to be delicate. The computational costs of MLMC and MC depend on the interplay among the accuracy (bias) and the computational cost of the numerical method for a single sample, as well as the variances of the sampled MLMC corrections or MC solutions. We characterize three regimes for the MLMC and MC performances using those parameters, and show that MLMC may not accelerate MC and can even have a higher cost when the variances of MC solutions and MLMC corrections are of the same order. Our studies are carried out by a few prototype hyperbolic systems: a linear scalar equation, the Euler and shallow water equations, and a linear relaxation model, the above statements are proved analytically in some cases, and demonstrated numerically for the cases of the stochastic hyperbolic equations driven by white noise parameters and Glimm's random choice method for deterministic hyperbolic equations. • Investigate multilevel Monte Carlo for deterministic and uncertain hyperbolic systems. • Identify three regimes for the MLMC/MC performances using bias, cost and variance. • MLMC may be outperformed by MC when their variances are of the same order. • Analytical proof for prototypical scalar advection equation with white noise parameters. • Numerical justification for stochastic hyperbolic equations and Glimm's method. [ABSTRACT FROM AUTHOR]

In this work, we propose an accurate, robust (the solution remains in the set of states), and stable discretization of a nonconservative model for the simulation of compressible multicomponent flows with shocks and material interfaces. We consider the gamma-based model by Shyue (1998) [58] where each component follows a stiffened gas equation of state (EOS). We here extend the framework proposed in Renac (2019) [53] and Coquel et al. (2021) [15] for the discretization of hyperbolic systems, with both fluxes and nonconservative products, to unstructured meshes with curved elements in multiple space dimensions. The framework relies on a high-order discontinuous Galerkin spectral element method (DGSEM) using collocation of quadrature and interpolation points as proposed by Gassner (2013) [27] in the case of hyperbolic conservation laws. We modify the integrals over discretization elements where we replace the physical fluxes and nonconservative products by two-point numerical fluctuations. The contributions of this work are threefold. First, we analyze the semi-discrete DGSEM discretization of general hyperbolic systems with conservative and nonconservative terms and derive the conditions to obtain a scheme that is high-order accurate, free-stream preserving, and entropy stable when excluding material interfaces. Second, we design a three-point scheme with a HLLC solver for the gamma-based model that does not require a root-finding algorithm for the approximation of the nonconservative products. The scheme is proved to be robust and entropy stable for convex entropies, to preserve uniform profiles of pressure and velocity across material interfaces (material interface preservation), and to satisfy a discrete minimum principle on the specific entropy and maximum principles on the parameters of the EOS. Third, the HLLC solver is applied at interfaces in the DGSEM, while we consider two kinds of fluctuations in the integrals over discretization elements: the former is entropy conservative (EC), while the latter preserves material interfaces (CP). Time integration is performed using high-order strong-stability preserving Runge-Kutta schemes. The fully discrete scheme is shown to preserve material interfaces with CP fluctuations. Under a given condition on the time step, both EC and CP fluctuations ensure that the cell-averaged solution remains in the set of states; satisfy a minimum principle on any convex entropy and maximum principles on the EOS parameters. These results have allowed us to use existing limiters in order to restore positivity, and discrete maximum principles of degrees-of-freedom within elements. Numerical experiments in one and two space dimensions on flows with discontinuous solutions support the conclusions of our analysis and highlight stability, robustness and accuracy of the proposed DGSEM with either CP, or EC fluctuations, while the scheme with CP fluctuations is shown to offer better resolution capabilities. • High-order and robust discretization of a compressible nonconservative multicomponent flow model. • A DGSEM for unstructured meshes with curved elements is proposed. • Design contact-preserving and entropy conservative numerical fluxes. • Design an HLLC solver that is applied at cell interfaces. • The discrete scheme maintains positivity of the solution, preserves material interfaces and invariant domains. [ABSTRACT FROM AUTHOR]

In this paper we present a novel method for the numerical solution of linear advection equations, which is based on ridgelets. Such equations arise for instance in radiative transfer or in phase contrast imaging. Due to the fact that ridgelet systems are well adapted to the structure of linear transport operators, it can be shown that our scheme operates in optimal complexity, even if line singularities are present in the solution. The key to this is showing that the system matrix (with diagonal preconditioning) is uniformly well-conditioned and compressible – the proof for the latter represents the main part of the paper. We conclude with some numerical experiments about N -term approximations and how they are recovered by the solver, as well as localisation of singularities in the ridgelet frame. [ABSTRACT FROM AUTHOR]

We propose a fast method for high order approximations of the solution of n -dimensional parabolic problems over hyper-rectangular domains in the framework of the method of approximate approximations. This approach, combined with separated representations, makes our method effective also in very high dimensions. We report on numerical results illustrating that our formulas are accurate and provide the predicted approximation rate 6 also in high dimensions. [ABSTRACT FROM AUTHOR]

We show that a very simple modification of the Pure Greedy Algorithm for approximating functions by sparse sums from a dictionary in a Hilbert or more generally a Banach space has optimal convergence rates. [ABSTRACT FROM AUTHOR]

We study the Weighted t -Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t -USC problem, a parameter t and an undirected graph G = ( V , E ) with edge-weights w : E → R ≥ 0 and vertex-weights η : V → R + are given. The goal is to find a vertex set S ⊆ V with | S | ≤ t while minimizing w ( S , V \ S ) / η ( S ) , where w ( S , V \ S ) is the total weight of the edges with exactly one endpoint in S and η ( S ) = ∑ v ∈ S η ( v ) . For this problem, we present a ( O ( log ⁡ t ) , 1 + ϵ ) factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when t = n o ( 1 ) . We also present better approximation algorithms for Weighted ρ -Unbalanced Cut and Min–Max k -Partitioning problems. [ABSTRACT FROM AUTHOR]

Herein, we present Linear Threshold Ranking (LTR), an extension of the Linear Threshold Model (Kempe et al., KDD 2003). LTR models the spread of a message supporting a target candidate in a social network and how social influence affects the preferences of the voters who receive it, in elections based on positional scoring rules. The problem of election control through social influence requires finding a bounded subset of nodes to be the initial spreaders of this message to maximize the Margin of Victory of a target candidate against the most voted opponent. We prove the problem is NP -hard in LTR. By showing the equivalence of LTR with alternative stochastic processes and then exploiting submodularity, we provide a 1 3 (1 − 1 e) approximation algorithm. We achieve similar results also in the destructive variation of LTR, where the message undermines a target candidate, negatively influencing the voters' preference on that candidate. [ABSTRACT FROM AUTHOR]