Search

Fuzzy rough set theory has been successfully applied to many attribute reduction methods, in which the lower approximation set plays a pivotal role. However, the definition of lower approximation used has ignored the information conveyed by the upper approximation and the boundary region. This oversight has resulted in an unreasonable relation representation of the target set. Despite the fact that scholars have proposed numerous enhancements to rough set models, such as the variable precision model, none have successfully resolved the issues inherent in the classical models. To address this limitation, this paper proposes an unsupervised attribute reduction algorithm for mixed data based on an improved optimal approximation set. Firstly, the theory of an improved optimal approximation set and its associated algorithm are proposed. Subsequently, we extend the classical theory of optimal approximation sets to fuzzy rough set theory, leading to the development of a fuzzy improved approximation set method. Finally, building on the proposed theory, we introduce a novel, fuzzy optimal approximation-set-based unsupervised attribute reduction algorithm (FOUAR). Comparative experiments conducted with all the proposed algorithms indicate the efficacy of FOUAR in selecting fewer attributes while maintaining and improving the performance of the machine learning algorithm. Furthermore, they highlight the advantage of the improved optimal approximation set algorithm, which offers higher similarity to the target set and provides a more concise expression. [ABSTRACT FROM AUTHOR]

In this article, we give the sharp bounds of probabilistic Kolmogorov N , δ -widths and probabilistic linear N , δ -widths of the multivariate Sobolev space W 2 A with common smoothness on a S q norm equipped with the Gaussian measure μ , where A ⊂ R d is a finite set. And we obtain the sharp bounds of average width from the results of the probabilistic widths. These results develop the theory of approximation of functions and play important roles in the research of related approximation algorithms for Sobolev spaces. [ABSTRACT FROM AUTHOR]

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1−∊ fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor ∊ approaches 0 when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast ∊ approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1−∊ fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary's distribution, then we design an algorithm that achieves a 1−∊ fraction of the weighted average of the optimal profit of each distribution the adversary picks. In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1+∊) the mixed packing-covering problem with O(γ m log (n/Δ)/∊2) oracle calls where the constraint matrix of this LP has dimension n× m, the success probability of the algorithm is 1−Δ, and γ quantifies how significant a single request is when compared to the sum total of all requests. We discuss implications of our results to several special cases including online combinatorial auctions, network routing, and the adwords problem. [ABSTRACT FROM AUTHOR]

In causal inference, natural strata are a new compromise between conventional strata and matching in a fixed ratio, say pair matching or matching two controls to each treated individual. Like matching in a fixed ratio, natural strata: (a) do not require weights, (b) balance many measured covariates beyond those that define the strata and (c) provide closer balance for a measured continuous covariate coarsely cut to form strata. Unlike matching in a fixed ratio, the ratio of controls to treated individuals need not be an integer, so if the data permit a fixed ratio comparison of 1‐to‐2.5 or even 1‐to‐0.75, then these ratios are possible using natural strata. Optimal natural strata are defined by a moderate number of fixed strata plus an integer program that minimizes the imbalance in many other measured covariates that are not used to specify the strata. Solving large integer programs is computationally difficult. A tool in the theory of approximation algorithms is 'randomized rounding of a linear program' to produce an integer solution: a fractional solution to a linear program defines a probability distribution for an integer‐valued random variable which is sampled. We apply this tool in a new way to produce natural strata and develop new properties of randomized rounding in this context. When proportional strata are impractical, we approximate them by minimizing the earthmover distance to proportionality. The method is applied to study birth outcomes for older and younger mothers in the United States in 2018. An R package natstrat is available at CRAN. [ABSTRACT FROM AUTHOR]

We consider a new extension of the bin packing problem in which a set of connectivity constraints should be satisfied. An undirected graph with a weight function on the nodes is given. The objective is to pack all the nodes in the minimum number of unit-capacity bins, such that the induced subgraph on the set of nodes packed in each bin is connected. After analyzing some structural properties of the problem, we present a linear time approximation algorithm for this problem when the underlying graph is traceable. We show that the approximation factor of this algorithm is 2 and this factor is tight. Finally, concerning the investigated structural properties, we extend the algorithm for more general graphs. This extended algorithm also has a tight approximation factor of 2. [ABSTRACT FROM AUTHOR]

In the early 1980s it was well established that Leray solutions of the unforced Navier-Stokes equations in Rn decay in energy norm for large t. With the works of T. Miyakawa, M. Schonbek and others it is now known that the energy decay rate cannot in general be any faster than t-(n+2)/4 and is typically much slower. In contrast, we show in this note that, given an arbitrary Leray solution u(t), the difference of any two Stokes approximations to the Navier-Stokes flow u(t) will always decay at least as fast as t-(n+2)/4, no matter how slow the decay of ku(t) kL2(Rn) might be. [ABSTRACT FROM AUTHOR]

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = (V, E) with a degree upper bound Bv on each vertex v ∈ V, and the task is to find a spanning tree of minimum cost that satisfies all the degree bounds. Let OPT be the cost of an optimal solution to this problem. In this article we present a polynomial-time algorithm which returns a spanning tree T of cost at most OPT and dT (v) ≤ Bv + 1 for all v, where dT(v) denotes the degree of v in T. This generalizes a result of Fürer and Raghavachari [1994] to weighted graphs, and settles a conjecture of Goemans [2006] affirmatively. The algorithm generalizes when each vertex v has a degree lower bound Av and a degree upper bound Bv, and returns a spanning tree with cost at most OPT and Av --1 ≤ dT (v) ≤ Bv + 1 for all v ∈ V. This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [2001] for the design of approximation algorithms. [ABSTRACT FROM AUTHOR]

In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient. Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. As a corollary of our result, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. By prior work, there is a deterministic local algorithm that achieves the approximation factor of 4 -- 1[Δ/2] in graphs of maximum degree Δ. This approximation ratio is known to be optimal in the port-numbering model--our main theorem implies that it is optimal also in the standard model in which each node has a unique identifier. Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is (α, r)-homogeneous if its nodes are linearly ordered so that an α fraction of nodes have pairwise isomorphic radius-r neighbourhoods. We show that there exists a finite (α, r)-homogeneous 2k-regular graph of girth at least g for any α < 1 and any r, k, and g. [ABSTRACT FROM AUTHOR]

A common approach to clustering data is to view data objects as points in a metric space, and then to optimize a natural distance-based objective such as the k-median, k-means, or min-sum score. For applications such as clustering proteins by function or clustering images by subject, the implicit hope in taking this approach is that the optimal solution for the chosen objective will closely match the desired "target" clustering (e.g., a correct clustering of proteins by function or of images by who is in them). However, most distance-based objectives, including those mentioned here, are NP-hard to optimize. So, this assumption by itself is not sufficient, assuming P ≠ NP, to achieve clusterings of low-error via polynomial time algorithms. In this article, we show that we can bypass this barrier if we slightly extend this assumption to ask that for some small constant c, not only the optimal solution, but also all c-approximations to the optimal solution, differ from the target on at most some ∈ fraction of points--we call this (c, ∈)-approximation-stability. We show that under this condition, it is possible to efficiently obtain low-error clusterings even if the property holds only for values c for which the objective is known to be NP-hard to approximate. Specifically, for any constant c > 1, (c, ∈)-approximation-stability of k-median or k-means objectives can be used to efficiently produce a clustering of error O(∈) with respect to the target clustering, as can stability of the min-sum objective if the target clusters are sufficiently large. Thus, we can perform nearly as well in terms of agreement with the target clustering as if we could approximate these objectives to this NP-hard value. [ABSTRACT FROM AUTHOR]

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q > 2. Specifically, we show that the partition function is hard for the complexity class #RHπ1 under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first-order phase transition of the "random cluster" model, which is a probability distribution on graphs that is closely related to the q-state Potts model. [ABSTRACT FROM AUTHOR]

Cross-validation (CV) is a widely adopted approach for selecting the optimal model. However, the computation of empirical cross-validation error (CVE) has high complexity due to multiple times of learner training. In this paper, we develop a novel approximation theory of CVE and present an approximate approach to CV based on the Bouligand influence function (BIF) for kernel-based algorithms. We first represent the BIF and higher order BIFs in Taylor expansions, and approximate CV via the Taylor expansions. We then derive an upper bound of the discrepancy between the original and approximate CV. Furthermore, we provide a novel computing method to calculate the BIF for general distribution, and evaluate BIF criterion for sample distribution to approximate CV. The proposed approximate CV requires training on the full data set only once and is suitable for a wide variety of kernel-based algorithms. Experimental results demonstrate that the proposed approximate CV is sound and effective. [ABSTRACT FROM AUTHOR]

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any a-approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem by a can be used to construct an a-approximation mechanism that is truthful in expectation. This immediately yields a variety of new and significantly improved results for various problem domains and furthermore, yields truthful (in expectation) mechanisms with guarantees that match the best-known approximation guarantees when truthfulness is not required. In particular, we obtain the first truthful mechanisms with approximation guarantees for a variety of multiparameter domains. We obtain truthful (in expectation) mechanisms achieving approximation guarantees of O(vm) for combinatorial auctions (CAs), (1 + ∊) for multiunit CAs with B = O(log m) copies of each item, and 2 for multiparameter knapsack problems (multi-unit auctions). [ABSTRACT FROM AUTHOR]

The restless bandit problem is one of the mostwell-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any nontrivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. In this article, we consider the FEEDBACK MAB problem, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process whose exact state is only revealed when the arm is played. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is also an instance of a Partially Observable Markov Decision Process (POMDP), and is widely studied in wireless scheduling and unmanned aerial vehicle (UAV) routing. Unlike the stochastic MAB problem, the FEEDBACK MAB problem does not admit to greedy index-based optimal policies. We develop a novel duality-based algorithmic technique that yields a surprisingly simple and intuitive (2 + ϵ)-approximate greedy policy to this problem. We show that both in terms of approximation factor and computational efficiency, our policy is closely related to the Whittle index, which is widely used for its simplicity and efficiency of computation. Subsequently we define a multi-state generalization, that we term MONOTONE bandits, which remains subclass of the restless bandit problem. We show that our policy remains a 2-approximation in this setting, and further, our technique is robust enough to incorporate various side-constraints such as blocking plays, switching costs, and even models where determining the state of an arm is a separate operation from playing it. Our technique is also of independent interest for other restless bandit problems, and we provide an example in non-preemptive machine replenishment. Interestingly, in this case, our policy provides a constant factor guarantee, whereas the Whittle index is provably polynomially worse. By presenting the first O(1) approximations for nontrivial instances of restless bandits as well as of POMDPs, our work initiates the study of approximation algorithms in both these contexts. [ABSTRACT FROM AUTHOR]

The spin-adaptation of single-reference quantum chemical methods for excited states of open-shell systems has been nontrivial. The primary reason is that the configuration space, generated by a truncated rank of excitations from only one component of a reference multiplet, is spin-incomplete. Those “missing” configurations are of higher ranks and can, in principle, be recaptured by a particular class of excitation operators. However, the resulting formalisms are then quite involved and there are situations [e.g., time-dependent density functional theory (TD-DFT) under the adiabatic approximation] that prevent one from doing so. To solve this issue, we propose here a tensor-coupling scheme that invokes all the components of a reference multiplet (i.e., a tensor reference) rather than increases the excitation ranks. A minimal spin-adapted n-tuply excited configuration space can readily be constructed by tensor products between the n-tuple tensor excitation operators and the chosen tensor reference. Further combined with the tensor equation-of-motion formalism, very compact expressions for excitation energies can be obtained. As a first application of this general idea, a spin-adapted open-shell random phase approximation is first developed. The so-called “translation rule” is then adopted to formulate a spin-adapted, restricted open-shell Kohn–Sham (ROKS)-based TD-DFT (ROKS-TD-DFT). Here, a particular symmetry structure has to be imposed on the exchange-correlation kernel. While the standard ROKS-TD-DFT can access only excited states due to singlet-coupled single excitations, i.e., only some of the singly excited states of the same spin (Si) as the reference, the new scheme can capture all the excited states of spin Si-1, Si, or Si+1 due to both singlet- and triplet-coupled single excitations. The actual implementation and computation are very much like the (spin-contaminated) unrestricted Kohn–Sham-based TD-DFT. It is also shown that spin-contaminated spin-flip configuration interaction approaches can easily be spin-adapted via the tensor-coupling scheme. [ABSTRACT FROM AUTHOR]

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination using a confluent flow. Single- and multi-commodity confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are (multi-commodity) confluent flows since Internet routing is destination based. We present near-tight approximation algorithms, hardness results, and existence theorems for minimizing congestion in single-commodity confluent flows. The maximum edge congestion of a single-commodity confluent flow occurs at one of the incoming edges of the destination. Therefore, finding a minimum-congestion confluent flow is equivalent to the following problem: given a directed graph G with k sinks and non-negative demands on all the nodes of G, determine a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. The main result of this article is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + 1n(k) in G, if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than Hk , the kth harmonic number, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (log2 k)/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand. We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph is k-connected. In particular, we prove that k-connected graphs with k sinks admit confluent flows of congestion less than AC +dmax, where C is the congestion of the best splittable flow, and dmax is the maximum demand of any node in G. The proof of this existence theorem is non-constructive and relies on topological techniques introduced by Lovász. [ABSTRACT FROM AUTHOR]

We present constant-factor approximation algorithms for several widely-studied NP-hard optimization problems in network design, including the multicommodity rent-or-buy, virtual private network design, and single-sink buy-at-bulk problems. Our algorithms are simple and their approximation ratios improve over those previously known, in some cases by orders of magnitude. We develop a general analysis framework to bound the approximation ratios of our algorithms. This framework is based on a novel connection between random sampling and game-theoretic cost sharing. [ABSTRACT FROM AUTHOR]

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓp norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2poly(log n)), we show that there is no polynomial-time algorithm with approximation ratio 2(log n)1/2-∈ where n is the dimension of the lattice and ∈ > 0 is an arbitrarily small constant. We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2(log n)½-∈. [ABSTRACT FROM AUTHOR]

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n² cycle covers, each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than ⌊d/2⌋ copies of any 2-cycle then we can find a similar decomposition into n² pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2/3 of the weight of the longest tour. This improves upon the previous 5/8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5-approximation algorithm for the latter problem, which is again much simpler than the previous one. For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log2 n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log2 n. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4). [ABSTRACT FROM AUTHOR]

In the ASYMMETRIC k-CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point from its center is as small as possible. We showthat the ASYMMETRIC k-CENTER problem is hard to approximate up to a factor of log* n - 0(1) unless NP ⊆ DTIME(nlog log n). Since an O(log* n)-approximation algorithm is known for this problem, this resolves the asymptotic approximability of ASYMMETRIC k-CENTER. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric) k-Center problem with costs. [ABSTRACT FROM AUTHOR]

In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an associated positive weight. The cost of travel through a face is the Euclidean distance traveled, multiplied by the face's weight. For a given parameter ε , 0 < ε < 1, the cost of the computed paths is at most 1 + ε times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C( P) ...) time, where C ( P) captures geometric parameters and the weights of the faces of P. [ABSTRACT FROM AUTHOR]

This paper is motivated by Marchi and Arruda (Math Mech Solids, 2018), who developed numerous approximations to the inverse Langevin function, minimizing their maximum relative error with the help of special software. We are convinced that this method, together with the minimax approximation, is the most robust and versatile approximation algorithm. It uses one of the first objective functions developed by differential evolution. It guarantees the best solution in one trial. In previous papers, a constraint on the error function of the inverse Langevin function was imposed, but here we discuss the approximants resulting from various types of constraint. The evolution of the different mathematical methods that have been used to approximate the inverse Langevin function will also be treated, providing a useful starting point for researchers beginning to work in the field of approximation theory. To categorize the existing solutions, we find the optimal approximations of the inverse Langevin function for a given complexity and for different constraints on the error function. [ABSTRACT FROM AUTHOR]

This paper introduces an efficient algorithm for finding the dominant generalized eigenvectors of a pair of symmetric matrices. Combining tools from approximation theory and convex optimization, we develop a simple scalable algorithm with strong theoretical performance guarantees. More precisely, the algorithm retains the simplicity of the well-known power method but enjoys the asymptotic iteration complexity of the powerful Lanczos method. Unlike these classic techniques, our algorithm is designed to decompose the overall problem into a series of subproblems that only need to be solved approximately. The combination of good initializations, fast iterative solvers, and appropriate error control in solving the subproblems lead to a linear running time in the input sizes compared to the superlinear time for the traditional methods. The improved running time immediately offers acceleration for several applications. As an example, we demonstrate how the proposed algorithm can be used to accelerate canonical correlation analysis, which is a fundamental statistical tool for learning of a low-dimensional representation of high-dimensional objects. Numerical experiments on real-world datasets confirm that our approach yields significant improvements over the current state of the art. [ABSTRACT FROM AUTHOR]

In this article we present and analyse new multilevel adaptations of classical stochastic approximation algorithms for the computation of a zero of a function f : D → R d defined on a convex domain D ⊂ R d , which is given as a parameterised family of expectations. The analysis of the error and the computational cost of our method is based on similar assumptions as used in Giles (Oper Res 56(3):607–617, 2008) for the computation of a single expectation. Additionally, we essentially only require that f satisfies a classical contraction property from stochastic approximation theory. Under these assumptions we establish error bounds in pth mean for our multilevel Robbins–Monro and Polyak–Ruppert schemes that decay in the computational time as fast as the classical error bounds for multilevel Monte Carlo approximations of single expectations known from Giles (Oper Res 56(3):607–617, 2008). Our approach is universal in the sense that having multilevel implementations for a particular application at hand it is straightforward to implement the corresponding stochastic approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper tackles the problem of millimeter-wave (mmWave) channel estimation in massive MIMO communication systems. A new Bayes-optimal channel estimator is derived using recent advances in the approximate belief propagation Bayesian inference paradigm. By leveraging the inherent sparsity of the mmWave MIMO channel in the angular domain, we recast the underlying channel estimation problem into that of reconstructing a compressible signal from a set of noisy linear measurements. Then, the generalized approximate message passing (GAMP) algorithm is used to find the entries of the unknown mmWave MIMO channel matrix. Unlike all the existing works on the same topic, we model the angular-domain channel coefficients by Laplacian distributed random variables. Furthermore, we establish the closed-form expressions for the various statistical quantities that need to be updated iteratively by GAMP. To render the proposed algorithm fully automated, we also develop an expectation-maximization (EM) based procedure that can be easily embedded within GAMP’s iteration loop in order to learn all the unknown parameters of the underlying Bayesian inference problem. The computer simulations show that the proposed combined EM-GAMP algorithm under a Laplacian prior exhibits improvements both in terms of channel estimation accuracy, achievable rate, and computational complexity, as compared to the Gaussian mixture prior that has been advocated in the recent literature. In addition, it is found that the Laplacian prior speeds up the convergence time of GAMP over the entire signal-to-noise ratio range. [ABSTRACT FROM AUTHOR]

We study the classic assortment optimization problem in which a retailer seeks the revenue maximizing set of products to offer to each arriving customer. This study relates two variants of this assortment problem: the space constrained assortment problem, in which the retailer has a limit on the total space of the offered assortment, and the fixed cost assortment problem, in which the retailer incurs a fixed cost for each offered product. In particular, we develop an approximation scheme for the space constrained problem for any random utility choice model that only relies on the ability to solve the corresponding fixed cost assortment problem. We then apply this technique to give a constant factor approximation scheme for the space constrained assortment problem under a classical model for vertically differentiated products. Last, we present computational results to show the efficacy of this approach. [ABSTRACT FROM AUTHOR]

The project MoVe IT! (www.moveit-fp7.eu), funded by the Seventh Framework Programme of the European Union, was focussed on modernisation of inland waterway vessels by retrofitting. In order to stimulate an implementation of the results by the industry, visualization of the positive impacts was realised by a set of vivid demonstrators. In this paper, the demonstrations by simulators for a single screw motor cargo vessel of the type Johann Welker are described. The motion simulations are carried out by a custom made (for inland vessels developed) computer program, which use common naval architect force calculation algorithms and a new approximation theory for added masses. The simulator demonstrations comprise descriptions and visualisations of ship lengthening, application of different rudder and a new propulsion device. Five different cases are examined, the original vessel and four retrofit options. First retrofit variant is the lengthened vessel with original rudder and propeller. Other two analysis are performed changing only the rudder system. In fourth simulator demonstration the original propeller is changed to a pump propeller (a novel propulsion device). The environment are in the simulator demonstrations: constant draught of the vessel, and calm, infinite deep waterway. As results of simulator demonstrations the effects on fuel consumption and manoeuvrability are discussed in the paper. [ABSTRACT FROM AUTHOR]

Abstract The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set S of leaf labels and a set R of resolved triplets over S and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a 1 ∕ 4 -approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted k -ary phylogenetic tree for any specified k ≥ 2 subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every S ′ ⊆ S with | S ′ | = 3 , R contains at least one rooted triplet involving the leaf labels in S ′), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered. [ABSTRACT FROM AUTHOR]

Attribute subset selection is an important issue in data mining and information processing. However, most automatic methodologies consider only the relevance factor between samples while ignoring the diversity factor. This may not allow the utilization value of hidden information to be exploited. For this reason, we propose a hybrid model named intuitionistic fuzzy (IF) rough set to overcome this limitation. The model combines the technical advantages of rough set and IF set and can effectively consider the above-mentioned statistical factors. First, fuzzy information granules based on IF relations are defined and used to characterize the hierarchical structures of the lower and upper approximations of IF rough set within the framework of granular computing. Then, the computation of IF rough approximations and knowledge reduction in IF information systems are investigated. Third, based on the approximations of IF rough set, significance measures are developed to evaluate the approximation quality and classification ability of IF relations. Furthermore, a forward heuristic algorithm for finding one optimal reduct of IF information systems is developed using these measures. Finally, numerical experiments are conducted on public datasets to examine the effectiveness and efficiency of the proposed algorithm in terms of the number of selected attributes, computational time, and classification accuracy. [ABSTRACT FROM AUTHOR]

Abstract We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using " t -spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t -spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time. [ABSTRACT FROM AUTHOR]

Abstract We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP -complete, and give constant-factor approximation algorithms for those problems. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems. [ABSTRACT FROM AUTHOR]

In this article we continue the study started in [8] to use Riesz MValgebras for IoT devices signals processing. The Shepard local approximation operators introduced in [8] were defines such that to approximate single variable functions. In real industrial usage, the signals coming from IoT devices may be influenced by mode than a parameter, and thus we introduce generalized Shepard local approximation operators that can approximate multi-dimensional functions and some numerical experiments are considered. [ABSTRACT FROM AUTHOR]

Abstract The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a (1 − ε) -approximation for two agents, and a (8 / 9 − ε) -approximation for three agents. Apart from the extension to matroids, the (8 / 9 − ε) -approximation for three agents improves on a (7 / 8 − ε) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed. [ABSTRACT FROM AUTHOR]

Abstract This paper considers a class of nonlinear filtering algorithms based on variational Bayesian (VB) theory to settle the unknown measurement noise problem in target tracking system. When the unknown measurement noise is conditionally independent of states, based on the variational idea, estimate of probability density function of state is converted into approximation two probability density functions for both unknown noise and nonlinear states. Then, an iterative algorithm is established to jointly estimate the state and the unknown measurement noise using variational Bayesian inference. Thus, the unknown measurement noise could be estimated as hidden state. The convergence result of the proposed nonlinear probability density function approximation algorithm is also given. The simulation results of typical examples show that the proposed VB based methods have superior performance to these classic algorithms in target tracking problems. [ABSTRACT FROM AUTHOR]

The topic of rough set theory considers a relation to determine the lower and upper approximations of a set X. Originally, this relation was assumed to be an equivalence relation. This research focuses on using tolerance relations instead of equivalences, i.e. we do not assume the transitivity of the relations. More specifically, in this paper we investigate tolerances induced by irredundant coverings. We characterize the interrelation between the lattices of lower and upper approximations of such tolerances R and p. The theory of Formal Concept Analysis makes it possible to examine the inclusions of the resulting concepts. We also use quasiorders (denoted by ≤ and ≥ (p)) and an equivalence relation (denoted by ker p) for summarizing the connection between tolerances and lattices in a theorem. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is to develop new techniques in approximate dynamic programming, along with the notions of rounded distributions and inventory filtering, to devise a quasi-PTAS for the capacitated assortment planning problem, recently studied by Goyal et al. (Oper Res 64(1):219-235, 2016). Motivated by real-life applications, their nested preference lists model stands as the only setting in dynamic assortment optimization where provably ϵ-optimal inventory levels can be efficiently computed. However, these findings crucially depend on certain distributional assumptions, leaving the general problem wide open in terms of approximability prior to this work. In addition to proposing the first rigorous approach for handling the nested preference lists model in its utmost generality, from a technical perspective, we augment the existing literature on dynamic programming with a number of promising ideas. These are novel algorithmic tools for efficiently keeping approximate distributions as part of the state description, while losing very little information and while accumulating only small approximation errors throughout the overall computation. From a conceptual perspective, at the cost of losing an ϵ-factor in optimality, we show how to dramatically improve on the truly exponential nature of standard dynamic programs, which seem essential for the purpose of computing optimal inventory levels. [ABSTRACT FROM AUTHOR]

In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant approximation ratio smaller than 2. The considered greedy algorithms and approaches based on linear programming involve the incorporation of k-restricted full components for some k ≥ 3. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for k → ∞. However, the running time is also exponentially dependent on k, so only small k are tractable in practice. We investigate different implementation aspects and parameter choices that finally allow us to construct algorithms (somewhat) feasible for practical use. We compare the algorithms against each other, to an exact algorithm based on integer linear programs, and to fast and simple 2-approximations as well as state-of-the-art heuristics. [ABSTRACT FROM AUTHOR]

Abstract We demonstrate here that submodular minimization (SM) problems subject to constraints containing up to two variables per inequality, SM2, are 2-approximable in polynomial time and a better approximation factor cannot be achieved in polynomial time unless NP = P. The 2-approximation holds when either the constraints have the round-up property (the rounding up of a feasible fractional solution is feasible) or, if the constraints do not have this property, for monotone submodular functions. The submodular minimization or supermodular maximization on constraints where the coefficients of the two variables in each constraint are of opposite signs (monotone constraints) is solvable in polynomial time. The 2-approximability and the polynomial time solvability for monotone constraints hold also for multi-sets that contain elements with integer multiplicity greater than 1, except that the running time is then pseudo-polynomial in that it depends on the range of the variables. This complexity cannot be improved unless NP = P. Our results indicate that SM2 problems are not much harder than the respective linear integer problems on two variables per constraint: For monotone constraints both problems are polynomial time solvable, and for non-monotone NP-hard problems, both problems have 2-approximation algorithms. For SM2 problems the factor 2 approximation is provably best possible, whereas for the respective linear integer problems it has not been established that the factor 2 is best possible, but this has been conjectured. On the other hand, for SM2 problems where the two variables constraints' coefficients form a totally unimodular constraint matrix, the linear integer optimization problem is solved in polynomial time, whereas the submodular optimization is proved here to be NP-hard. The submodular minimization NP-hard problems for which our general purpose 2-approximation algorithm applies include submodular-vertex cover, submodular-2SAT, submodular-min satisfiability, submodular-edge deletion for clique, submodular-node deletion for biclique and others. [ABSTRACT FROM AUTHOR]

Milano Retinex is a family of spatial color algorithms inspired by Retinex and mainly devoted to the image enhancement. In the so-called point-based sampling Milano Retinex algorithms, this task is accomplished by processing the color of each image pixel based on a set of colors sampled in its surround. This paper presents STAR, a segmentation based approximation of the point-based sampling Milano Retinex approaches: it replaces the pixel-wise image sampling by a novel, computationally efficient procedure that detects once for all the color and spatial information relevant to image enhancement from clusters of pixels output by a segmentation. The experiments reported here show that STAR performs similarly to previous point-based sampling Milano Retinex approaches and that STAR enhancement improves the accuracy of the well-known algorithm scale-invariant feature transform on the description and matching of photographs captured under difficult light conditions. [ABSTRACT FROM AUTHOR]

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

In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a (2k-1)-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variation of the classic dominating set problem - The Two Disjoint Connected Dominating Sets (DCDS) problem, which finds applications in many real domains including wireless sensor networks. In the DCDS problem, we are given a graph G = ( V , E ) and required to find a new edge set E ′ with minimum cardinality such that the resulting new graph after the adding of E ′ has a pair of disjoint connected dominating sets. This problem is very hard in general graphs, and we show that it is NP -hard even restricted to trees. We also present a polynomial time approximation algorithm for the DCDS problem for arbitrary trees with performance ratio 3 2 asymptotically. [ABSTRACT FROM AUTHOR]

Non-orthogonal multiple access (NOMA)-based cognitive wireless networks can improve the spectral efficiency to utilize the vacant spectrum resource and exploit the power domain diversity. In this paper, we formulate a max-min resource allocation problem for video traffic in NOMA-based cognitive wireless networks as a mixed integer non-linear programming (MINLP) problem. The max-min video transmission problem is subject to the constraints of maximum accessed user number at each subchannel, total available energy of each secondary user, video encoding characteristics, and interference power threshold. To solve the formulated MINLP problem, we divide it into two subproblems, i.e., a power allocation and secondary user scheduling subproblem, and a video packet scheduling subproblem. First, we apply a successive convex approximation to transform the joint power allocation and secondary user scheduling subproblem into a bi-convex programming problem. Second, the binary search and dual decomposition methods are combined to obtain the approximated optimal power allocation and secondary user scheduling solutions. Finally, we propose a heuristic packet scheduling algorithm. Simulation numerical results show that the proposed algorithm improves the video quality and guarantees the fairness among different secondary users. [ABSTRACT FROM AUTHOR]

We propose a mixed “skeleton” and “equivalence” nested approximation method to compress the impedance matrix of the method of moments for the wideband multiscale simulations. We first introduce a nested skeleton approximation, where the impedance matrix is expressed recursively by sampling the dominant basis functions (e. g., skeletons) with a fully algebraic implementation from the original basis functions. The idea is to introduce the automatically constructed test surface around the interface between near- and far-field regions, for each group the dominant RWGs are sampled recursively with the adaptive cross approximation to compress the matrix against the test surface. Second, we introduce a mixed-form algorithm of “skeleton” and “equivalence” nested approximation method, at low levels, the nested skeleton approximation is employed, and it is smoothly transferred to standard wideband nested equivalence approximation (WNESA) at high levels. An accurate number of skeletons can be always found with a predetermined threshold at a low level, which will improve computation efficiency, with respect to WNESA. The computational complexity of the proposed algorithm is $\mathcal {O}(N\log {N})$ , $N$ is the number of unknowns. Numerical wideband multiscale simulations demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

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

We present the spatial discretization of the nonlinear convective flux in the incompressible Navier–Stokes equations using local boundary-value problems. The finite-volume discretization of the incompressible Navier–Stokes equations over staggered grids requires the approximation of the cell-face velocity components. In the proposed method, the cell-face velocity components are computed from local boundary-value problems, with the pressure gradient and the gradient of the transverse flux as source terms. The approximation is expressed as the sum of the homogeneous part, corresponding to the convection–diffusion operator, and the inhomogeneous part, corresponding to the source terms. The homogeneous part of the approximation is shown to be a weighted average of the central and the upwind approximation and thus, is first-order convergent over coarse grids and second-order over finer grids. We show that the inhomogeneous part of the approximation effectively removes the numerical diffusion introduced by the homogeneous part. The inclusion of the source terms in the local boundary-value problem results in a more accurate approximation that shows uniform second-order convergence and does not introduce any spurious oscillations. [ABSTRACT FROM AUTHOR]

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP. [ABSTRACT FROM AUTHOR]

A physics-based rank-revealing multilevel algorithm to more efficiently compute low-rank (LR) approximations of the method of moments matrix blocks ${\mathbf{Z}}^{\textrm {os}}$ is presented. Using surface subsets of volumetric nonuniform spherical grids (proxy grids), an LR approximation ${\mathbf{Z}}^{\textrm {os}}\approx {\mathbf{AB}}^{\dagger }$ is obtained in two stages: 1) an upward pass and a downward pass on a multilevel tree, via truncated singular value decomposition-based analyses of interactions between source subclusters and their attendant proxy grids, rapidly estimates the rank and yields a domain of ${\mathbf{Z}}^{\textrm {os}}$ , in the form of a matrix ${\mathbf{B}}$ with orthonormal columns and 2) a fast matrix–matrix multiplication step yields ${\mathbf{A}}$. The algorithm reduces the ${\mathcal{ O}}(N^{3})$ computational costs of revealing the rank to ${\mathcal{ O}}(N^{2})$ or ${\mathcal{ O}}(N^{3/2})$ operations and that of finding an LR approximation to ${\mathcal{ O}}(N^{2})$ or ${\mathcal{ O}}(N^{3/2}\log N)$ operations by adopting enclosing or belt-like proxy grids for electromagnetically large basis/testing function distributions that are either densely packed in a volume or quasi-planar, respectively. [ABSTRACT FROM AUTHOR]