This paper presents the first convergence result for random search algorithms to a subset of the Pareto set of given maximum size k with bounds on the approximation quality. The core of the algorithm is a new selection criterion based on a hypothetical multilevel grid on the objective space. It is shown that, when using this criterion for accepting new search points, the sequence of solution archives converges with probability one to a subset of the Pareto set that epsilon-dominates the entire Pareto set. The obtained approximation quality epsilon is equal to the size of the grid cells on the finest level of resolution that allows an approximation with at most k points within the family of grids considered. While the convergence result is of general theoretical interest, the archiving algorithm might be of high practical value for any type iterative multiobjective optimization method, such as evolutionary algorithms or other metaheuristics, which all rely on the usage of a finite on-line memory to store the best solutions found so far as the current approximation of the Pareto set.
One option to control the approximation quality under size restrictions is to define a which maps each possible solution set to a real value that can then be used to decide on the inclusion of a new search point. Several algorithms have been proposed that implement this concept @cite_20 @cite_16 . In case that such a quality indicator fulfils certain monotonicity conditions, it can be used as a potential function in the convergence analysis. As shown in @cite_9 @cite_17 , this entails convergence to a subset of the Pareto set as a local optimum of the quality indicator, but it remained open how such a local optimum relates to a guarantee on the approximation quality @math . @cite_17 also analyzed an adaptive grid archiving method proposed in @cite_19 and proved that after finite time, even though the solution set itself might permanently oscillate, it will always represent an @math -approximation whose approximation quality depends on the granularity of the adaptive grid and on the number of allowed solutions. The results depend on the additional assumption that the grid boundaries converge after finite time, which is fulfilled in certain special cases.
@cite_9 @cite_19 @cite_16 @cite_20 @cite_17
2973707709 2808191361 2163637155 2263717697
In sparse approximation theory, the fundamental problem is to reconstruct a signal A∈ℝn from linear measurements 〈Aψi〉 with respect to a dictionary of ψi's. Recently, there is focus on the novel direction of Compressed Sensing [9] where the reconstruction can be done with very few—O(k logn)—linear measurements over a modified dictionary if the signal is compressible, that is, its information is concentrated in k coefficients with the original dictionary. In particular, these results [9, 4, 23] prove that there exists a single O(k logn) ×n measurement matrix such that any such signal can be reconstructed from these measurements, with error at most O(1) times the worst case error for the class of such signals. Compressed sensing has generated tremendous excitement both because of the sophisticated underlying Mathematics and because of its potential applications In this paper, we address outstanding open problems in Compressed Sensing. Our main result is an explicit construction of a non-adaptive measurement matrix and the corresponding reconstruction algorithm so that with a number of measurements polynomial in k, logn, 1 e, we can reconstruct compressible signals. This is the first known polynomial time explicit construction of any such measurement matrix. In addition, our result improves the error guarantee from O(1) to 1 + e and improves the reconstruction time from poly(n) to poly(k logn) Our second result is a randomized construction of O(kpolylog (n)) measurements that work for each signal with high probability and gives per-instance approximation guarantees rather than over the class of all signals. Previous work on Compressed Sensing does not provide such per-instance approximation guarantees; our result improves the best known number of measurements known from prior work in other areas including Learning Theory [20, 21], Streaming algorithms [11, 12, 6] and Complexity Theory [1] for this case Our approach is combinatorial. In particular, we use two parallel sets of group tests, one to filter and the other to certify and estimate; the resulting algorithms are quite simple to implement We consider the over-time version of the Max-Min Fair Allocation problem. Given a time horizon @math , with at each time t a set of demands and a set of available resources that may change over the time defining instance @math , we seek a sequence of solutions @math that (1) are near-optimal at each time t , and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k -lookahead setting where at time t , the instances at times @math are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the over-time version of the problem is much harder than the static one, since it becomes @math -hard even for families of instances for which the static problem is trivial. Then, we provide a @math -approximation algorithm for the off-line setting using as subroutine a ρ-approximation algorithm for the static version. We also give a @math -competitive algorithm for the online setting using also as subroutine a ρ-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a @math -approximation algorithm using as subroutine a ρ-approximation algorithm for the static version. Given any scheme in conservation form and an appropriate uniform grid for the numerical solution of the initial value problem for one-dimensional hyperbolic conservation laws we describe a multiresolution algorithm that approximates this numerical solution to a prescribed tolerance in an efficient manner. To do so we consider the grid-averages of the numerical solution for a hierarchy of nested diadic grids in which the given grid is the finest, and introduce an equivalent multiresolution representation. The multiresolution representation of the numerical solution consists of its grid-averages for the coarsest grid and the set of errors in predicting the grid-averages of each level of resolution in this hierarchy from those of the next coarser one. Once the numerical solution is resolved to our satisfaction in a certain locality of some grid, then the prediction errors there are small for this particular grid and all finer ones; this enables us to compress data by setting to zero small components of the representation which fall below a prescribed tolerance. Therefore instead of computing the time-evolution of the numerical solution on the given grid we compute the time-evolution of its compressed multiresolution representation. Algorithmically this amounts to computing the numerical fluxes of the given scheme at the points of the given grid by a hierarchical algorithm which starts with the computation of these numerical fluxes at the points of the coarsest grid and then proceeds through diadic refinements to the given grid. At each step of refinement we add the values of the numerical flux at the center of the coarser cells. The information in the multiresolution representation of the numerical solution is used to determine whether the solution is locally well-resolved. When this is the case we replace the costly exact value of the numerical flux with an accurate enough approximate value which is obtained by an inexpensive interpolation from the coarser grid. The computational efficiency of this multiresolution algorithm is proportional to the rate of data compression (for a prescribed level of tolerance) that can be achieved for the numerical solution of the given scheme. We consider the problem of maximizing a (non-monotone) submodular function subject to a cardinality constraint. In addition to capturing well-known combinatorial optimization problems, e.g., Max-k-Coverage and Max-Bisection, this problem has applications in other more practical settings such as natural language processing, information retrieval, and machine learning. In this work we present improved approximations for two variants of the cardinality constraint for non-monotone functions. When at most k elements can be chosen, we improve the current best 1 e -- o(1) approximation to a factor that is in the range [1 e + 0.004, 1 2], achieving a tight approximation of 1 2 -- o(1) for k = n 2 and breaking the 1 e barrier for all values of k. When exactly k elements must be chosen, our algorithms improve the current best 1 4 -- o(1) approximation to a factor that is in the range [0.356, 1 2], again achieving a tight approximation of 1 2 -- o(1) for k = n 2. Additionally, some of the algorithms we provide are very fast with time complexities of O(nk), as opposed to previous known algorithms which are continuous in nature, and thus, too slow for applications in the practical settings mentioned above. Our algorithms are based on two new techniques. First, we present a simple randomized greedy approach where in each step a random element is chosen from a set of "reasonably good" elements. This approach might be considered a natural substitute for the greedy algorithm of Nemhauser, Wolsey and Fisher [45], as it retains the same tight guarantee of 1--1 e for monotone objectives and the same time complexity of O(nk), while giving an approximation of 1 e for general non-monotone objectives (while the greedy algorithm of Nemhauser et. al. fails to provide any constant guarantee). Second, we extend the double greedy technique, which achieves a tight 1 2 approximation for unconstrained submodular maximization, to the continuous setting. This allows us to manipulate the natural rates by which elements change, thus bounding the total number of elements chosen.