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]

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]

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]

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 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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Accurate yet efficient computation of the Voigt and complex error function is a challenge since decades in astrophysics and other areas of physics. Rational approximations have attracted considerable attention and are used in many codes, often in combination with other techniques. The 12-term code ' cpf12 ' of Humlíček achieves an accuracy of five to six significant digits throughout the entire complex plane. Here we generalize this algorithm to a larger (even) number of terms. The n  = 16 approximation has a relative accuracy better than 10−5 for almost the entire complex plane except for very small imaginary values of the argument even without the correction term required for the cpf12 algorithm. With 20 terms the accuracy is better than 10−6. In addition to the accuracy assessment we discuss methods for optimization and propose a combination of the 16-term approximation with the asymptotic approximation of the w4 code of Humlíček for high efficiency. [ABSTRACT FROM AUTHOR]

This paper presents an approximate minimum mean squared error (MMSE) adaptive beam-pattern design (ABD) method for MIMO active sensing systems. The proposed approximate MMSE ABD method leverages the physics of the MIMO arrays to provide a linear-Gaussian approximation that is specific to MIMO active sensing systems, and yields a computationally simple optimization problem. Computational complexity analysis confirms this theoretical reduction in the number of floating-point operations required, most notably that evaluation of the proposed approximate optimization cost function grows polynomially with the number of targets being tracked, whereas for evaluation of the exact cost the growth is exponential. Additionally, numerical results indicate that, even for a simple scenario with a single target being tracked, the proposed approximate MMSE ABD method does indeed reduce the mean squared error of target parameter estimation compared to the nonadaptive case, with a reduction in computation time of four orders of magnitude compared to exact MMSE ABD. [ABSTRACT FROM AUTHOR]

In this paper, we present a new low-complexity iterative joint phase estimation and decoding algorithm which can be applied to low-density-parity-check (or turbo) codes for channels affected by strong phase noise. The algorithm exhibits a very good performance and a very low complexity even in strong phase noise, high code rate, and high-order constellations. The proposed algorithm works by first obtaining a preliminary pilots-aided phase estimation. Next, the expressions for the belief propagation messages are approximated around that reference and reduced to a Gaussian canonical form. This results in a simple closed form of a recursive update. Simulations results for phase-shift-keying modulation of size 8 and quadrature-amplitude modulation of size 64 are presented and compared with other algorithms in the literature. [ABSTRACT FROM AUTHOR]

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

We propose a novel online learning paradigm for nonlinear-function estimation tasks based on the iterative projections in the $L^2$ space with probability measure reflecting the stochastic property of input signals. The proposed learning algorithm exploits the reproducing kernel of the so-called dictionary subspace, based on the fact that any finite-dimensional space of functions has a reproducing kernel characterized by the Gram matrix. The $L^2$ -space geometry provides the best decorrelation property in principle. The proposed learning paradigm is significantly different from the conventional kernel-based learning paradigm in two senses: first, the whole space is not a reproducing kernel Hilbert space; and second, the minimum mean squared error estimator gives the best approximation of the desired nonlinear function in the dictionary subspace. It preserves efficiency in computing the inner product as well as in updating the Gram matrix when the dictionary grows. Monotone approximation, asymptotic optimality, and convergence of the proposed algorithm are analyzed based on the variable-metric version of adaptive projected subgradient method. Numerical examples show the efficacy of the proposed algorithm for real data over a variety of methods including the extended Kalman filter and many batch machine-learning methods such as the multilayer perceptron. [ABSTRACT FROM AUTHOR]

Independent Component Analysis (ICA) is a technique for unsupervised exploration of multichannel data that is widely used in observational sciences. In its classic form, ICA relies on modeling the data as linear mixtures of nonGaussian independent sources. The maximization of the corresponding likelihood is a challenging problem if it has to be completed quickly and accurately on large sets of real data. This problem has been addressed by resorting to quasi-Newton methods, which rely on sparse approximations of the Hessian of the log-likelihood. However, those approximations are not accurate when the ICA model does not hold exactly, as is often the case for real datasets. We propose a new algorithm, dubbed Picard, which makes use of sparse approximate Hessians only as a preconditioner to the L-BFGS algorithm, refining the Hessian approximation from a memory of the past iterates. Extensive numerical comparisons to several algorithms of the same class demonstrate the superior performance of the proposed technique, especially on real data. [ABSTRACT FROM AUTHOR]

High efficiency video coding (HEVC) fractional interpolation algorithm has very high computational complexity. In this paper, two approximate HEVC fractional interpolation filters are proposed. They significantly reduce computational complexity of HEVC fractional interpolation with a negligible PSNR loss and bit rate increase. In addition, two approximate HEVC fractional interpolation hardware are proposed. They, in the worst case, can process 45 quad full HD (${3840\times 2160}$) fps. They consume up to 67.1% less energy than original HEVC fractional interpolation hardware. Therefore, they can be used in consumer electronics products that require a low energy HEVC encoder. [ABSTRACT FROM AUTHOR]

We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for the general model of Markov decision processes with nonunit transition times. When preemption is allowed, we provide a (1/2 − ε)-approximation, along with an example showing this is tight. When preemption isn’t allowed, we provide a 1/12-approximation, which improves to a 4/27-approximation when transition times are unity. Our model captures the Markovian Bandits model of Gupta et al., the Stochastic Knapsack model of Dean et al., and the Budgeted Learning model of Guha and Munagala. Our algorithms improve existing results in all three areas. In our analysis, we encounter and overcome to our knowledge a new obstacle: an algorithm that provably exists via analytical arguments, but cannot be found in polynomial time. [ABSTRACT FROM AUTHOR]

An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ , for Δ ≥ 3 , is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Δ , which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K 1 , k -free graphs yields an approximation ratio 2 k − 3 . We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to ( K 1 , k , chair ) -free graphs. [ABSTRACT FROM AUTHOR]

In the Canadian traveler problem, we are given an edge weighted graph with two specified vertices s and t and a probability distribution over the edges that tells which edges are present. The goal is to minimize the expected length of a walk from s to t . However, we only get to know whether an edge is active the moment we visit one of its incident vertices. Under the assumption that the edges are active independently, we show NP-hardness on series-parallel graphs and give results on the adaptivity gap. We further show that this problem is NP-hard on disjoint-path graphs and cactus graphs when the distribution is given by a list of scenarios. We also consider a special case called the multi-target graph search problem. In this problem, we are given a probability distribution over subsets of vertices. The distribution specifies which set of vertices has targets. The goal is to minimize the expected length of the walk until finding a target. For the independent decision model, we show that the problem is NP-hard on trees and give a ( 3.59 + ϵ ) -approximation for trees and a ( 14.4 + ϵ ) -approximation for general metrics. For the scenario model, we show NP-hardness on star graphs. [ABSTRACT FROM AUTHOR]

In this paper, we obtain an approximation theorem by max-product operators with the use of power series method which is more effective than ordinary convergence and includes both Abel and Borel methods. We also estimate the error in this approximation. Finally, we provide an example which satisfies our theorem. [ABSTRACT FROM AUTHOR]

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

The DC Power Flow approximation has been widely used for decades in both industry and academia due to its computational speed and simplicity, but suffers from inaccuracy, in part due to the assumption of a lossless network. This paper presents a natural extension of the DC Power Flow to lossy networks. Our approach is based on reformulating the lossy active power flow equations into a novel fixed-point equation, and iterating this fixed-point mapping to generate a sequence of improving estimates for the active power flow solution. Each iteration requires the solution of a standard DC Power Flow problem with a modified vector of power injections. The first iteration returns the standard DC Power Flow, and one or two additional iterations yields a one or two order-of-magnitude improvement in accuracy. For radial networks, we give explicit conditions on the power flow data which guarantee that the active power flow equations possess a unique solution, and that our iteration converges exponentially and monotonically to this solution. For meshed networks, we extensively test our results via standard power flow cases. [ABSTRACT FROM PUBLISHER]