We consider a two-stage submodular maximization problem subject to a cardinality constraint and k matroid constraints, where the objective function is the expected difference of a nonnegative monotone submodular function and a nonnegative monotone modular function. We give two bi-factor approximation algorithms for this problem. The first is a deterministic $\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right),1} \right)$-approximation algorithm, and the second is a randomized $\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right) - \varepsilon ,1} \right)$-approximation algorithm with improved time efficiency.

Sign truncated matching pursuit (STrMP) algorithm is presented in this paper. STrMP is a new greedy algorithm for the recovery of sparse signals from the sign measurement, which combines the principle of consistent reconstruction with orthogonal matching pursuit (OMP). The main part of STrMP is as concise as OMP and hence STrMP is simple to implement. In contrast to previous greedy algorithms for one-bit compressed sensing, STrMP only need to solve a convex and unconstrained subproblem at each iteration. Numerical experiments show that STrMP is fast and accurate for one-bit compressed sensing compared with other algorithms.

We extend the classical empirical interpolation method [M. Barrault, Y. Maday, N.C.Nguyen and A.T. Patera, An empirical interpolation method: application to efficientreduced-basis discretization of partial differential equations. Compt. Rend. Math.Anal. Num. 339 (2004) 667–672] to a weighted empiricalinterpolation method in order to approximate nonlinear parametric functions with weightedparameters, e.g. random variables obeying various probabilitydistributions. A priori convergence analysis is provided for the proposedmethod and the error bound by Kolmogorov N-width is improved from the recent work [Y.Maday, N.C. Nguyen, A.T. Patera and G.S.H. Pau, A general, multipurpose interpolationprocedure: the magic points. Commun. Pure Appl. Anal. 8(2009) 383–404]. We apply our method to geometric Brownian motion, exponentialKarhunen–Loève expansion and reduced basis approximation of non-affine stochastic ellipticequations. We demonstrate its improved accuracy and efficiency over the empiricalinterpolation method, as well as sparse grid stochastic collocation method.

This paper considers the placement of m sensors at n > m possible locations. Given noisy observations, knowledge of the state correlation matrix, and a mean-square error criterion (equivalently maximizing an efficacy cost criterion), the problem is formulated as an integer programming problem. Computing the solution for large m and n is infeasible, requiring us to look at approximate algorithms and bounding optimal performance. Approximate algorithms include greedy algorithms and variations based on examining the efficacy cost function and projection-based methods that all run in polynomial time of m and n. A sequence of nested bounds are found that upper bound the optimal performance (with analysis based on using matrix pencils and generalized eigenvectors). Finally, we show through simulations that the approximate algorithms perform well and provide tight implementable lower bounds to optimal performance and the nested bounds provide upper bounds to optimal performance with tighter bounds achieved with increasing complexity. The sensor placement problem has many energy applications where we are often confronted with limited resources. Some examples include where to place environmental sensors for an area in which there are many distributed solar photovoltaic generators and where to place grid monitors on an electrical distribution microgrid.

We propose two new algorithms to improve greedy sampling of high-dimensional functions. While the techniques have a substantial degree of generality, we frame the discussion in the context of methods for empirical interpolation and the development of reduced basis techniques for high-dimensional parametrized functions. The first algorithm, based on a saturation assumption of the error in the greedy algorithm, is shown to result in a significant reduction of the workload over the standard greedy algorithm. In a further improved approach, this is combined with an algorithm in which the train set for the greedy approach is adaptively sparsified and enriched. A safety check step is added at the end of the algorithm to certify the quality of the sampling. Both these techniques are applicable to high-dimensional problems and we shall demonstrate their performance on a number of numerical examples.

The convergence and efficiency of the reduced basis method used for the approximation of the solutions to a class of problems written as a parametrized PDE depends heavily on the choice of the elements that constitute the “reduced basis”. The purpose of this paper is to analyze the a priori convergence for one of the approaches used for the selection of these elements, the greedy algorithm. Under natural hypothesis on the set of all solutions to the problem obtained when the parameter varies, we prove that three greedy algorithms converge; the last algorithm, based on the use of an a posteriori estimator, is the approach actually employed in the calculations.

In this paper we study the size of the largest clique ω(G(n, α)) in a random graph G(n, α) on n vertices which has power-law degree distribution with exponent α. We show that, for ‘flat’ degree sequences with α > 2, with high probability, the largest clique in G(n, α) is of a constant size, while, for the heavy tail distribution, when 0 < α < 2, ω(G(n, α)) grows as a power of n. Moreover, we show that a natural simple algorithm with high probability finds in G(n, α) a large clique of size (1 − o(1))ω(G(n, α)) in polynomial time.

Let X = (X1, …, Xn) be a random binary vector, with a known joint distribution P. It is necessary to inspect the coordinates sequentially in order to determine if Xi = 0 for every i, i = 1, …, n. We find bounds for the ratio of the expected number of coordinates inspected using optimal and greedy searching policies.