Search

We propose a model to address the overlooked problem of node clustering in simple hypergraphs. Simple hypergraphs are suitable when a node may not appear multiple times in the same hyperedge, such as in co‐authorship datasets. Our model generalizes the stochastic blockmodel for graphs and assumes the existence of latent node groups and hyperedges are conditionally independent given these groups. We first establish the generic identifiability of the model parameters. We then develop a variational approximation Expectation‐Maximization algorithm for parameter inference and node clustering, and derive a statistical criterion for model selection. To illustrate the performance of our R package HyperSBM, we compare it with other node clustering methods using synthetic data generated from the model, as well as from a line clustering experiment and a co‐authorship dataset. [ABSTRACT FROM AUTHOR]

ABSTRACT Trivariate joint modeling for longitudinal count data, recurrent events, and a terminal event for family data has increased interest in medical studies. For example, families with Lynch syndrome (LS) are at high risk of developing colorectal cancer (CRC), where the number of polyps and the frequency of colonoscopy screening visits are highly associated with the risk of CRC among individuals and families. To assess how screening visits influence polyp detection, which in turn influences time to CRC, we propose a clustered trivariate joint model. The proposed model facilitates longitudinal count data that are zero‐inflated and over‐dispersed and invokes individual‐specific and family‐specific random effects to account for dependence among individuals and families. We formulate our proposed model as a latent Gaussian model to use the Bayesian estimation approach with the integrated nested Laplace approximation algorithm and evaluate its performance using simulation studies. Our trivariate joint model is applied to a series of 18 families from Newfoundland, with the occurrence of CRC taken as the terminal event, the colonoscopy screening visits as recurrent events, and the number of polyps detected at each visit as zero‐inflated count data with overdispersion. We showed that our trivariate model fits better than alternative bivariate models and that the cluster effects should not be ignored when analyzing family data. Finally, the proposed model enables us to quantify heterogeneity across families and individuals in polyp detection and CRC risk, thus helping to identify individuals and families who would benefit from more intensive screening visits. [ABSTRACT FROM AUTHOR]

We improve the approximation ratio for Maximum Weight Series-Parallel Subgraph from 1 / 2 to 1 / 2 + 1 / 60. [ABSTRACT FROM AUTHOR]

In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B + 1) -approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network. [ABSTRACT FROM AUTHOR]

Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of [ γ 4 a (1 + γ + γ 2 + γ 3) − ] for any ≥ 0 with a query complexity of ⌈ n / a ⌉ + a and a memory complexity of O (a k log (k) log (1 /)) , where a is a positive integer and γ is the submodularity ratio. However, the algorithm may produce less-than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of 1 − e − γ − with linear query complexity. [ABSTRACT FROM AUTHOR]

Given a set of h pairwise disjoint convex polygonal obstacles in the plane, defined with n vertices, we preprocess and compute one routing table at each vertex in a subset of vertices of . For routing a packet from any vertex s ∈ to any vertex t ∈ , our scheme computes a routing path with a multiplicative stretch 1 + and an additive stretch 2 k ℓ , by consulting routing tables at only a subset of vertices along that path. Here, k is the number of obstacles of the routing path intersects, and ℓ depends on the geometry of obstacles in . During the preprocessing phase, we construct routing tables of size O (n + h 3 2 polylog (h )) in O (n + h 3 2 polylog (h )) time, where < 1 is an input parameter. [ABSTRACT FROM AUTHOR]

Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label +. Otherwise, this edge is marked by a negative label -. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster's size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]

We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. We do not assume that the points are in general position. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers. [ABSTRACT FROM AUTHOR]

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O (n 8) and O (n 4) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O (n 2) time, i.e., when two starting points of the two tours are given as input. [ABSTRACT FROM AUTHOR]

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree δ and maximum degree Δ . We provide a linear-time algorithm for computing a cycle C ′ ≠ C of length at least n - 4 α (n + 2 α) + 8 , where α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of Δ δ = o (n) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0 < p ≤ 0.02 , if the minimum degree of G is at least 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least 1 - 1 n 50 p 4 + 1 in p o l y (n) · 2 4 p n time. This result implies that, when the minimum degree δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when δ = ω (log n) , our probabilistic algorithm works in 2 o (n) time. [ABSTRACT FROM AUTHOR]

Inter-Domain Path Computation under Node-Defined Domain Uniqueness Constraint (IDPC-NDU) is one of the routing cost optimization problems in multi-domain networks that has been proposed and received much attention by researchers. Because the IDPC-NDU is NP-Hard, the approaches using approximation algorithms are frequently used. These approximation algorithms often construct solutions based on connecting edges between adjacent domains, with little consideration of edges between non-adjacent domains. Furthermore, this study investigates how to combine an algorithm with the capability of exploration with another algorithm with the capability of exploiting in order to balance the ability to explore and exploit the search space. As a result, based on new encoding and decoding solution methods, this study proposes combinations of the algorithms Multi-start Method and Variable Neighbourhood Search Method. By considering the inter-domain edges connecting non-adjacent domains, the new encoding and decoding methods help to examine more possible paths between the source node and the destination node. The proposed algorithm is evaluated by comparing it to the most recent algorithms that were proposed to solve the IDPC-NDU. Analysis of experimental results on various instances shows that the proposed algorithm exceeds other algorithms in most of the experimental cases. In particular, one-fifth of the test cases on which the proposed algorithm finds the optimal solution. Besides, the study also analyses the influence of the attributes of the input data on the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm to obtain the sampling factors to model any frequency partitioning so that it is realized using low complexity rational decimated non-uniform filter banks (RDNUFBs). The proposed algorithm is employed to approximate the Bark scale to find a rational frequency partitioning that can be realized using RDNUFBs with less approximation error. The proposed Bark frequency partitioning is found to reduce the average deviation in centre frequency and bandwidth by 65.04% and 48.50%, respectively, and root-mean-square bandwidth deviation by 54.46% when compared to those of the existing perceptual wavelet approximation of Bark scale. In the first filter bank design approach discussed in the paper, a near-perfect reconstruction partially cosine modulated filter bank is employed to obtain the improved Bark frequency partitioning. In the second design approach, the hardware complexity of the PCM-based RDNUFB is reduced by deriving the channels with different sampling factors from the same prototype filter by the method of channel merging. There is a considerable reduction of 40.83% in the number of multipliers when merging of partially cosine modulated channels is employed. It is also found that both the proposed approaches can reduce the delay by 95.17% when compared to the existing rational tree approximation methods and hence, are suitable for real-time applications. [ABSTRACT FROM AUTHOR]

The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a (4 / 3 + ε) -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a 4 / 3 -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below 4 3 for a nontrivial class of TAP/CAP instances. [ABSTRACT FROM AUTHOR]

A λ $\lambda $‐backbone coloring of a graph G $G$ with its subgraph (also called a backbone) H $H$ is a function c:V(G)→{1,...,k} $c:V(G)\to \{1,\ldots ,k\}$ ensuring that c $c$ is a proper coloring of G $G$ and for each {u,v}∈E(H) $\{u,v\}\in E(H)$ it holds that |c(u)−c(v)|≥λ $|c(u)-c(v)|\ge \lambda $. In this paper we propose a way to color cliques with tree and forest backbones in linear time that the largest color does not exceed max{n,2λ}+Δ(H)2⌈logn⌉ $\max \{n,2\lambda \}+{\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil $. This result improves on the previously existing approximation algorithms as it is (Δ(H)2⌈logn⌉) $({\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil)$‐absolutely approximate, that is, with an additive error over the optimum. We also present an infinite family of trees T $T$ with Δ(T)=3 ${\rm{\Delta }}(T)=3$ for which the coloring of cliques with backbones T $T$ requires at least max{n,2λ}+Ω(logn) $\max \{n,2\lambda \}+{\rm{\Omega }}(\mathrm{log}n)$ colors for λ $\lambda $ close to n2 $\frac{n}{2}$. The construction draws on the theory of Fibonacci numbers, particularly on Zeckendorf representations. [ABSTRACT FROM AUTHOR]

A novel and efficient modeling approach has been developed for simulating the responses of triaxial induction logging (TIL) in layered biaxial anisotropic (BA) formations. The core of this innovative technique lies in analytically calculating the primary fields within a homogeneous medium and approximating the scattered fields within layered formations. The former involves employing a two-level subtraction technique. Initially, the first-level subtraction entails altering the direction of the Fourier transform to mitigate the integral singularity of the spectral fields, particularly in high-angle and horizontal wells. Conversely, the second-level subtraction aims to further optimize integral convergence by creating an equivalent unbounded transverse isotropic (TI) formation and eliminating the corresponding spectral fields. With the two-level subtractions, the convergence of the spectral field has been enhanced by more than six orders of magnitude. Additionally, a strict recursive algorithm and approximation method are developed to compute the scattered fields in layered biaxial anisotropic media. The rigorous algorithm is based on a modified amplitude propagator matrix (MAPM) approach and serves as the benchmark for the approximation method. In contrast, the approximation method exploits the similarity between the spectral scattered field of the TI medium and the BA medium, establishing corresponding equivalent layered TI models for each magnetic component. Since the scattered field in TI models only involves a one-dimensional semi-infinite integral, the computational complexity is significantly reduced. Numerical simulation examples demonstrate that the new simulation method is at least two orders of magnitude faster than the current modeling approach while maintaining computational precision error within 0.5%. This significantly improved simulation efficiency provides a solid foundation for expediting the logging data processing. [ABSTRACT FROM AUTHOR]

Optimization of conflicting functions is of paramount importance in decision making, and real world applications frequently involve data that is uncertain or unknown, resulting in multi-objective optimization (MOO) problems of stochastic type. We study the stochastic multi-gradient (SMG) method, seen as an extension of the classical stochastic gradient method for single-objective optimization. At each iteration of the SMG method, a stochastic multi-gradient direction is calculated by solving a quadratic subproblem, and it is shown that this direction is biased even when all individual gradient estimators are unbiased. We establish rates to compute a point in the Pareto front, of order similar to what is known for stochastic gradient in both convex and strongly convex cases. The analysis handles the bias in the multi-gradient and the unknown a priori weights of the limiting Pareto point. The SMG method is framed into a Pareto-front type algorithm for calculating an approximation of the entire Pareto front. The Pareto-front SMG algorithm is capable of robustly determining Pareto fronts for a number of synthetic test problems. One can apply it to any stochastic MOO problem arising from supervised machine learning, and we report results for logistic binary classification where multiple objectives correspond to distinct-sources data groups. [ABSTRACT FROM AUTHOR]

With the progress in Global Navigation Satellite Systems (GNSS) technology, accurate geoid modelling has started to play an essential role in geodetic applications such as establishing height datum as a continuous surface model and related vertical control for infrastructure projects. Thus, numerous geoid modelling methods have been offered since 1990's, each of them has its own algorithm and approximation theories. Classical Stokes-Helmert is one of the most well-known methods all over the world by geodetic communities. However, a user-friendly software package of the method is not publicly accessible on the Internet. Therefore, a compact and user-friendly software package "CSHSOFT" is developed and presented for scholars in this field. A fractionated programming strategy has been treated to build individual components striving high accuracy and computational efficiency for geoid heights. Subsequently, the CSHSOFT is simply tested to construct a geoid model in the mountainous area in Auvergne test-bed where several geoid modelling techniques are implemented. Afterward, the new geoid model of the region is externally evaluated by GNSS-levelling data in terms of rigorous orthometric heights. The fitting statistics of 2.75 cm and 0.36 ppm in absolute and relative height differences fairly indicate that the CSHSOFT is a vigorous tool for gravimetric geoid modelling, and can be comfortably employed for geoscientific and technical studies. [ABSTRACT FROM AUTHOR]

Due to Prolonged operation and external environmental factors, composite insulators may develop various defects, which can potentially lead to serious accidents in power systems. Detecting and analyzing these defects is critically important. In this study, we combine machine learning with laser‐induced breakdown spectroscopy (LIBS) to identify defects in composite insulators and obtain spectral data from both defective and nondefective samples. The Uniform Manifold Approximation and Projection algorithm was employed to reduce the dimensionality of the data, thereby enhancing detection accuracy and efficiency. Decision tree, random forest (RF), K‐nearest neighbor, and support vector machine algorithms were used to classify the dimensionality‐reduced data. The results indicate that the RF algorithm achieved the best classification performance, with accuracies of 100% and 95.46% for the training and test sets, respectively. Furthermore, the precision, recall, and F1 scores, which reflect model performance, also showed superior results with the RF algorithm. These findings suggest that the combination of LIBS technology and machine learning can rapidly and accurately detect and analyze defects in composite insulators, offering new insights and methods for defect detection in composite insulators. [ABSTRACT FROM AUTHOR]

We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks. Such algorithms (most prominently stochastic gradient descent and its variants) are used extensively in the field of deep learning. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates by such algorithms. We answer this question in the negative by proving hardness results for the problems of approximation and integration on a novel class of neural network approximation spaces. In particular, our results confirm a conjectured and empirically observed theory-to-practice gap in deep learning. We complement our hardness results by showing that error bounds of a comparable order of convergence are (at least theoretically) achievable. [ABSTRACT FROM AUTHOR]

In this study, we propose a novel cloud-edge collaborative task assignment model for smart farms that consists of a cloud server, m edge servers, and n sensors. The edge servers rely solely on solar-generated energy, which is limited, whereas the cloud server has access to a limitless amount of energy supplied by the smart grid. Each entire task from a sensor is processed by either an edge server or the cloud server. We consider the task to be unsplittable. Building on the algorithm for the multimachine job scheduling problem, we develop a corresponding approximation algorithm. In addition, we propose a new discrete heuristic based on the dwarf mongoose optimization algorithmm, named the discrete dwarf mongoose optimization algorithm, and we utilize the proposed approximation algorithm to improve the convergence speed of this heuristic while yielding better solutions. In this study, we consider task sets with heavy tasks independently, where a heavy task is a task that requires many computing resources to process. If such tasks are assigned as ordinary tasks, the assignment results may be poor. Therefore, we propose a new method to solve this kind of problem. [ABSTRACT FROM AUTHOR]

Summary: Large‐scale linear time‐invariant (LTI) dynamical systems are widely used to characterize complicated physical phenomena. Glover developed the Hankel norm approximation (HNA) algorithm for optimally reducing the system in the Hankel norm, and we study its numerical issues. We provide a remedy for the numerical instabilities of Glover's HNA algorithm caused by clustered singular values. We analyze the effect of our modification on the degree and the Hankel error of the reduced system. Moreover, we propose a two‐stage framework to reduce the order of a large‐scale LTI system given samples of its transfer function for a target degree k$$ k $$ of the reduced system. It combines the adaptive Antoulas–Anderson (AAA) algorithm, modified to produce an intermediate LTI system in a numerically stable way, and the modified HNA algorithm. A carefully computed rational approximation of an adaptively chosen degree d$$ d $$ gives us an algorithm for reducing an LTI system, which achieves a balance between speed and accuracy. [ABSTRACT FROM AUTHOR]

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n / 2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac's theorem from 1952. Dirac's theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ (G) ≤ n / 2 , the length of a longest cycle L is at least 2 δ (G) . Thus the "essential" part in finding the longest cycle is in approximating the "offset" k = L - 2 δ (G) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2 δ (G) + Ω (f (k)) . [ABSTRACT FROM AUTHOR]

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.82, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm by Agarwal and Procopiuc [Algorithmica 2002] yields an O (n log k) + (1 / ϵ) O (2 d k 1 - 1 / d log k) -time (1 + ϵ) -approximation for Euclidean k-center, where d is the dimension. We show for a closely related problem, k-supplier, the double-exponential dependence on dimension is unavoidable if one hopes to have a sub-linear dependence on k in the exponent. We also derive similar algorithmic results to the ones by Agarwal and Procopiuc for both k-center and k-supplier. We use a relatively new tool, called Voronoi separator, which makes our algorithms and analyses substantially simpler. Furthermore we consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2 O (k log k) n 2 time 3-approximation for NUkC in general metrics, and a 2 O ((k log k) / ϵ) d n time (1 + ϵ) -approximation for Euclidean NUkC. The latter time bound matches the bound for k-center. [ABSTRACT FROM AUTHOR]

Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP [ABSTRACT FROM AUTHOR]

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435–454, 1995. https://doi.org/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of 16 for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1) A 16 -approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was O (log | V (G) |) . (2) A 16 · ⌈ k / u min ⌉ -approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V , E) with edge costs c ∈ Q ≥ 0 E and edge capacities u ∈ Z ≥ 0 E , find a minimum-cost subset of the edges F ⊆ E such that the capacity of any cut in (V, F) is at least k; u min (respectively, u max ) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u max ≤ k . The previous best approximation ratio was min (O (log | V |) , k , 2 u max) . (3) A 20 -approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. The previous best approximation ratio was O (log | V (G) |) , where G denotes the input graph. [ABSTRACT FROM AUTHOR]

Confidence bands are used to estimate the likely range of the true parameter, whereas prediction bands provide an idea of the possible values of the parameter after applying a regression model. This study proposes an equation to construct confidence and prediction bands applicable to any linear or nonlinear chemometric regression model; that is, statistical methods used in analytical chemistry to establish relationships between two or more variables. The proposed equation is developed and presented as a useful tool to represent the uncertainty in estimates based on a set of data in chemical measurements. Once the set of data is adjusted as a regression model (linear, polynomial, or multivariable), the proposed equation can be used to construct confidence and prediction bands based on the adjustment equation. The proposed equation operates if the adjustment equation is continuous and derivable. The plot bands on any regression model provide a solid understanding of uncertainty assessment and have the advantage of total control and independence of algorithms and numeral approximations. [ABSTRACT FROM AUTHOR]

Reactive silica materials like vitreous silica or cristobalite were dissolved at temperatures between 100 and 220 °C for up to 7 days in NaOH lyes. The liquid and solid reaction products were analyzed chemically. Sodium water glasses with silica concentrations of up to 27 wt % and molar SiO2/Na2O ratios of up to 3.7 were obtained. The experimental data were evaluated by an approximation algorithm. The initial size reduction rates ranged between 0.1 and 7 µm h−1, depending on the temperature and the choice of starting materials. Correlations between thermodynamics and kinetics were discussed. [ABSTRACT FROM AUTHOR]

Emergency medical services (EMS) are an important part of the modern healthcare system that tries to provide timely medical care and transportation to patients to reduce morbidity and mortality. Performance evaluation of such EMS systems to determine measures such as mean service rates, dispatch probabilities, busy probabilities, and on-scene times is necessary to design effective and efficient systems. In this paper, we consider an urban EMS system that employs three types of emergency vehicles, including advanced life support (ALS), basic life support (BLS) and first responder vehicle (FRV). We consider two types of patients: type A requires ALS to be dispatched, while type B patients are expected to be served by BLS ambulances. We also consider co-located servers so ambulances of different types can be co-located at the same station. The presence of different types of servers (ambulances) and the patients with different dispatch policies, along with co-located servers, makes it applicable to a more realistic system. We first discuss a modification of the hypercube queueing model for the proposed system and then present an approximate approach for application in large EMS systems. These approaches are compared against a simulation-based model by computing server utilization, service times and on-scene time of ambulances. [ABSTRACT FROM AUTHOR]

In this paper, we study the following Minimum Cost Multicovering (MCMC) problem: Given a set of n client points C and a set of m server points S in a fixed dimensional Rd space, determine a set of disks centered at these server points so that each client point c is covered by at least k(c) disks and the total cost of these disks is minimized, where k(·) is a function that maps every client point to some nonnegative integer no more than m and the cost of each disk is measured by the \alpha th power of its radius for some constant α >0. MCMC is a fundamental optimization problem with applications in many areas such as wireless/sensor networking. Despite extensive research on this problem for about two decades, only constant approximations were known for general k. It has been a long standing open problem to determine whether a PTAS is possible. In this paper, we give an affirmative answer to this question by presenting the first PTAS for it. Our approach is based on a number of novel techniques, such as balanced recursive realization and bubble charging, and new counterintuitive insights to the problem. Particularly, we approximate each disk with a set of sub-boxes and optimize them at the subdisk level. This allows us to first compute an approximate disk cover through dynamic programming, and then obtain the desired disk cover through a balanced recursive realization procedure. [ABSTRACT FROM AUTHOR]

Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. ∙ An algorithm that for a given n-vertex graph G and integer k in time 22O(k)n2 either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than k. It also yields a (22k+1-1)-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to f(k)n2 the running times of various algorithms on graphs of cliquewidth k. Breaking the "cubic barrier" for rankwidth and cliquewidth was an open problem in the area. ∙ An algorithm that for a given n-vertex graph G and integer k in time 2O(k)n either constructs a branch decomposition of G of width at most 2k or concludes that the branchwidth of G is more than k. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021]. [ABSTRACT FROM AUTHOR]

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ϵ>0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ϵ expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ϵ-kernels of point sets, approximate nearest neighbor searching, polytope approximations, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size nO(n)/ϵ(n-1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the ℓp unit ball, this bound has been improved to 2O(n)/ϵ(n-1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, under the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter ϵ>0, we show that there exists a polytope P consisting of 2O(n)/ϵ(n-1)/2 vertices (facets) such that K⊂P⊂K(1+ϵ). This bound is optimal in the worst case up to factors of 2O(n). As an additional consequence, we obtain the fastest (1+ϵ)-approximate CVP algorithm that works in any norm, with a running time of 2O(n)/ϵ(n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1+ϵ)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2O(n)). [ABSTRACT FROM AUTHOR]

Functionally graded materials are widely used in the aerospace, nuclear, and aviation industries because of their exceptional properties. The progressive and continuous variation in elastic and thermal characteristics across its surfaces reduces thermal stress within the material and increases its endurance. To study how functionally gradient thermoelastic nanobeams interact with abrupt heat in the context of nonclassical thermoelasticity with phase delays, this study introduces a new mathematical model incorporating memory-dependent derivatives. A heat transfer equation based on memory-dependent derivatives with two delay times can be formulated by combining Eringen's assumptions, the Hamiltonian principle, and Euler–Bernoulli's theory. The analytical solutions for the domains of the system were obtained in the field of the Laplace transform. The distributions of physical fields such as temperature, displacement, deflection, and flexural moment were found numerically using an approximation algorithm. Through the discussion of the computational results and the graphical figures, the effects of effective parameters such as kernel functions, time delay, and nonlocal quantum were indicated. Moreover, a comparison of the current thermal conductivity model with existing classical and nonclassical thermal conductivity models was established to confirm the proposed model. [ABSTRACT FROM AUTHOR]

This paper demonstrates that the space of piecewise-smooth bivariate functions can be well-approximated by the space of the functions defined by a set of simple (non-linear) operations on smooth uniform tensor product splines. The examples include bivariate functions with jump discontinuities or normal discontinuities across curves, and even across more involved geometries such as a three-corner discontinuity. The provided data may be uniform or non-uniform, and noisy, and the approximation procedure involves non-linear least-squares minimization. Also included is a basic approximation theorem for functions with jump discontinuity across a smooth curve. [ABSTRACT FROM AUTHOR]

In atmospheric modeling, sub-grid parameterization is an important method for studying the topographic effects of solar radiation using high-resolution Digital Elevation Model (DEM) data. For reducing the amount of computation, some approximate methods that can lead to errors are used in existing sub-grid parameterization schemes for clear-sky direct solar radiation (SPS-CSDSR). The lack of a high-precision fast terrain occlusion algorithm (HPFTOA) remains one of the biggest constraints in this field. This study proposed an HPFTOA. It mainly uses two kinds of acceleration algorithms. One method is to use a dynamic, lossless, and fast occlusion search radius. Another way is to use the rectangular grid for calculations within the accuracy of DEM data to avoid coordinate projection conversions. The test results indicate that the HPFTOA can carry out large-scale computation based on DEM data with a resolution of 90 m. Because it rarely uses approximation algorithms and considers the curvature of the Earth, SPS-CSDSR can achieve unprecedented precision. The HPFTOA can also be used in the fields of mountain solar energy assessment, remote sensing, and telemetry, including terrain-obscuring the probe. As computer performance improves and algorithms and execution code are optimized, the application prospects will be very broad. [ABSTRACT FROM AUTHOR]

Dimension reduction is a technique used to transform data from a high-dimensional space into a lower-dimensional space, aiming to retain as much of the original information as possible. This approach is crucial in many disciplines like engineering, biology, astronomy, and economics. In this paper, we consider the following dimensionality reduction instance: Given an n-dimensional probability distribution p and an integer m < n , we aim to find the m-dimensional probability distribution q that is the closest to p, using the Kullback–Leibler divergence as the measure of closeness. We prove that the problem is strongly NP-hard, and we present an approximation algorithm for it. [ABSTRACT FROM AUTHOR]

The Industrial Internet of Things (IIoT) envisions enhanced surveillance and control for industrial applications through diverse IoT devices. However, the increasing heterogeneity of deployed end devices poses challenges to current practices, hampering overall performance as device numbers escalate. To tackle this issue, we introduce an innovative distributed power control algorithm leveraging the wireless channel's nature to approximate the centralized maximum-weight scheduling algorithm. Employing ubiquitous multi-protocol mobile devices as intermediaries, we propose a concurrent dual-hop/multi-hop backhauling strategy, improving interoperability and facilitating data relay, translation, and forwarding from end IoT devices. Our focus is directed towards addressing large-scale network stability and queue management challenges. We formulate a long-term time-averaged optimization problem, incorporating considerations of end-to-end rate control, routing, link scheduling, and resource allocation to guarantee essential network-wide throughput. Furthermore, we present a real-time decomposition-based approximation algorithm that ensures adaptive resource allocation, queue stability, and meeting Quality of Service (QoS) constraints with the highest energy efficiency. Comprehensive numerical results verify significant energy efficiency improvements across diverse traffic models, maintaining throughput requirements for both uniform and hotspot User Equipment (UE) distribution patterns. This work offers a comprehensive solution to enhance IIoT performance and address evolving challenges in industrial applications. [ABSTRACT FROM AUTHOR]

We consider the weighted completion time minimization problem for capacitated parallel machines, which is a fundamental problem in modern cloud computing environments. In our setting, the processed jobs may be of varying duration, require different resources, and be of unequal importance (weight). Each server (machine) can process multiple concurrent jobs up to its capacity. We study heuristic approaches with provable approximation guarantees and offer an algorithm that prioritizes the jobs with the smallest volume-by-weight ratio. We bound the algorithm's approximation ratio using a decreasing function of the ratio between the highest resource demand of any job and the server's capacity. Thereafter, we create a hybrid, constant approximation algorithm for two or more machines. We also develop a constant approximation algorithm for the case of a single machine. Via a numerical study and a mixed-integer linear program of the problem, we demonstrate the performance of the suggested algorithm with respect to the optimal solutions and alternative scheduling methods. We show that the suggested scheduling method can be applied to both offline and online problems that may arise in real-world settings. This research is the first, to the best of our knowledge, to propose a polynomial-time algorithm with a constant approximation ratio for minimizing the weighted sum of job completion times for capacitated parallel machines. [ABSTRACT FROM AUTHOR]

We study rectangle stabbing problems in which we are given n axis-aligned rectangles in the plane that we want to stab, that is, we want to select line segments such that for each given rectangle there is a line segment that intersects two opposite edges of it. In the horizontal rectangle stabbing problem (Stabbing), the goal is to find a set of horizontal line segments of minimum total length such that all rectangles are stabbed. In the horizontal–vertical stabbing problem (HV-Stabbing), the goal is to find a set of rectilinear (that is, either vertical or horizontal) line segments of minimum total length such that all rectangles are stabbed. Both variants are NP-hard. Chan et al. (ISAAC, 2018) initiated the study of these problems by providing constant approximation algorithms. Recently, Eisenbrand et al. (A QPTAS for stabbing rectangles, 2021) have presented a QPTAS and a polynomial-time 8-approximation algorithm for Stabbing, but it was open whether the problem admits a PTAS. In this paper, we obtain a PTAS for Stabbing, settling this question. For HV-Stabbing, we obtain a (2 + ε) -approximation. We also obtain PTASs for special cases of HV-Stabbing: (i) when all rectangles are squares, (ii) when each rectangle's width is at most its height, and (iii) when all rectangles are δ -large, that is, have at least one edge whose length is at least δ , while all edge lengths are at most 1. Our result also implies improved approximations for other problems such as generalized minimum Manhattan network. [ABSTRACT FROM AUTHOR]

In generalized malleable scheduling, jobs can be allocated and processed simultaneously on multiple machines so as to reduce the overall makespan of the schedule. The required processing time for each job is determined by the joint processing speed of the allocated machines. We study the case that processing speeds are job-dependent M ♮ -concave functions and provide a constant-factor approximation for this setting, significantly expanding the realm of functions for which such an approximation is possible. Further, we explore the connection between malleable scheduling and the problem of fairly allocating items to a set of agents with distinct utility functions, devising a black-box reduction that allows to obtain resource-augmented approximation algorithms for the latter. [ABSTRACT FROM AUTHOR]

In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time for fixed k, and it remained open the question of whether there exists a c-approximation algorithm for a constant c independent of k, that runs in FPT time. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time. [ABSTRACT FROM AUTHOR]

We consider the class of disjoint bilinear programs max { x T y ∣ x ∈ X , y ∈ Y } where X and Y are packing polytopes. We present an O (log log m 1 log m 1 log log m 2 log m 2 ) -approximation algorithm for this problem where m 1 and m 2 are the number of packing constraints in X and Y respectively. In particular, we show that there exists a near-optimal solution (x ~ , y ~) such that x ~ and y ~ are "near-integral". We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique. As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an O (log n log log n log L log log L) -approximation where L is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an O (log n log log n log L log log L) -approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance. [ABSTRACT FROM AUTHOR]

This article focuses on designing efficient iteration algorithms for nonequilibrium three‐temperature heat conduction equations, which are used to formulate the radiative energy transport problem. Based on the framework of relaxation iteration, we design a new accelerated iteration algorithm by reasonable approximation of the Jacobi matrix, according to the characteristics of the discrete scheme for the three‐temperature equations. Adopting the iteration framework, we analyze the advantages and disadvantages of several iteration algorithms commonly used in practice and the new iteration algorithm. Finally, we compare the new iteration algorithm with some other iteration algorithms by solving several nonlinear models, and show that the new algorithm can achieve significant acceleration effect. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a function f: V → {0, 1, 2, 3, 4} is a triple Roman dominating function (TRDF) of G, for each vertex v ∈ V, (i) if f (v) = 0, then v must have either one neighbour in V4, or either two neighbours in V2 ∪ V3 (one neighbour in V3) or either three neighbours in V2, (ii) if f (v) = 1, then v must have either one neighbour in V3 ∪ V4 or either two neighbours in V2, and if f (v) = 2, then v must have one neighbour in V2 ∪ V3 ∪ V4. The triple Roman domination number of G is the minimum weight of an TRDF f of G, where the weight of f is v V f (v). The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at most 4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an (2H (Δ(G) + 1) - 1)-approximation algorithm for solving the problem for any graph G, where Δ(G) is the maximum degree of G and H (d) denotes the first d terms of the harmonic series. In addition, we prove that for any ε > 0 there is no (1/4 - ε) ln |V |-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP ⊆ DTIME (|V |O(log log |V |)). [ABSTRACT FROM AUTHOR]

We study the autowave front propagation in a medium with discontinuous characteristics and the conditions for its stabilization to a stationary solution with a large gradient at the interface between media in the one-dimensional case. The asymptotic method of differential inequalities, based on constructing an asymptotic approximation of the solution, is the main method of study. We develop an algorithm for constructing such an approximation for the solution of the moving front form in a medium with discontinuous characteristics. The application of such an algorithm requires a detailed analysis of the behavior of the solution in neighborhoods of two singular points: the front localization point and the medium discontinuity point. As a result, we obtain a system of equations for the front propagation speed; this distinguishes this paper from the previously published ones. The developed algorithm can be used to describe autowave propagation in layered media. The results can also be extended to the multidimensional case. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V and edge set E , a vertex set D is a dominating set (DS) of G , if every vertex v ∈ V is either in D or adjacent to a vertex in D. If D is a DS of G and for every vertex v ∈ V ∖ D there exists a vertex u ∈ D adjacent to v such that (D ∖ { u }) ∪ { v } is also a DS of G , then D is a secure dominating set (SDS). The minimum secure dominating set problem (MinSDS) is to find an SDS of G with the minimum cardinality. In this paper, we design PTASs for MinSDS on planar graphs and growth-bounded graphs, that is, the computed solutions approximate the optimal value within factor (1 + ɛ) for any constant ɛ ∈ (0 , 1). [ABSTRACT FROM AUTHOR]