Search

We study the weak convergence of a greedy algorithm of approximation by a given set in a Banach space. It is proved that the greedy algorithm of approximation by a strongly norm-reducing set in a uniformly smooth Banach space with the WN-property weakly converges. In an arbitrary separable Banach space without the WN-property, we construct an example of a strongly norm-reducing set such that the greedy algorithm of approximation by this set does not weakly converge for some initial element. [ABSTRACT FROM AUTHOR]

For maneuvering target tracking, the interactive multiple model (IMM) algorithm and its variants have shown good performance, among which the variable structure IMM (VSIMM) algorithm is the most widely studied one. The approximation degree of the algorithm and the matching degree of the model subset will affect the performance of the VSIMM. In addition, considering that smoothing can provide better estimation of the target state, a new adaptive VSIMM filtering and smoothing (AVSIMMFS) algorithm is proposed in this paper. First, an accurate model of the VSIMM algorithm is established, in which the IMM is run in parallel with and independently from the different model subsets, and the state estimation of the model subset with the highest probability is selected as the final estimation result. Then, an adaptive VSIMM (AVSIMM) algorithm was designed based on the VSIMM algorithm. The adaptation is reflected in the construction of a new model subset from the original model subsets, which improves the matching degree between the model subset and the actual maneuvering model of the target. Finally, by smoothing the filtering data of the AVSIMM algorithm, the AVSIMMFS algorithm is obtained. Because of the combination of forward filtering and backward smoothing, the target tracking accuracy is further improved. Simulation results show that the tracking performance of the AVSIMMFS algorithm is better than that of other methods. [ABSTRACT FROM AUTHOR]

Ink classification is the ability to distinguish unknown inks into different groups, and ink source prediction is the ability to predict the manufacturer or model of an unknown ink. These are regular tasks in forensic analysis. The latter is more challenging than the former, as ink source prediction has expanded beyond ink classification. In this work, we reported on an approach to predict the source of black inks based on direct analysis in real time mass spectrometry and assess the strength of black ink source prediction conclusion via the likelihood ratio, using a dataset that included 39 inks from three manufacturers with a high market share. Most of these inks contain similar or identical chemical components. Dimensionality reduction based on the principal component analysis and unified manifold approximation and projection algorithms was implemented, and subsequently, the distribution plots illustrated the variations between and within the inks. Unified manifold approximation and projection showed significant priority in avoiding overcrowding of cluster representation versus principal component analysis, with results as high as 99.83% for the prediction of the ink source using 41,432 spectra data (70% data for training and 30% data for testing) after dimensionality reduction. A likelihood ratio was used to evaluate the strength of ink evidence, and the pool‐adjacent‐violators algorithm and logistic algorithms were used to calibrate the likelihood ratio. The results showed that the pool‐adjacent‐violators algorithm and logistic algorithms both had an excellent equal error rate of 0.004 but slightly different results in the rates of misleading evidence in favor of the prosecutor's hypothesis, rates of misleading evidence in favor of the defense's hypothesis, log likelihood ratio costs after calibration (Cllrcal), and minimum log likelihood ratio costs (Cllrmin). A blind test validated the robustness of the methods. Ink source prediction of 39 black inks based on DART‐MS method with results as high as 99.83% assessed the strength of prediction via likelihood ratio with EER = 0.004. [ABSTRACT FROM AUTHOR]

We study the Independent Set problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldórsson [SODA 1995] showed that for every δ > 0 the Independent Set problem has a polynomial-time (d - 1 2 + δ) -approximation algorithm in K 1 , d -free graphs. We extend this result by showing that K a , b -free graphs admit a polynomial-time O (α (G) 1 - 1 / a) -approximation, where α (G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldórsson by showing that for some γ = Θ (d / log d) , there is no polynomial-time γ -approximation algorithm for these graphs, unless NP = ZPP. Bonnet et al. [Algorithmica 2020] showed that Independent Set parameterized by the size k of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least 4, (2) the star K 1 , 4 , and (3) any tree with two vertices of degree at least 3 at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken conditions (1) and (2) that G does not contain a cycle of constant length at least 5 or K 1 , 5 ). First, under the ETH, there is no f (k) · n o (k / log k) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant δ > 0 such that no δ -approximation can be computed in f (k) · n O (1) time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime f (k) · n o (k) . Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, Independent Set has no n o (α (H)) algorithm in H-free graphs. Also, we prove that there is no d / k o (1) -approximation algorithm for K 1 , d -free graphs with runtime f (d , k) · n O (1) , under the deterministic Gap-ETH. [ABSTRACT FROM AUTHOR]

We study the problem of how to split many point sets in R d into smaller parts using a few (shared) splitting hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization. [ABSTRACT FROM AUTHOR]

The five-axis flank milling process of sculptured surfaces is an intricate process involving time-varying and nonlinear characteristics under the multiphysics coupling effect. The milling force during the process is an important factor that influences the machining accuracy of sculptured surfaces. Face gears, as parts with sculptured surfaces, are widely employed in the aerospace and machinery manufacturing industries. To realize the high-precision manufacturing of face gears with a universal milling machine, this study proposes a five-axis flank milling method for face gears. In addition, based on the tangent plane approximation algorithm and the Receptance Coupling Substructure Analysis (RCSA) method, the milling force and the tool tip vibration during the face gear machining process are investigated. Finally, a five-axis flank milling force model and a face gear surface machining error model are established considering the interaction between the milling force and the process system. [ABSTRACT FROM AUTHOR]

This paper aims to obtain the best shape accuracy evaluation algorithm for silicon nitride ceramic balls after lapping, and to extract the initial signal of the ball surface to improve the accuracy and reliability of the algorithm. The research methods of this paper are as follows: Firstly, an analysis of the uniform envelope of the lapping trajectory of ceramic balls is carried out to verify whether the lapping trajectory after processing can achieve a consistent envelope on the balls' surface. On this basis, it is found through experiments that the standard deviation SD between the roundness deviations of different contour sections is small. The value is maintained at approximately 0.03 μm, and the roundness deviation can approximately replace the spherical deviation. Then the different contour sections of the sphere are sampled by the Taylor roundness instrument. Considering the uncertainty, the sampling points of different contour sections are averaged and used as the original signal of the sphere surface. Then the EMD method is used to process the signal to be detected on the sphere surface. The initial signal of the sphere surface is extracted by judging whether the number of ripples Kc obtained by decomposition is greater than the critical value. Then the initial signal is used as the input value of the approximation algorithm. Through the roundness deviation approximation algorithm based on the least square method, the given minimum approximation domain range is finely processed. The divided fine points are used as the center of the circle to intersect with the initial signal. The maximum, minimum, and range of each circle are calculated to obtain the roundness error based on the minimum circumscribed circle, the maximum inscribed circle, and the minimum region method. Finally, the calculated values are compared with those obtained by the traditional algorithm. The experimental results of this paper show that the algorithm is consistent with the roundness error measured by the instrument, compared with the mainstream evaluation criteria. In summary, the conclusions can be drawn as follows: Through a large number of experimental cases and comparative experiments, the algorithm has high accuracy and reliability. The research results of this paper have essential reference significance for accurately evaluating the shape accuracy of ceramic balls in actual production. [ABSTRACT FROM AUTHOR]

Parameter servers (PSs) placement is one of the most important factors for global model training on distributed deep learning. This paper formulates a novel problem for placement strategy of PSs in the dynamic available storage capacity, with the objective of minimizing the training time of the distributed deep learning under the constraints of storage capacity and the number of local PSs. Then, we provide the proof for the NP-hardness of the proposed problem. The whole training epochs are divided into two parts, i.e. the first epoch and the other epochs. For the first epoch, an approximation algorithm and a rounding algorithm are proposed in this paper, to solve the proposed problem. For the other epochs, an adjustment algorithm is proposed, by continuously adjusting the decisions for placement strategy of PSs to decrease the training time of the global model. Simulation results show that the proposed approximation algorithm and rounding algorithm perform better than existing works for all cases, in terms of the training time of global model. Meanwhile, the training time of global model for the proposed approximation algorithm is very close to that for optimal solution generated by the brute-force approach for all cases. Besides, the integrated algorithm outperforms the existing works when the available storage capacity varies during the training. [ABSTRACT FROM AUTHOR]

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f + ε) . Let Δ denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires O (log Δ / log log Δ) rounds, for constants ε ∈ (0 , 1 ] and f ∈ N + . This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and ε , our algorithm improves over the (f + ε) -approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is O (log Δ + log W) , where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in O (f log n) rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of O (f log 2 n) . Finally, for weighted vertex cover ( f = 2 ) our algorithm achieves a deterministic running time of O (log n) , matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (f ⌈ log 2 (M) + 1 ⌉ + ε) -approximate integral solution in O (1 + f / log n) · log Δ log log Δ + (f · log M) 1.01 · log ε - 1 · (log Δ) 0.01 rounds, where f bounds the number of variables in a constraint, Δ bounds the number of constraints a variable appears in, and M = max 1 , ⌈ 1 / a min ⌉ , where a min is the smallest normalized constraint coefficient. [ABSTRACT FROM AUTHOR]

Logistic regression is commonly used to estimate the association of one (or more) independent variable(s) with a binary- dependent outcome. In many applications latent sources are both spatially dependent and non-Gaussian; thus, it is desirable to exploit both properties jointly. Spatial logistic regression is a well-established technique of including spatial dependence in logistic regression models. In this paper, we develop a spatial logistic regression model based on a valid skew-Gaussian random field. For parameter estimation, we use a Monte Carlo extension of the EM algorithm along with an approximation based on the standard logistic function. A simulation study is applied in order to determine the performance of the proposed model and also to compare the results with a recently introduced model with established efficiency. The identifiability of the parameters is investigated as well. As an illustrative purpose, an application to the Meuse heavy metals dataset is presented. Supplementary materials accompanying this paper appear online. [ABSTRACT FROM AUTHOR]

In graph theory, a "dominating vertex set" is a subset of vertices in a graph such that every vertex in the graph is either a member of the subset or adjacent to a member of the subset. In other words, the vertices in the dominating set "dominate" the remaining vertices in the graph. Dominating vertex sets are important in graph theory because they can help us understand and analyze the behavior of a graph. For example, in network analysis, a set of dominant vertices may represent key nodes in a network that can influence the behavior of other nodes. Identifying dominant sets in a graph can also help in optimization problems, as it can help us find the minimum set of vertices that can control the entire graph. Now that there are theories about vagueness, it is important to define parallel ideas in vague structures, such as intuitionistic fuzzy graphs. This paper describes a better way to find dominating vertex sets (DVSs) in intuitive fuzzy graphs (IFGs). Even though there is already an algorithm for finding DVSs in IFGs, it has some problems. For example, it does not take into account the vertex volume, which has a direct effect on how DVSs are calculated. To address these limitations, we propose a new algorithm that can handle large-scale IFGs more efficiently. We show how effective and scalable the method is by comparing it to other methods and applying it to water flow. This work's contributions can be used in many areas, such as social network analysis, transportation planning, and telecommunications. [ABSTRACT FROM AUTHOR]

We present BonnLogic , a timing optimization framework that replaces critical paths by logically equivalent realizations with less delay. Our tool allows to revise early decisions on the logical structure of the netlist in late physical design. The core routine of our framework is a new algorithm that constructs delay-optimized circuits for alternating And - Or paths with prescribed input arrival times. It is a sophisticated dynamic programming algorithm which is a common generalization of the previously best approaches. In contrast to all earlier methods, we avoid fixing the structure of sub-solutions before deciding on how to combine them, significantly expanding the search space of the algorithm. Our algorithm provably fulfills the best known approximation guarantees, almost always computes delay-optimum solutions, and empirically outperforms all previous approaches. In addition, we show how any algorithm for And - Or paths optimization which is restricted to integral arrival times can be generalized to fractional arrival times with the same guarantees on the delay. The reduction to And - Or path optimization allows us to optimize general combinatorial paths of arbitrary length in our logic restructuring framework BonnLogic. The framework is applied successfully as a late step in an industrial physical design flow. Experiments demonstrate the effectiveness of BonnLogic on industrial 7 nm instances. • We describe a new dynamic program for delay optimization of extended And - Or Paths. • We extend any And - Or paths optimization from integral to fractional arrival times. • On more than 95% of our test instances, our algorithm finds a delay-optimum circuit. • We propose BonnLogic , a framework for timing optimization of logic paths. • Experiments on recent 7nm chips show the effectiveness of BonnLogic. [ABSTRACT FROM AUTHOR]

Set-valued optimization using the set approach is a research topic of high interest due to its practical relevance and numerous interdependencies to other fields of optimization. However, it is a very difficult task to solve these optimization problems even for specific cases. In this paper, we study set-valued optimization problems and develop a multiobjective optimization problem that is strongly related to it. We prove that the set of weakly minimal solutions of this subproblem is closely related to the set of weakly minimal elements of the set-valued optimization problem and that these sets can get arbitrarily close in a certain sense. Subsequently, we introduce a concept of approximations of the solution set of the set-valued optimization problem. We define a quality measure in the image space that can be used to compare finite approximations of this kind and outline a procedure to enhance a given approximation. We conclude the paper with some numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose and investigate two new kernel regression estimators based on a bias reduction transformation technique. We study the properties of these estimators and compare them with Nadaraya–Watson's regression estimator and Slaoui's (2016) regression estimator. It turns out that, with an adequate choice of the parameters of the two proposed estimators, the rate of convergence of two estimators will be faster than the two classical estimators, and the asymptotic MISE (mean integrated squared error) will be smaller than the two classical estimators. We corroborate these theoretical results through simulations and a real Malaria dataset. [ABSTRACT FROM AUTHOR]

We introduce a new method for Estimation of Signal Parameters based on Iterative Rational Approximation (ESPIRA) for sparse exponential sums. Our algorithm uses the AAA algorithm for rational approximation of the discrete Fourier transform of the given equidistant signal values. We show that ESPIRA can be interpreted as a matrix pencil method (MPM) applied to Loewner matrices. These Loewner matrices are closely connected with the Hankel matrices that are usually employed for signal recovery. Due to the construction of the Loewner matrices via an adaptive selection of index sets, the MPM is stabilized. ESPIRA achieves similar recovery results for exact data as ESPRIT and the MPM, but with less computational effort. Moreover, ESPIRA strongly outperforms ESPRIT and the MPM for noisy data and for signal approximation by short exponential sums. [ABSTRACT FROM AUTHOR]

We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements { ke Z + : e Ⲉ E}, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when ke and many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ke = 1) of Min Sum Set Cover (MSSC) studied by Feige, Lovász, and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., | e| = 2) and ke = 1 for every edge e E. We give a 16/9 ≃ 1.778 approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the lp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of (p + 1)1+1/p for all p ≥ 1, giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC. [ABSTRACT FROM AUTHOR]

In the directed Steiner tree (DST) problem, we are given an n-vertex directed edgeweighted graph, a root r, and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log² k/ log log k)- approximation algorithm for DST that runs in quasi-polynomial time, i.e., in time n poly log(k) . By assuming the projection game conjecture and NP ¢n0<ε<1 ZPTIME(2nε ) and adjusting the parameters in the hardness result of [Halperin and Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585--594], we show the matching lower bound of Ω (log² k/ log log k) for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. Our algorithm is proceeded by reducing DST to an intermediate problem, namely, the group Steiner tree on trees with dependency constraint problem, which we approximate using the framework developed by [Rothvo{\ss}, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arxiv:1111.5473, 2011] and [Friggstad et al., Linear programming hierarchies suffice for directed Steiner tree, in Proceedings of the 17th Annual Conference on Integer Programming and Combinatorial Optimization, 2014, pp. 285--296]. [ABSTRACT FROM AUTHOR]

Abstract. In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits a (1 + (1))-approximation 9(n)-time algorithm and a nearly tight 12(n) lower bound [D. Nanongkai, STOC'14, ACM, New York, 2014, pp. 565-573; C. Lenzen and B. Patt-Shamir, PODC'15, ACM, New York, 2015, pp. 153-162]. (9, 0 and n hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios (C. Lenzen and D. Peleg, PODC, ACM, New York, 2013, pp. 375-382; S. Holzer and R. Wattenofer, PODC, ACM, New York, 2012, pp. 355-364; D. Peleg, L. Roditty, and E. Tal, ICALP, Springer, Berlin, 2012, pp. 660-672; D. Nanongkai, STOC, ACM, New York, 2014, pp. 565-573-672). For the exact case, Elkin [STOC'17, ACM, New York, 2017, pp. 757-790] presented an 0(n5/3 log2/3 n) time bound, which was later improved to O(n5/4) [C.-C. Huang, D. Nanongkai, T. Saranurak, FOCS'17, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 168-179]. It was shown that any superlinear lower bound (in n) requires a new technique [K. Censor-Hillel, S. Khoury, A. Paz, DISC'17, LIPIcs Leibniz Int. Proc. Inform., Vol. 91, Schloss-Dagstuhl, Wadern, Germany, 2017, 10], but otherwise it remained widely open whether there exists a O(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) 0(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous 0(n5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous 0(n5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ..., poly(n)}). As far as we know, ours is the first o(n²) algorithm that only requires unidirectional communication. For arbitrary weights, the previous state-of-the-art required 0(n4/3) time [U. Agarwal and V. Ramachandran, IPDPS 2019, IEEE Computer Society, Los Alamitos, CA, 2019, and SPAA 2020, ACM, New York, 2020, pp. 11-21]. Our algorithm is extremely simple and relies on a new technique called random filtered broadcast. Given any sets of nodes A, B C V and assuming that every b E B knows all distances from nodes in A, and every node v E V knows all distances from nodes in B, we want every v E V to know DistThroughB (a, v) = minbEB dist(a, b) + dist(b, v) for every a E A. Previous works typically solve this problem by broadcasting all knowledge of every b E B, causing superlinear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in 0(n) expected time. [ABSTRACT FROM AUTHOR]

This paper presents a tensor approximation algorithm, based on the Levenberg–Marquardt method for the nonlinear least square problem, to decompose large-scale tensors into the sum of the products of vector groups of a given scale, or to obtain a low-rank tensor approximation without losing too much accuracy. An Armijo-like rule of inexact line search is also introduced into this algorithm. The result of the tensor decomposition is adjustable, which implies that the decomposition can be specified according to the users' requirements. The convergence is proved, and numerical experiments show that it has some advantages over the classical Levenberg–Marquardt method. This algorithm is applicable to both symmetric and asymmetric tensors, and it is expected to play a role in the field of large-scale data compression storage and large-scale tensor approximation operations. [ABSTRACT FROM AUTHOR]

• We introduce a new similarity measure for rooted, unordered, node-labeled trees. • We present an exact solver as well as a scalable 4-approximation algorithm. • We validate our approach using molecular trees and RNA secondary structures. Rooted trees are ubiquitous data structures which are used to model hierarchical objects from a plethora of different application domains. For various downstream analysis tasks, measures are needed that quantify (dis-)similarity between rooted trees. Many such measures exist, e. g., the widely used tree edit distance (TED). However, there are few algorithms to compute (dis-)similarity measures which are specifically designed for rooted, unordered, node-labeled trees and support input trees of different orders. To close this gap in the literature, we introduce the edge-preservation similarity (EPS). We show how to exactly compute EPS via integer quadratic programming on small instances and present a scalable 4-approximation algorithm. An evaluation on tree representations of pseudoknotted RNA secondary structures and acyclic molecular graphs shows that both exact and approximate (normalized) EPS better preserves functional similarities between the compared RNAs and molecules than the often-used TED. Python implementations of our algorithms and scripts to reproduce the results are available on GitHub: https://github.com/bionetslab/edge-preservation-similarity. [ABSTRACT FROM AUTHOR]

We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear programming formulation. In addition, we show this linear program has a smaller integrality gap than previously known formulations, and we give an equivalent compact formulation, showing that it can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W 1 ≤ ⋯ ≤ W T . When item i is inserted at time t, we gain a profit of p it ; however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time (1 2 - ϵ) -approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys–Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we turn our algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard. [ABSTRACT FROM AUTHOR]

Two methods are presented for finding the top‐k items in data streams using Field Programmable Gate Arrays (FPGAs). These methods deploy two variants of a novel accelerator architecture capable of extracting an approximate list of the topmost frequently occurring items in a single pass over the input stream without the need for random access. The first variant of the accelerator implements the well‐known Probabilistic sampling algorithm by mapping its main processing stages to a hardware architecture consisting of two custom systolic arrays. The proposed architecture retains all the properties of this algorithm, which works even if the stream size is unknown at run time. The architecture shows better scalability compared to other architectures that are based on other stream algorithms. In addition, experimental results on both synthetic and real datasets, when implementing the accelerator on an Intel Arria 10 GX 1150 FPGA device, showed very good accuracy and significant throughput gains compared to the existing software and hardware‐accelerated solutions. The second variant of the accelerator is specifically tailored for applications requiring higher accuracy, provided that the size of the stream is known at run time. This variant takes advantage of the embedded memory resources in an FPGA to implement a sketch‐based filter that precedes the main systolic array in the accelerator's pipeline. This filter enhances the accuracy of the accelerator by pre‐processing the stream to remove much of the insignificant items, allowing the accelerator to process a significantly smaller filtered stream. [ABSTRACT FROM AUTHOR]

Sliced inverse regression (SIR) is a recommended method to identify and estimate the central dimension reduction (CDR) subspace. CDR subspace is at the base to describe the conditional distribution of the response Y given a d-dimensional predictor vector X. To estimate this space, two versions are very popular: the slice version and the kernel version. A recursive method of the slice version has already been the subject of a systematic study. In this paper, we propose to study the kernel version. It's a recursive method based on a stochastic approximation algorithm of the kernel version. The asymptotic normality of the proposed estimator is also proved. A simulation study that not only shows the good numerical performance of the proposed estimate and which also allows to evaluate its performance with respect to existing methods is presented. A real dataset is also used to illustrate the approach. [ABSTRACT FROM AUTHOR]

The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b -matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the k -degenerate graphs, whose approximation ratios are α + 2 k − 2 and α k , where α is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an (α + k) -approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are k -systems with independence oracles. [ABSTRACT FROM AUTHOR]

A fuzzy equivalence relation can be used for clustering. But when using it in applications, we often get a similarity relation rather than an equivalence one because of various reasons. We need to reform it into an equivalence relation close to it to cluster. A commonly used method is transitive closure method, but it usually results in serious distortions about the relation. This paper further studies fuzzy similarity and equivalence relations using fuzzy graphs, and obtains some new results. The defects of transitive closure method are analyzed, and an improved clustering algorithm is given, but it cannot eliminate the inconsistency phenomenon in classification hierarchy structure. To solve this problem, the optimal fuzzy equivalence relation of similarity relation is studied. An optimization model which can derive it exactly is given, but it is too complex for applications. An effective approximation algorithm to get the optimal equivalence relation is thus presented. Several examples and some discussions are also given to illustrate the given methods. [ABSTRACT FROM AUTHOR]

Due to the nonlinearities and dynamical properties of multisection web machines, it is essential to accomplish an appropriate mathematical model as well as design a compatible control scheme. A generalized fully driven web winding model is constructed taking unpredictable changes of moment of inertia and radius of rolls into consideration. In this article, a fractional‐order sliding surface algorithm‐based hierarchical control frame is applied to multisection web machines to deal with matched and mismatched uncertainties and disturbances. In addition, the Radius Basis Function neural network is deployed to estimate necessary system dynamics and the proposed control scheme taking advantage of first‐order low‐pass filters to produce virtual control signals without complicated calculation and attenuate the explosion of terms phenomenon. Finally, the semi‐global stability of the entire system is determined using Lyapunov's stability theory. The simulation results are presented to clarify the superior performance of robust control algorithm and approximation law in the presence of nonideal elements. [ABSTRACT FROM AUTHOR]

In this paper, under some new appropriate conditions imposed on the parameter and mappings involved in the resolvent operator associated with an (H; η)-monotone operator, its Lipschitz continuity is proved and an estimate of its Lipschitz constant is computed. This paper is also concerned with the establishment of a new equivalence relationship between the graph convergence of a sequence of (H; η)-monotone operators and their associated resolvent operators, respectively, to a given (H; η)-monotone operator and its associated resolvent operator. A new iterative scheme for approximating a common element of the set of solutions of a variational inclusion problem and the set of fixed points of a given total asymptotically nonexpansive mapping is constructed. As an application of the obtained equivalence conclusion concerning graph convergence, under some suitable conditions, the strong convergence of the sequence generated by our suggested iterative algorithm to a common element of the above-mentioned two sets is proved. Our results improve and generalize the corresponding results of recent works. [ABSTRACT FROM AUTHOR]

This article proposes a lateral vehicle trajectory planning and control algorithm using a model predictive control (MPC) scheme for an automated perpendicular parking system. Previous work showed that approximated clothoid-based local path planning using a virtual towing distance provides low computational time and the stability of lateral vehicle motion in a parking system. However, this approach cannot function in certain parking situations and may cause undesirable steering maneuvers due to state-dependent planning. We present a new approximated clothoid path based on lateral vehicle kinematics to cope with these problems. Using the proposed kinematic model, we formulate an MPC problem for path planning. Then, the proposed lateral vehicle trajectory planning becomes an MPC problem under constraints. Besides, we show that lateral vehicle motion for vertical parking can be implemented using simple kinematic lateral motion control. Experimental results show that the vehicle with the proposed method moves smoothly and completes the given parking mission under constraints, even under tight parking space conditions. [ABSTRACT FROM AUTHOR]

The single facility location problem in multiple regions with different norms (SMDN) generalizes the well-known Weber Problem. The SMDN consists of finding the optimum location of a single facility in the plane which is partitioned into multiple regions where the distance to travel in each region is measured or approximated with different norms. In this study, we specifically focus on the SMDN considering three regions with either rectilinear or Euclidean norms. We first introduce some analytical properties of this problem. Then, we devise a specially tailored branch-and-bound algorithm, i.e. a Big Square Small Square algorithm (BSSS), and two heuristics, named as Discrete Approximation algorithm (DA) and Modified Weiszfeld procedure (MW). The performance of the proposed approaches are tested using both standard test instances from the literature and randomly generated instances. According to our extensive computational experiments, the BSSS stands out to be a suitable exact solution approach in terms of both accuracy and efficiency when commercial mixed integer nonlinear solvers are not applicable. Besides, we also observe that the DA yields quite accurate solutions at the expense of high computation times while the MW arises to be the most efficient method with the least accuracy. [ABSTRACT FROM AUTHOR]

Given a set S of n points, a weight function w to associate a non-negative weight to each point in S, a positive integer k ≥ 1 , and a real number > 0 , we devise the following algorithms to compute a k-vertex fault-tolerant spanner network G (S , E) for the metric space induced by the weighted points in S: (1). When the points in S are located in a simple polygon, we present an algorithm to compute G with multiplicative stretch 1 0 + , and the number of edges in G (size of G) is O (k n (lg n) 2). (2) When the points in S are located in the free space of a polygonal domain with h number of obstacles, we present an algorithm to compute G with multiplicative stretch 6 + and size O (h k n (lg n) 2). (3) When the points in S are located on a polyhedral terrain, we devise an algorithm to compute G with multiplicative stretch 6 + and size O (k n (lg n) 2). [ABSTRACT FROM AUTHOR]

The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f (k) ⋅ n O 휖 (1) that outputs a solution with at most (1 + 휖)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + 휖 in the cost of the selected tasks. [ABSTRACT FROM AUTHOR]

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result the approximation guarantee for weighted instances did not match the factor 2 achieved by the greedy algorithm for unweighted instances.Our main result closes this gap by developing a semi-streaming algorithm with an approximation guarantee of 2 + ε for weighted matroid intersection, improving upon the previous best guarantee of 4 + ε . Our techniques also allow us to generalize recent results by Levin and Wajc on submodular maximization subject to matching constraints to that of matroid-intersection constraints. While our algorithm is an adaptation of the local ratio technique used in previous works, the analysis deviates significantly and relies on structural properties of matroid intersection, called kernels. Finally, we also conjecture that our algorithm gives a (k + ε) approximation for the intersection of k matroids but prove that new tools are needed in the analysis as the structural properties we use fail for k ≥ 3 . [ABSTRACT FROM AUTHOR]

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527–542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149–158, 1987). [ABSTRACT FROM AUTHOR]

We consider the graph k-partitioning problem under the min-max objective, termed as Minmax k -cut. The input here is a graph G = (V , E) with non-negative integral edge weights w : E → Z + and an integer k ≥ 2 and the goal is to partition the vertices into k non-empty parts V 1 , ... , V k so as to minimize max i = 1 k w (δ (V i)) . Although minimizing the sum objective ∑ i = 1 k w (δ (V i)) , termed as Minsum k -cut, has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of Minmax k -cut by showing that it is NP-hard and W[1]-hard when parameterized by k, and design a parameterized approximation scheme when parameterized by k. The main ingredient of our parameterized approximation scheme is an exact algorithm for Minmax k -cut that runs in time (λ k) O (k 2) n O (1) + O (m) , where λ is value of the optimum, n is the number of vertices, and m is the number of edges. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for Minsum k -cut. Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing ℓ p -norm measures of k-partitioning for every p ≥ 1 . [ABSTRACT FROM AUTHOR]

We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by d. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding a minimum-weight vertex cover in a d-partite hypergraph. Next, we study the natural LP relaxation, which can be solved in polynomial time for fixed d and—for time-cost tradeoff instances—up to an arbitrarily small error in general. Improving on prior work of Lovász and of Aharoni, Holzman and Krivelevich, we describe a deterministic algorithm with approximation ratio slightly less than d 2 for minimum-weight vertex cover in d-partite hypergraphs for fixed d and given d-partition. This is tight and yields also a d 2 -approximation algorithm for general time-cost tradeoff instances, even if d is not fixed. We also study the inapproximability and show that no better approximation ratio than d + 2 4 is possible, assuming the Unique Games Conjecture and P ≠ NP . This strengthens a result of Svensson [21], who showed that under the same assumptions no constant-factor approximation algorithm exists for general time-cost tradeoff instances (of unbounded depth). Previously, only APX-hardness was known for bounded depth. [ABSTRACT FROM AUTHOR]

Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i) to allow some bounded edge congestion in solutions, (ii) to only consider the unit weight (cardinality) setting, (iii) to only require fractional routability of the selected demands (the all-or-nothing flow setting). For the general form (no congestion, general weights, integral routing) of edge-disjoint paths (edp) even the case of unit capacity trees which are stars generalizes the maximum matching problem for which Edmonds provided an exact algorithm. For general capacitated trees, Garg, Vazirani, Yannakakis showed the problem is APX-Hard and Chekuri, Mydlarz, Shepherd provided a 4-approximation. This is essentially the only setting where a constant approximation is known for the general form of edp. We extend their result by giving a constant-factor approximation algorithm for general-form edp in outerplanar graphs. A key component for the algorithm is to find a single-treeO(1) cut approximator for outerplanar graphs. Previously O(1) cut approximators were only known via distributions on trees and these were based implicitly on the results of Gupta, Newman, Rabinovich and Sinclair for distance tree embeddings combined with results of Anderson and Feige. [ABSTRACT FROM AUTHOR]

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem. [ABSTRACT FROM AUTHOR]

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]

Diameter—the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O (n 1.99) -time algorithm even in sparse graphs (Roditty L, Williams, VV in Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC '13), pp 515–524. ACM, 2013). To circumvent this lower bound, we investigate which parameters allow for running times of the form f (k) (n + m) where k is the respective parameter and f is a computable function. To this end, we systematically explore a hierarchy of structural graph parameters. [ABSTRACT FROM AUTHOR]

We consider a variant of the k-center clustering problem in I R d , where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that p + q = k , and each red center and each blue center must be a distance of at least some given α ≥ 0 apart. The aim is to minimize the covering radius. We provide a bi-criteria approximation algorithm for the problem and a polynomial time algorithm for the constrained problem where all centers must lie on a given line ℓ. Additionally, we present a polynomial time algorithm for the case where only the orientation of the line is fixed in the plane ( d = 2 ), although the algorithm works even in I R d by constraining the line to lie in a plane and with a fixed orientation. [ABSTRACT FROM AUTHOR]

Supersaturation of dissolved gas in water will cause fish to suffer from gas bubble diseases and even death. Therefore, it is imperative to illustrate the dissipation process of dissolved gas and then seek measures to remit the negative effects of dissolved gas supersaturation on fish. Generally, adding solid media (SM) to water has proven to be an effective and economical way to remove supersaturated dissolved gas from aquaculture water. While, the supersaturated dissolved gas dissipation framework in solid media containing water was still unclear. In this paper, combined with laboratory experiments and research available in the literature, the dissipation framework of dissolved gas was proposed along with the calculation of the liquid gas interfacial transfer mass, solid wall adsorption mass, porous media adsorption mass, and inner dissipation mass. The solid wall adsorption coefficient was found to follow a power function of the contact angle, and the porous adsorption coefficient logarithmically increased with the specific surface area. It was found that the inner dissipation coefficient exponentially increased with increasing total dissipation coefficient. Utilizing an approximation algorithm method, a model for the prediction of the dissipation coefficient was established. The research reported in this paper could contribute to enriching the research field of supersaturated dissolved dissipation and is significant for ecological and environmental protection. [Display omitted] [ABSTRACT FROM AUTHOR]

We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is 4 3 , which matches the current best ratio. The approximation ratio of the algorithm is 6 5 on subcubic graphs, which is an improvement upon the previous best ratio of 5 4. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches. [ABSTRACT FROM AUTHOR]

The squared metric k -facility location problem is a frequently encountered generalization of the k -means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44.473 + ϵ , which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36.342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric. • We give a (36.342 + ϵ) -approximation algorithm for the squared metric k -facility location problem. • We obtain a well-behaved fractional solution to the squared metric k -facility location problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach that exploits the properties of the squared metric. [ABSTRACT FROM AUTHOR]

This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k -Path Splitting Exact Cover (k-PSEC). Both problems receive a digraph G and a set P of paths in G , and their objective is to find a minimum cardinality set S of paths, whose elements are arc-disjoint and cover all arcs of G. Despite the similarities, the solutions for each problem must satisfy different properties. For k-PSEC , the set S must be obtained by splitting the paths in P in order to guarantee that no element of S has length greater than a given integer k. For PCEC , the paths in P cannot be split, and the elements of S are single arcs of G or complete paths of P. PCEC and k-PSEC have practical applications in network design and network monitoring systems, being also natural versions of graph covering problems. However, there are no theoretical studies on their complexity. This work not only presents NP-hardness results for the problems, but also proves that, unless P = NP , PCEC cannot be | P | O (1) -approximated in polynomial-time. Moreover, polynomial-time algorithms are presented for paths, cycles, and trees, and polynomial-time approximation algorithms are proposed for special cases of k-PSEC. [ABSTRACT FROM AUTHOR]

Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least 2 1 / α for the hard-core model on bipartite α -expanders. [ABSTRACT FROM AUTHOR]

Dominance-based rough set approach (DRSA) is an effective knowledge acquisition tool for ordered data, and to meet the needs of practical applications, the DRSA-based extended models have been widely studied. Nevertheless, the collected data in practical applications are always polluted by noise and most of these extended models are very susceptible to noise. In addition, with the arrival of new attributes and the removal of obsolete attributes, the ordered data have the characteristic of attributes evolving over time (i.e., dynamic ordered data). How to efficiently mining knowledge from dynamic ordered data is a meaningful topic. Motivated by these two issues, we first propose a robust fuzzy dominance rough set model to combat noise interference and then develop incremental update approximation mechanisms based on the proposed model for dynamic ordered data. Firstly, the vaguely quantified fuzzy dominance rough set (VQFDRS) and its matrix representation are introduced. Subsequently, we develop the incremental mechanisms to update the approximations of VQFDRS when multiple attributes are added to or deleted from an ordered data, respectively. Then, on this basis, a static calculation approximations algorithm and two incremental calculation approximations algorithms are designed, respectively. Finally, a series of numerical comparative experiments are performed on six public datasets. Experimental results indicate that the VQFDRS has good robustness, and the incremental algorithms are highly efficient compared with static algorithm under the dynamic data environment. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]